Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu không có cạnh nào.

Có ~M~ truy vấn, mỗi truy vấn có dạng như sau: "~u \ v~" - Thêm cạnh ~(u, v)~ vào đồ thị.

Một thành phần liên thông có dạng vòng là thành phần liên thông thỏa mãn mọi đỉnh đều kề với đúng ~2~ đỉnh khác.

Yêu cầu: Sau mỗi truy vấn, hãy đếm số thành phần liên thông có dạng vòng.

Input

• Dòng đầu tiên gồm ~2~ số nguyên ~N~ và ~M~ ~(1 \le N, M \le 3 \times 10^5)~.

• Mỗi dòng thứ ~i~ trong ~M~ dòng tiếp theo ghi ~2~ số nguyên ~u, v~ là cạnh được thêm vào trong truy vấn thứ ~i~ ~(1 \le u, v \le N)~.

Dữ liệu vào luôn đảm bảo không có cạnh trùng và cạnh nối một đỉnh với chính nó.

Output

Gồm ~M~ dòng, dòng thứ ~i~ là số thành phần liên thông có dạng vòng sau truy vấn thứ ~i~.

Scoring

Sample Input 1

4 4
1 2
2 3
3 1
3 4

Sample Output 1

0
0
1
0