19706번 - Hotspot 스페셜 저지다국어

문제

Consider a country with $n$ towns. The towns are connected by $m$ roads, all with the same length. (See Figure 2 for an example.)

This country has $k$ citizens. Interestingly, the home and office of the $i$th citizen are located in different towns $A_i$ and $B_i,ドル respectively. Hence, every day, the $i$th citizen moves back and forth between two fixed towns $A_i$ and $B_i$ (since the $i$th citizen needs to work).

To save time, the $i$th citizen will choose a path with the shortest length. If there are several shortest paths between $A_i$ and $B_i,ドル the $i$th citizen chooses by random one shortest path which Donald does not know. The expected chance that the $i$th citizen passing through town w equals

\[E_i(w) = \frac{\text{Number of shortest paths between }A_i\text{ and }B_i\text{ passing through town }w}{\text{Number of shortest paths between }A_i\text{ and }B_i}\]

Donald is the president of the country and he wants to understand the needs of his citizens. He wants to setup a meeting office in a town so that he can meet as many citizens as possible. Precisely, he aims to setup the meeting office in a town $w$ that maximizes $\sum_{i=0}^{k-1}{E_i(w)}$.

Your task is to help Donald identify the town $w$. When there are multiple towns $w$ that maximize $\sum_{i=0}^{k-1}{E_i(w)},ドル report any one of them. In addition, due to certain geological constraints during the construction of the towns and roads, it is found that the number of shortest paths between any two towns will not exceed 2ドル^{15}$. Note that double-precision floating-point is required for this problem.

Example 1: Suppose $k = 1$ where $(A_0, B_0) = (4, 10)$. Then, there is exactly one shortest path of length 2ドル,ドル which is $(4, 7, 10)$. Donald can build the meeting office in either town 4ドル,ドル town 7ドル,ドル or town 10ドル$.

Example 2: Suppose $k = 2$ where $(A_0, B_0) = (4, 10)$ and $(A_1, B_1) = (3, 8)$. Then, there is exactly one shortest path between town 4ドル$ and town 10ドル$ of length 2ドル,ドル which is $(4, 7, 10)$. Also, there is exactly one shortest path between town 3ドル$ and town 8ドル$ of length 3ドル,ドル which is $(3, 7, 11, 8)$. If Donald builds the meeting office in town 7ドル,ドル the expected number of citizens passing through town 7ドル$ is 2ドル$.

Example 3: Suppose $k = 2$ where $(A_0, B_0) = (1, 13)$ and $(A_1, B_1) = (6, 2)$. Then, we have: (1) 10ドル$ shortest paths of lenght 4ドル$ between town 1ドル$ and town 13ドル$. (2) 3 shotest paths of lenght 3ドル$ between town 6ドル$ and town 2ドル$. If Donald builds the meeting office in town 7ドル,ドル we have: (1) For the 0th citizen, 9ドル$ shortest paths between town 1ドル$ and town 13ドル$ passing through town 7ドル. (2) For the 1st citizen, 2ドル$ shortest paths between town 6 and $town 2ドル$ passing through town 7ドル$. Then, the expected number of citizens passing through town 7 is $E_0(7) + E_1(7) = 9/10 + 2/3 = 1.567$. In fact, this is the best solution. Donald needs to build the meeting office in town 7ドル$.

입력

The input will start with two integers $n$ and $m$ in a single line. $n$ denotes the number of towns while $m$ denotes the number of edges. Then, the next $m$ lines are the roads, each consisting of two integers representing the two towns connected by the road.

Afterwards, the next line contains an integer $k,ドル which denotes the number of citizens. It is followed by $k$ lines. The $i$th line stores two integers $A_i$ and $B_i,ドル for $i = 0, . . . , k - 1$.

출력

Output a single line with exactly one integer, representing the town $w$ that maximises $\sum_{i=0}^{k-1}{E_i(w)}$. When there are multiple possible towns, output any one of them.

제한

• n ≤ 5000
• m ≤ 40000
• k ≤ 2000

힌트