ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ /8-р анги/

Газар дор тунель бүр нь ямар нэг 2 уулзвараар тодорхойлогдох М тунель, N уулзвар байв. Хулганы хаан уулзвар бүрийн тунель болгонд гэрлэн дохио байрлуулахаар шийджээ. Уулзварууд нь 1-ээс N хүртэл дугаарлагдсан бол уулзвар бүрт хэдэн гэрлэн дохио байрлуулах шаардлагатай вэ.

Input

Нэг мөрөнд зайгаар тусгаарлагдан N, M натурал тоонууд өгөгдөнө.

( 0<=N<=100, 0<=M<=N*(N-1)/2 )

Дараагийн M мөрөнд i, j дугаартай уулзваруудыг холбосон тунелийг тодорхойлох i, j тоонууд зайгаар тусгаарлагдан өгөгдөнө. ( 1<=i,j<=N )

Output

k дахь тоо нь k дахь уулзварт шаардагдах гэрлэн дохионы тоог илэрхийлэх N тоо нэг мөрөнд зайгаар тусгаарлагдан хэвлэгдэнэ.

Example

Intput:

7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
Output:
3 3 2 2 5 2 3