Tỷ phú mới về hưu được mệnh danh là “ngài Drone” vì ông sở hữu rất nhiều drone khác nhau, ông còn xây dựng một tòa nhà lớn để chứa drone và xem chúng như thú cưng của mình. Mỗi ngày ông thường chơi đùa với các drone, thích thú nhìn chúng bay qua bay lại trên bầu trời, sử dụng chúng để chụp hình phong cảnh. Tuy nhiên việc quản lý nhiều drone không đơn giản nên ông đã tự xây dựng một chương trình để theo dõi và điều khiển các drone.

Trong chương trình, các drone được đánh số thứ tự từ 1 đến ~ n ~. Ban đầu, tất cả drone được bay tự do và mỗi drone được xem là một nhóm. Khi ông dùng lệnh dạng ~ (x,y) ~ thì nhóm chứa drone thứ ~ x ~ và nhóm chứa drone thứ ~ y ~ sẽ gộp lại thành một nhóm lớn hơn. Nếu drone ~ x ~ và drone ~ y ~ đã ở trong một nhóm thì không cần thực hiện lệnh gộp nhóm.

Yêu cầu: Cho ~ q ~ lệnh, mỗi lệnh có dạng ~ (x,y) ~, hãy cho biết sau mỗi lệnh như vậy thì chênh lệch số lượng nhỏ nhất giữa hai nhóm drone là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương ~ n,q ~ ~ (1 ≤ n, q ≤ 10^5) ~
• ~ q ~ dòng tiếp theo, dòng thứ ~ i ~ ghi 2 số ~ x_i, y_i ~ ~ (1 ≤ x_i, y_i ≤ n ) ~ cho biết một lệnh.

Kết quả

Gồm ~ q ~ dòng, dòng thứ ~ i ~ cho biết chênh lệch số lượng nhỏ nhất giữa hai nhóm drone sau khi thực hiện lệnh thứ ~ i ~, nếu tất cả drone đã gộp thành 1 nhóm thì ghi 0.

Ràng buộc

• Có 50% số test có ~ 1 ≤ n, q ≤ 2000 ~
• 50% số test còn lại có ~ 2000 < n, q ≤ 10^5 ~

Ví dụ:

Input 1

4 5
1 2
2 3
1 3
3 4
1 4 

Output 1

0
2
2
0
0