C - Ascending Labels Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の連結な単純無向グラフが与えられます。 頂点には 1,2,\ldots,N の番号が付けられており、i 個目の辺は頂点 U_i と頂点 V_i を結びます。

以下の条件をすべて満たす整数列 A=(A_1,A_2,\ldots,A_N) を 1 つ構築してください。

  • すべての頂点 v について、0 \le A_v \le N である。
  • A_1=0 である。
  • 頂点 1 以外のすべての頂点 v について、v に隣接する頂点 w のうち A_w=A_v-1 を満たすものがちょうど 1 つ存在する。

なお、本問題の制約下で、上記の条件をすべて満たす整数列が少なくとも 1 つ存在することが証明できます。 また、条件を満たす整数列が複数存在する場合、どれを出力しても正答とみなされます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 3 \times 10^4
  • 1 \le N \le 3 \times 10^5
  • N-1 \le M \le 3 \times 10^5
  • 1 \le U_i < V_i \le N
  • i \neq j ならば (U_i,V_i) \neq (U_j,V_j)
  • 与えられるグラフは連結
  • ひとつの入力における N の総和は 3 \times 10^5 以下
  • ひとつの入力における M の総和は 3 \times 10^5 以下
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。ここで \mathrm{case}_i は i 個目のテストケースを意味する。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

T 行出力せよ。i 行目には i 個目のテストケースの答えを出力せよ。

各テストケースについて、条件を満たす整数列 A を以下の形式で出力せよ。

A_1 A_2 \dots A_N

入力例 1

3
6 7
1 5
1 3
3 5
2 5
3 4
3 6
4 6
1 0
6 10
4 6
1 4
2 5
3 6
1 3
1 2
2 3
2 4
3 4
3 5

出力例 1

0 2 1 2 1 2
0
0 3 2 1 3 3

この入力には 3 個のテストケースが含まれています。

1 個目のテストケースについて、A=(0,2,1,2,1,2) とすることを考えます。

  • 頂点 1 について、A_1=0 です。
  • 頂点 2 について、A_w=A_2-1 を満たす隣接頂点 w は頂点 5 のただ 1 つです。
  • 頂点 3 について、A_w=A_3-1 を満たす隣接頂点 w は頂点 1 のただ 1 つです。
  • 頂点 4 について、A_w=A_4-1 を満たす隣接頂点 w は頂点 3 のただ 1 つです。
  • 頂点 5 について、A_w=A_5-1 を満たす隣接頂点 w は頂点 1 のただ 1 つです。
  • 頂点 6 について、A_w=A_6-1 を満たす隣接頂点 w は頂点 3 のただ 1 つです。

以上より、この整数列 A は問題文中の条件を満たします。

他にも、A=(0,3,1,2,2,2) としても条件を満たすため、0 3 1 2 2 2 という出力も正答とみなされます。

下図は、出力例の各テストケースについて、各頂点の外側に頂点番号 v、内側に A_v を示したものです。

Score : 500 points

Problem Statement

You are given a connected simple undirected graph with N vertices and M edges. The vertices are numbered 1,2,\ldots,N, and the i-th edge connects vertices U_i and V_i.

Construct one integer sequence A=(A_1,A_2,\ldots,A_N) satisfying all of the following conditions.

  • 0 \le A_v \le N for every vertex v.
  • A_1=0.
  • For every vertex v other than vertex 1, there is exactly one vertex w adjacent to v satisfying A_w=A_v-1.

It can be proved that under the constraints of this problem, there exists at least one integer sequence satisfying all of the above conditions. If there are multiple integer sequences satisfying the conditions, any of them will be accepted.

T test cases are given; solve each of them.

Constraints

  • 1 \le T \le 3 \times 10^4
  • 1 \le N \le 3 \times 10^5
  • N-1 \le M \le 3 \times 10^5
  • 1 \le U_i < V_i \le N
  • (U_i,V_i) \neq (U_j,V_j) if i \neq j.
  • The given graph is connected.
  • The sum of N in each input is at most 3 \times 10^5.
  • The sum of M in each input is at most 3 \times 10^5.
  • All input values are integers.

Input

The input is given from Standard Input in the following format, where \mathrm{case}_i denotes the i-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Output T lines. The i-th line should contain the answer for the i-th test case.

For each test case, output an integer sequence A satisfying the conditions in the following format:

A_1 A_2 \dots A_N

Sample Input 1

3
6 7
1 5
1 3
3 5
2 5
3 4
3 6
4 6
1 0
6 10
4 6
1 4
2 5
3 6
1 3
1 2
2 3
2 4
3 4
3 5

Sample Output 1

0 2 1 2 1 2
0
0 3 2 1 3 3

This input contains three test cases.

For the first test case, consider setting A=(0,2,1,2,1,2).

  • For vertex 1, A_1=0.
  • For vertex 2, there is only one adjacent vertex w satisfying A_w=A_2-1, which is vertex 5.
  • For vertex 3, there is only one adjacent vertex w satisfying A_w=A_3-1, which is vertex 1.
  • For vertex 4, there is only one adjacent vertex w satisfying A_w=A_4-1, which is vertex 3.
  • For vertex 5, there is only one adjacent vertex w satisfying A_w=A_5-1, which is vertex 1.
  • For vertex 6, there is only one adjacent vertex w satisfying A_w=A_6-1, which is vertex 3.

Thus, this integer sequence A satisfies the conditions in the problem statement.

Additionally, setting A=(0,3,1,2,2,2) also satisfies the conditions, so the output 0 3 1 2 2 2 is also accepted.

The figure below shows, for each test case in the sample output, the vertex number v outside each vertex and A_v inside each vertex.