친구 네트워크

첫 줄에 사람의 수 n (2 이상 100000 이하) 과 친구 관계의 수 m (1 이상 4000 이하) 이 주어집니다. 이어서 m개의 줄에 두 사람 a b 가 친구가 됩니다.

친구 관계가 하나 생길 때마다, 그때 두 사람이 속한 친구 그룹의 크기(합쳐진 크기)를 한 줄에 하나씩 출력하세요. 이미 같은 그룹이면 그 그룹의 크기를 그대로 출력합니다.

예시

입력

5 4
1 2
2 3
4 5
1 5

출력

2
3
2
5