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

Thành phần liên thông là một nhóm các thành phố mà giữa hai thành phố bất kỳ trong thành phần liên thông đều có đường đi.

Sau mỗi ngày, nhiệm vụ của bạn là tìm số thành phần liên thông và kích thước của thành phần liên thông lớn nhất lớn nhất.

Input

Dòng đầu tiên chứa hai số nguyên n và m: số thành phố và số đường. Các thành phố được đánh số 1,2,~\dots~,n.

Tiếp theo là m dòng mô tả những con đường mới. Mỗi dòng có hai số nguyên u và v: một con đường hai chiều mới được xây dựng giữa thành phố u và v.

Output

In m dòng: số thành phần liên thông và kích thước của thành phần liên thông lớn nhất lớn nhất của m ngày

Hạn chế

~1 \le n \le 10^5~

~1 \le m \le 2 \cdot 10^5~

~1 \le u, v \le n~

Examples

Input

5 3
1 2
1 3
4 5

Output

4 2
3 3
2 3