Nhật ký mở rộng hạ tầng

Bối cảnh và bài toán

Một hệ thống hạ tầng có n trạm, ban đầu chưa có tuyến kết nối nào. Mỗi ngày một tuyến mới được kích hoạt giữa hai trạm. Sau từng ngày, bộ phận giám sát cần biết hệ thống hiện chia thành bao nhiêu cụm độc lập và cụm lớn nhất đang có bao nhiêu trạm.

Dữ liệu đến theo dòng thời gian và không có thao tác gỡ bỏ tuyến.

Yêu cầu

Sau mỗi tuyến mới, in số cụm liên thông hiện tại và kích thước cụm lớn nhất.

Input

• Dòng 1 chứa n m.
• m dòng tiếp theo, dòng thứ i chứa hai trạm a b được kết nối ở ngày i.

Output

In m dòng. Mỗi dòng gồm hai số: số component hiện tại và kích thước component lớn nhất sau khi thêm tuyến tương ứng.

Ràng buộc

• 2 <= n <= 10^5
• 1 <= m <= 2 * 10^5
• 1 <= a, b <= n, a != b

Chấm điểm

Ví dụ 1

Input

5 3
1 2
1 3
4 5

Output

4 2
3 3
2 3

Giải thích. Sau ba ngày, các component lần lượt biến đổi từ 5 cụm đơn lẻ thành {1,2,3} và {4,5}.

Ví dụ 2

Input

3 3
1 2
2 3
1 3

Output

2 2
1 3
1 3

Giải thích. Tuyến cuối nối hai trạm vốn đã cùng component nên không đổi số cụm hay kích thước lớn nhất.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Road Construction (Task 1676).