著名的「六度分隔理論」這麼告訴我們：「你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過六個人你就能夠認識任何一個陌生人。」
紅線對這個理論非常有興趣，想要設計一個實驗來驗證，他邀請了很多人來參與這個實驗，並且為每一個人計算Redline distance，也就是每個人與紅線的距離，計算方式如下：
1. 沒有人的Redline distance是負的。
2. 紅線自己的Redline distance是0。
3. 若有一個人(紅線除外)，在他的朋友中最小的Redline distance是n，則他的Redline distance是n + 1。
4. 沒辦法連結到紅線的人，其Redline distance是無限大，但是題目保證不會產生這種情形。
但是因為人數實在太多了，麻煩你寫一個程式幫紅線計算所有人的Redline distance。
輸入的第一列會有一個正整數，代表以下有幾組測試資料。接下來空一列，並且各組測試資料間也空一列。
每一組測試資料的第一列會有兩個數，P和D，P是這場實驗中有幾個人(每個人有一個編號從0到P-1，紅線的編號是0)，D是有幾對互相認識的朋友(P <= 1000，D < P(P-1) / 2)，然後以下D列每列會有兩個數，一對朋友兩人的編號。
每組測資P-1列，輸出1號到P-1號的Redline distance，每個數字一列。
（注意：你不需要輸出紅線的Redline distance）
請在每兩組測試資料間空一行。