Q10959: The Party, Part I

Don Giovanni 喜歡跳舞，有天他開了一場舞會，邀請很多人一起來跳舞，大家都覺得能和主人(Don Giovanni)一起跳舞是一見榮幸的事，所以他們創造了一個名詞叫Don Giovanni number， Don Giovanni number 的計算方法如下：

1. 沒有人的 Don Giovanni number 是負的
2. Don Giovanni 自己的 Don Giovanni number 是 0
3. 和 Don Giovanni 跳過舞的人他們的 Don Giovanni number 是 1 ，和 Don Giovanni number 是 n 的人跳過舞且沒有和 Don Giovanni number 比 n 小的人跳過舞的人，他們的 Don Giovanni number 是 n+1
4. 如果有人一直沒有和有 Don Giovanni number 的人跳舞，則他的 Don Giovanni number 是無限大，但是題目保證不會產生這種情形

你的工作是要確定每一個人的 Don Giovanni number

Input

輸入的第一列會有一個正整數，代表以下有幾組測試資料。接下來空一列，並且各組測試資料間也空一列。

每一組測試資料的第一列會有兩個數，P和D，P是這場舞會中有幾個人(每個人有一個編號從0到P-1，Don Giovanni 的編號是0)，D是有幾對跳舞的人(P<=1000，D<P(P-1)/2)，然後以下D列每列會有兩個數，代表跳舞的兩人的編號。

請參考Sample Input。

Output

輸出 1 號到 P-1 號的 Don Giovanni number，每個數字一列（請注意：你不需要輸出 Don Giovanni 的 Don Giovanni number）

每兩組測試資料間也請空一行。請參考 Sample Output。

2

5 6
0 1
0 2
3 2
2 4
4 3
1 2

5 5
1 2
0 1
2 3
3 4
0 4
   

1
1
2
2

1
2
2
1