RING

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: "$uv$" - 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.

Dữ liệu vào

• 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ó.

Dữ liệu ra

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$.

Ràng buộc

• $1\le N,M\le 3\times {10}^5$.
• $1\le u,v\le N$, $u\ne v$, không có hai truy vấn thêm cùng một cạnh.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N,M\le {10}^3$.
• Subtask 2 ($70\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ