Hệ thống đường ống dẫn dầu có ~N~ trạm điều áp, đánh số từ ~1~ đến ~N~ và ~M~ đoạn đường ống, đánh số từ ~1~ đến ~M~, mỗi đoạn nối hai trạm điều áp. Hệ thống có tính liên thông, tức là giữa hai trạm điều áp bao giờ cũng có đường ống nối với nhau (trực tiếp hoặc qua các trạm khác). Một đoạn đường ống được gọi là trục nếu việc hỏng đoạn đường ống đó sẽ dẫn đến tình trạng hệ thống mất liên thông. Trong hệ thống mà chúng ta đang xét, có ít nhất một đoạn đường trục.

Do tính chất quan trọng của các đường trục nên chúng được ưu tiên trong công tác duy tu bảo dưỡng. Người ta chế tạo hai robot phục vụ việc kiểm tra đường trục, robot thứ nhất đặt ở trạm ~1~, robot thứ hai đặt ở trạm ~N~. Với mỗi đoạn đường trục, khi được lệnh kiểm tra, robot thứ nhất xuất phát từ trạm ~1~, robot thứ hai xuất phát từ trạm ~N~ và cùng bắt đầu di chuyển tới hai trạm là hai đầu của đoạn đường trục này. Hai robot luôn phải di chuyển và chỉ dừng lại khi cả hai cùng đến đích. Biết rằng, mỗi đơn vị thời gian robot đi được một đoạn đường ống. Thời gian tập kết để kiểm tra đoạn đường trục là thời gian nhỏ nhất để hai robot cùng đến được hai trạm là hai đầu của đoạn đường trục.

Yêu cầu: Cho hệ thống đường ống, hãy xác định thời gian tập kết tương ứng với từng đoạn đường trục.

Input

• Dòng đầu số nguyên ~N, M~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~ xác định đoạn đường ống thứ ~i~ nối hai trạm ~u_i, v_i~ (không có hai đoạn đường ống nào cùng nối hai trạm điều áp).

Output

• Dòng đầu số nguyên ~K~ là số đường trục có trong mạng.
• ~K~ dòng sau, mỗi dòng ghi hai số nguyên ~U, T~ trong đó ~U~ là số thứ tự của đoạn đường trục, ~T~ là thời gian tập kết của hai robot đến hai trạm là hai đầu của đoạn đường trục ~U~, nếu không có phương án di chuyển hai robot thì ~T = -1~. Các dòng được đưa ra theo trật tự tăng của ~U~.

Sample Input 1

4 3
1 2
2 3
3 4

Sample Output 1

3
1 2
2 1
3 2

Sample Input 2

7 8
1 2
1 3
1 4
2 3
4 5
4 7
5 6
6 7

Sample Output 1

1
3 3

Subtasks

• Các test ứng với 50% số điểm có ~2 \le N \le 100~.
• Các test còn lại ứng với 50% số điểm có ~2 \le N \le 10^5~ và ~N-1 \le M \le 10^6~.