Có \(𝑛\) 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 \(𝑚\) 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.

Yêu cầu: Sau mỗi ngày, 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.

Dữ liệu vào

• 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,…,𝑛\).

• \(𝑚\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) mô tả một con đường mới được xây dựng giữa các thành phố \(u\) và \(v\).

Giả định rằng tất cả con đường sẽ được xây dựng giữa hai thành phố khác nhau.

Kết quả ra

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

Ràng buộc:

\(1 ≤ n ≤ 10^5; 1 ≤ m ≤ 2*10^5 ; 1 ≤ a,b ≤ n \)

Sample Input

5 3 
1 2 
1 3 
4 5

Sample Output

4 2 
3 3 
2 3