Câu lạc bộ Lập trình HaUI vừa kết nạp ~n~ thành viên mới, đánh số từ ~1~ đến ~n~; ban đầu chưa ai quen ai. Trong buổi giao lưu lần lượt diễn ra ~m~ sự kiện, sự kiện thứ ~i~ là "~u_i~ và ~v_i~ kết bạn với nhau".

Quan hệ quen biết có tính bắc cầu: hai thành viên thuộc cùng một nhóm khi và chỉ khi có thể đi từ người này tới người kia qua một chuỗi những người lần lượt là bạn của nhau. Tại mỗi thời điểm, ~n~ thành viên được chia thành các nhóm rời nhau; người chưa kết bạn với ai là một nhóm gồm ~1~ người.

Yêu cầu

Sau mỗi sự kiện, hãy cho biết số nhóm hiện có và số thành viên của nhóm đông nhất.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~;
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa hai số nguyên ~u_i~ và ~v_i~ mô tả sự kiện thứ ~i~, theo đúng thứ tự diễn ra.

Một cặp có thể xuất hiện nhiều lần và hai người đã cùng nhóm vẫn có thể kết bạn; khi đó các nhóm không thay đổi.

Kết quả ra

Ghi ra ~m~ dòng, dòng thứ ~i~ chứa hai số nguyên cách nhau bởi dấu cách: số nhóm và số thành viên của nhóm đông nhất ngay sau sự kiện thứ ~i~.

Ràng buộc

~2 \le n \le 2 \cdot 10^5~; ~1 \le m \le 2 \cdot 10^5~; ~1 \le u_i, v_i \le n~; ~u_i \ne v_i~.

• Subtask 1 (20% số điểm – test 01–04): ~n, m \le 100~;
• Subtask 2 (30% số điểm – test 05–10): ~n, m \le 2000~;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

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

Kết quả ra mẫu 1

5 2
4 2
4 2
3 4
3 4

Giải thích

Sau hai sự kiện đầu có ~4~ nhóm: ~\{1, 2\}~, ~\{3, 4\}~, ~\{5\}~, ~\{6\}~. Sự kiện thứ ba lặp lại cặp ~(1, 2)~ nên không có gì thay đổi. Sự kiện thứ tư gộp hai nhóm thành ~\{1, 2, 3, 4\}~: còn ~3~ nhóm, nhóm đông nhất có ~4~ người. Ở sự kiện thứ năm, ~2~ và ~3~ đã cùng nhóm (qua ~1~ và ~4~) nên kết quả giữ nguyên.