P5058 [ZJOI2004] Sniffer

In an information warfare exercise, the Red side successfully broke into the Blue side’s internal network. The Blue side has two information centers. The Red side plans to install a sniffer on some intermediate server so that it can listen to all information exchanged between the two information centers. However, the Blue side’s network is very large, and packets can travel from one information center to the other through more than one path. Now you need to solve this problem as quickly as possible: on which intermediate server should the sniffer be installed to ensure that all packets can be captured?

The first line contains an integer $n$, which is the number of servers in the Blue side’s network. The next several lines describe the network topology. Each line contains two integers $i, j$, meaning there is a bidirectional connection between server $i$ and server $j$. Server IDs start from $1$. A line with two $0$ indicates the end of the topology description. After that, there are two integers $a, b$, which are the IDs of the two center servers.

Output the ID of a server that satisfies the requirement. If there are multiple solutions, output the one with the smallest ID. If no solution can be found, output `No solution`.

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, and the number of edges does not exceed $5 \times 10^5$. Translated by ChatGPT 5