AT_arc224_c [ARC224C] Ascending Labels

$ 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 $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。ここで $ \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 $

### Sample Explanation 1 この入力には $ 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 $ を示したものです。  ### 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 $ - $ i \neq j $ ならば $ (U_i,V_i) \neq (U_j,V_j) $ - 与えられるグラフは連結 - ひとつの入力における $ N $ の総和は $ 3 \times 10^5 $ 以下 - ひとつの入力における $ M $ の総和は $ 3 \times 10^5 $ 以下 - 入力はすべて整数