Cho đơn đồ thị vô hướng liên thông \(G\) gồm \(n\) đỉnh, \(m\) cạnh. Cần định chiều lại các cạnh của đồ thị thành một chiều, sao cho đồ thị mới vẫn liên thông và số lượng cạnh hai chiều còn lại là ít nhất có thể?

Dữ liệu vào

• Dòng đầu: hai số nguyên \(n\) và \(m\)
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u\) và \(v\) là cạnh nối đỉnh \(u\) và đỉnh \(v\)

Dữ liệu ra

• Nhiều dòng, mỗi dòng là \(1\) cạnh trong đồ thị mới.
• Lưu ý: In theo thứ tự sắp xếp tăng dần

Ràng buộc

• \(1 \le n \le 10^3\)
• \(0 \le m \le n(n-1)/2\)

Input 1

7 10
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
2 5
3 6

Output 1

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