Cải cách du lịch

Cho một đồ thị vô hướng liên thông gồm $n$ đỉnh và $m$ cạnh. Đồ thị không có cạnh kép (không có hai cạnh nối cùng một cặp đỉnh) và không có khuyên.

Bạn cần định hướng mỗi cạnh theo một trong hai chiều, biến đồ thị thành đồ thị có hướng. Sau khi định hướng, với mỗi đỉnh $i$, gọi $r_i$ là số đỉnh $x$ mà tồn tại đường đi có hướng từ $i$ tới $x$ (kể cả chính $i$).

Hãy chọn cách định hướng sao cho giá trị ${min}_{1\le i\le n}{r}_i$ đạt giá trị lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số đỉnh và số cạnh.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_j$ và $v_j$ ($1\le u_j,v_j\le n$, $u_j\ne v_j$), mô tả một cạnh vô hướng nối hai đỉnh $u_j$ và $v_j$.

Dữ liệu ra

• Dòng đầu in ra một số nguyên — giá trị ${min}_i{r}_i$ lớn nhất có thể đạt được.
• $m$ dòng tiếp theo, mỗi dòng in ra hai số nguyên $u_j$ và $v_j$, có nghĩa cạnh thứ $j$ trong dữ liệu vào được định hướng từ $u_j$ tới $v_j$. Các cạnh phải được in theo đúng thứ tự xuất hiện trong dữ liệu vào.

Nếu có nhiều cách định hướng tối ưu, in ra một cách bất kỳ.

Ràng buộc

• $2\le n\le 400000$
• $1\le m\le 400000$
• Đồ thị liên thông, không có cạnh kép, không có khuyên.

Ví dụ