Di chuyển robot

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 (mỗi robot tới một đầu, robot nào tới đầu nào cũng được). 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.

Cụ thể, trong mỗi đơn vị thời gian, mỗi robot bắt buộc phải đi hết đúng một đoạn đường ống nối với trạm nó đang đứng (không được đứng chờ). Robot được đi qua một trạm hay một đoạn ống nhiều lần, được quay ngược lại đoạn ống vừa đi, và hai robot có thể cùng ở một trạm. Thời gian tập kết là số $T\ge 0$ nhỏ nhất sao cho sau đúng $T$ đơn vị thời gian, hai robot đứng ở hai đầu của đoạn đường trục. Nếu ngay từ đầu robot thứ nhất và robot thứ hai đã đứng ở hai đầu của đoạn đường trục (đoạn đường trục nối trạm $1$ với trạm $N$) thì $T=0$.

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.

Dữ liệu vào

• Dòng đầu chứa hai 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$ ($1\le u_i,v_i\le N$, $u_i\ne 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).

Dữ liệu ra

• Dòng đầu ghi 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$.

Ràng buộc

• $2\le N\le {10}^5$, $N-1\le M\le {10}^6$.
• Hệ thống liên thông, không có hai đoạn đường ống nối cùng một cặp trạm và có ít nhất một đoạn đường trục.

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$.

Ví dụ