P1656 Bomb the Railways

Country A dispatches General uim to take strategic measures against Country B to rescue the suffering people. Country B has $n$ cities connected by railways. Any two cities can be reached directly or indirectly via railways. uim discovers that if a certain railway is destroyed, there will be a pair of cities that can no longer reach each other by railway. Such a railway is called a "key road." To quickly paralyze the country's logistics system, uim hopes to blow up railways so that there exists a pair of cities that cannot reach each other. However, there is only one shell (Country A's parliament will not fund more). So, which single railway can he bomb?

The first line contains $n, m\ (1 \leq n \leq 150,\ 1 \leq m \leq 5000)$, representing that there are $n$ cities and a total of $m$ railways. The following $m$ lines each contain two integers $a, b$, indicating that city $a$ and city $b$ are directly connected by a railway.

Output several lines. Each line contains two numbers $a, b$, with $a < b$, indicating that $\lang a,b\rang$ is a key road. Please note: In the output, all pairs $\lang a,b\rang$ must be sorted by increasing $a$; if $a$ is the same, then sort by increasing $b$.

Translated by ChatGPT 5