Mạng Đường Đang Mở Rộng

Có $n$ địa điểm, ban đầu mỗi địa điểm là một thành phần riêng. Sau đó $m$ tuyến đường hai chiều được mở lần lượt. Ngay sau mỗi tuyến đường, cần biết mạng hiện có bao nhiêu thành phần liên thông và thành phần lớn nhất chứa bao nhiêu địa điểm.

Một tuyến đường có thể nối hai địa điểm vốn đã đi tới nhau; khi đó cấu trúc các thành phần không thay đổi.

Input

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Mỗi trong $m$ dòng tiếp theo chứa hai số nguyên $a$ và $b$, mô tả tuyến đường được mở tiếp theo giữa hai địa điểm khác nhau.

Output

• Sau mỗi tuyến đường, in một dòng gồm hai số: số thành phần liên thông hiện tại và kích thước của thành phần lớn nhất.

Constraints

• $1\le n\le 10^5$.
• $1\le m\le 2\cdot 10^5$.
• $1\le a,b\le n$ và $a$ khác $b$; một cạnh mới có thể nằm trong thành phần đã liên thông.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 30$ và $m\le 80$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

5 2
4 2
3 4
3 4
2 4