Xây dựng đường

Trong một chuyến đi khám phá thiên nhiên, FullHouse Dev đã đến thăm một vùng đất mới với nhiều thành phố nhưng chưa có đường giao thông. Họ được giao nhiệm vụ theo dõi quá trình xây dựng đường và phân tích sự kết nối giữa các thành phố.

Bài toán

Ban đầu có \(n\) thành phố và không có đường nối giữa chúng. Mỗi ngày, một con đường mới sẽ được xây dựng, và tổng cộng sẽ có \(m\) con đường. Một thành phần liên thông là một nhóm các thành phố mà từ thành phố này có thể đi đến bất kỳ thành phố nào khác trong nhóm bằng các con đường hiện có. Sau mỗi ngày, nhiệm vụ của bạn là tìm số lượng thành phần liên thông và kích thước của thành phần liên thông lớn nhất.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng thành phố và số lượng con đường. Các thành phố được đánh số từ \(1,2,\dots,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): một con đường mới được xây dựng giữa thành phố \(a\) và thành phố \(b\).
• Mỗi con đường sẽ được xây dựng giữa hai thành phố khác nhau.

OUTPUT FORMAT:

• In ra \(m\) dòng: thông tin yêu cầu sau mỗi ngày.

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

5 3
1 2
1 3
4 5

OUTPUT

4 2
3 3
2 3

Giải thích

• Sau ngày đầu tiên: có 4 thành phần liên thông (thành phố 1 và 2 kết nối với nhau, các thành phố 3, 4, và 5 riêng lẻ), và thành phần lớn nhất có kích thước 2.
• Sau ngày thứ hai: có 3 thành phần liên thông (thành phố 1, 2, và 3 kết nối với nhau, thành phố 4 và 5 riêng lẻ), và thành phần lớn nhất có kích thước 3.
• Sau ngày thứ ba: có 2 thành phần liên thông (thành phố 1, 2, và 3 kết nối với nhau, thành phố 4 và 5 kết nối với nhau), và thành phần lớn nhất có kích thước 3.