Cho đồ thị vô hướng gồm N đỉnh (ban đầu không có cạnh nào). Sau mỗi lần thêm một cạnh mới, hãy in ra số thành phần liên thông hiện tại của đồ thị.

Hai đỉnh thuộc cùng thành phần liên thông nếu có đường đi giữa chúng.

Đầu vào

• Dòng đầu chứa hai số nguyên N (1 ≤ N ≤ 10^5) và M (1 ≤ M ≤ 10^5).
• M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v — cạnh được thêm.

Đầu ra

In ra M dòng, dòng thứ i là số thành phần liên thông sau khi thêm cạnh thứ i.

Ví dụ

Input:
6 5
1 2
3 4
1 3
5 6
4 5

Output:
5
4
3
2
1