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à sẽ có tổng cộng \(m\) con đường.

Một thành phần là một nhóm các thành phố mà trong đó có một tuyến đường giữa hai thành phố bất kỳ sử dụng các con đường đã được xây dựng. Sau mỗi ngày, nhiệm vụ của bạn là tìm ra số lượng thành phần và kích thước của thành phần lớn nhất.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và đường. Các thành phố được đánh số \(1,2,\ldots,n\).
• Sau đó, có \(m\) dòng mô tả các con đường mới. Mỗi dòng có hai số nguyên \(a\) và \(b\): một con đường mới được xây dựng giữa các thành phố \(a\) và \(b\).
• Bạn có thể giả định rằng tất cả con đường sẽ được xây dựng giữa hai thành phố khác nhau.

Output

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

Constraints

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

Example

Sample input

5 3
1 2
1 3
4 5

Sample output

4 2
3 3
2 3