Có \(n\) thành phố và \(m\) chuyến bay liên thông giữa chúng. Nhiệm vụ của bạn là thêm các chuyến bay mới để có thể đi từ bất kì thành phố này đến bất kì thành phố khác. Số lượng chuyến bay mới tối thiểu cần thiết là bao nhiêu?

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{5}, 1 \leq m \leq 2 \times 10^{5})\) - số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1, 2, \ldots n\).
• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả chuyến bay đều là chuyến bay một chiều.

Output

• Đầu tiên in một số nguyên \(k\): số lượng cần thiết của các chuyến bay mới. Sau đó, in \(k\) dòng mô tả các chuyến bay mới. Bạn có thể in bất kì giải pháp hợp lệ nào.

Example

4 5  
1 2  
2 3  
3 1  
1 4  
3 4

1  
4 2