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: từ tệp GROUPD.INP

+ Dòng đầu tiên ghi hai số nguyên dương \(n,\ q\ (1 \leq n,\ q \leq 10^{5})\)

+ \(q\) dòng tiếp theo, dòng thứ \(i\) ghi 2 số \(x_{i},\ y_{i}\ (1 \leq x_{i},y_{i} \leq n)\) cho biết một lệnh.

Kết quả: ghi vào tệp GROUPD.OUT 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.

Ví dụ:

Giải thích:

+ Lệnh (1, 2): có các nhóm: (1, 2); (3); (4); nên độ chênh lệch nhỏ nhất là 0

+ Lệnh (2, 3): có các nhóm: (1, 2, 3); (4); nên độ chênh lệch nhỏ nhất là 2

+ Lệnh(1, 3): không thực hiện gộp nhóm vì 1 và 3 đã thuộc một nhóm. Độ chênh lệch nhỏ nhất là 2

+ Lệnh (3, 4): chỉ có nhóm: (1, 2, 3, 4 ) nên kết quả là 0

+ Lệnh (1, 4): không thực hiện gộp nhóm vì 1 và 4 đã thuộc một nhóm. Độ chênh lệch nhỏ nhất là 0

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(1 \leq n,q \leq 2000\)

+ 50% số test còn lại tương ứng 50% số điểm có \(2000 < n,q \leq 10^{5}\)