Chốt Chặn Tối Thiểu

Một thành phố có $n$ giao lộ và $m$ con phố hai chiều. Trung tâm điều phối ở giao lộ $1$, còn điểm cần cô lập ở giao lộ $n$.

Hãy đóng ít phố nhất sao cho sau khi đóng, không còn bất kỳ đường đi nào giữa hai giao lộ trên. Bạn phải xuất cả số lượng nhỏ nhất và một tập phố đạt được số lượng đó. Hai đầu mút của một phố có thể được in theo bất kỳ thứ tự nào; mỗi phố chỉ được liệt kê một lần.

Input

• Dòng đầu chứa hai số nguyên $n,m$.
• Mỗi trong $m$ dòng tiếp theo chứa hai số nguyên $a,b$, cho biết có một phố hai chiều nối $a$ và $b$. Mỗi cặp giao lộ xuất hiện nhiều nhất một lần.

Output

• Dòng đầu in số nguyên $k$: số phố nhỏ nhất cần đóng.
• Tiếp theo in đúng $k$ dòng, mỗi dòng chứa hai đầu mút của một phố cần đóng. Có thể in bất kỳ phương án tối ưu nào.

Constraints

• $2\le n\le 500$.
• $1\le m\le 1000$.
• $1\le a,b\le n$.
• Mỗi cặp giao lộ có nhiều nhất một phố.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10$ và $m\le 16$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

2
1 2
1 3