Mô tả bài toán: Số lượng thành phần liên thông

Có n thành phố và ban đầu không có con đường nào giữa chúng. Tuy nhiên, mỗi ngày một con đường mới sẽ được xây dựng, với tổng cộng m con đường.

Một thành phần liên thông là một nhóm các thành phố trong đó luôn có một đường đi giữa bất kỳ cặp thành phố nào trong nhóm.

Nhiệm vụ của bạn là:

• Sau mỗi ngày, xác định số lượng thành phần liên thông.
• Tìm kích thước của thành phần lớn nhất.

Input:

• 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.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~: biểu diễn rằng một con đường mới được xây dựng giữa thành phố ~a~ và ~b~.

Output:

• In ra ~m~ dòng, mỗi dòng chứa hai số nguyên:
  • Số lượng thành phần liên thông.
  • Kích thước của thành phần lớn nhất.

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ác thành phố được kết nối là: {1, 2}, {3}, {4}, {5}.
  • Số thành phần liên thông là ~4~, kích thước thành phần lớn nhất là ~2~.
• Sau ngày thứ hai:
  • Các thành phố được kết nối là: {1, 2, 3}, {4}, {5}.
  • Số thành phần liên thông là ~3~, kích thước thành phần lớn nhất là ~3~.
• Sau ngày thứ ba:
  • Các thành phố được kết nối là: {1, 2, 3}, {4, 5}.
  • Số thành phần liên thông là ~2~, kích thước thành phần lớn nhất là ~3~.