Xây Dựng Đường

Có $n$ thành phố, ban đầu không có đường nối. Mỗi ngày, một tuyến đường mới được xây dựng nối hai thành phố. Sau mỗi ngày, hãy cho biết: số lượng thành phần liên thông và kích thước thành phần lớn nhất.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — tuyến đường xây dựng ngày đó.

Dữ liệu ra

In $m$ dòng, mỗi dòng gồm hai số nguyên: số thành phần liên thông và kích thước thành phần lớn nhất sau ngày tương ứng.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le a,b\le n$, $a\ne b$

Ví dụ