Đuổi Bắt Cảnh Sát

Tên cướp đang ở ngã tư $1$ (ngân hàng) và cần chạy trốn đến ngã tư $n$ (cảng). Cảnh sát muốn chặn tối thiểu số con đường để ngăn tên cướp đến đích. Hãy tìm số con đường tối thiểu cần chặn và liệt kê các con đường đó.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — con đường hai chiều giữa $a$ và $b$.

Dữ liệu ra

• Dòng 1: số nguyên $k$ — số con đường cần chặn.
• $k$ dòng tiếp theo: mỗi dòng gồm hai số nguyên — hai đầu của con đường bị chặn.

Ràng buộc

• $2\le n\le 500$
• $1\le m\le 1000$
• Không có cạnh đa

Ví dụ