Byteland có ~n~ thành phố và ~m~ con đường nối giữa chúng. Mục tiêu là xây dựng thêm một số con đường mới sao cho mọi cặp thành phố đều có thể đi đến nhau (tức là đồ thị trở nên liên thông).

Nhiệm vụ của bạn là xác định số lượng tối thiểu các con đường cần xây thêm và liệu kê những con đường này.

Dữ liệu vào:

• 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 hiện có.
• Sau đó có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~ — cho biết có một con đường giữa hai thành phố đó.

Mỗi con đường nối hai thành phố khác nhau, và không có hai con đường nào trùng nhau.

Dữ liệu ra:

• In ra một số nguyên ~k~: số lượng con đường cần xây thêm.
• Sau đó in ra ~k~ dòng, mỗi dòng chứa hai số nguyên mô tả các con đường mới.

Có thể in ra bất kỳ lời giải hợp lệ nào.

Input:

4 2
1 2
3 4

Output:

1
2 3

Giới hạn:

• ~1\leq n\leq 10^5~
• ~1\leq m\leq 2\times 10^5~
• ~1\leq a, b\leq n~