Hotspot

문제

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

This country has $kk$ citizens. Interestingly, the home and office of the $ii$th citizen are located in different towns $A_{i}A\_i$ and $B_{i}B\_i$, respectively. Hence, every day, the $ii$th citizen moves back and forth between two fixed towns $A_{i}A\_i$ and $B_{i}B\_i$ (since the $ii$th citizen needs to work).

To save time, the $ii$th citizen will choose a path with the shortest length. If there are several shortest paths between $A_{i}A\_i$ and $B_{i}B\_i$, the $ii$th citizen chooses by random one shortest path which Donald does not know. The expected chance that the $ii$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 $ww$ that maximizes ${\sum }_{i=0}^{k-1}{E}_i(w)\backslash sum\_\{i=0\}^\{k-1\}\{E\_i(w)\}$.

Your task is to help Donald identify the town $ww$. When there are multiple towns $ww$ that maximize ${\sum }_{i=0}^{k-1}{E}_i(w)\backslash 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}2^\{15\}$. Note that double-precision floating-point is required for this problem.

Example 1: Suppose $k=1k\; =\; 1$ where $(A_0,B_0)=(4,10)(A\_0,\; B\_0)\; =\; (4,\; 10)$. Then, there is exactly one shortest path of length $22$, which is $(4,7,10)(4,\; 7,\; 10)$. Donald can build the meeting office in either town $44$, town $77$, or town $1010$.

Example 2: Suppose $k=2k\; =\; 2$ where $(A_0,B_0)=(4,10)(A\_0,\; B\_0)\; =\; (4,\; 10)$ and $(A_1,B_1)=(3,8)(A\_1,\; B\_1)\; =\; (3,\; 8)$. Then, there is exactly one shortest path between town $44$ and town $1010$ of length $22$, which is $(4,7,10)(4,\; 7,\; 10)$. Also, there is exactly one shortest path between town $33$ and town $88$ of length $33$, which is $(3,7,11,8)(3,\; 7,\; 11,\; 8)$. If Donald builds the meeting office in town $77$, the expected number of citizens passing through town $77$ is $22$.

Example 3: Suppose $k=2k\; =\; 2$ where $(A_0,B_0)=(1,13)(A\_0,\; B\_0)\; =\; (1,\; 13)$ and $(A_1,B_1)=(6,2)(A\_1,\; B\_1)\; =\; (6,\; 2)$. Then, we have: (1) $1010$ shortest paths of lenght $44$ between town $11$ and town $1313$. (2) 3 shotest paths of lenght $33$ between town $66$ and town $22$. If Donald builds the meeting office in town $77$, we have: (1) For the 0th citizen, $99$ shortest paths between town $11$ and town $1313$ passing through town $7.(2)Forthe1stcitizen,7.\; (2)\; For\; the\; 1st\; citizen,$2$shortestpathsbetweentown6andshortest\; paths\; between\; town\; 6\; and$town $22$ passing through town $77$. Then, the expected number of citizens passing through town 7 is $E_0(7)+E_1(7)=9\mathrm{/}10+2\mathrm{/}3=1.567E\_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 $77$.

입력

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

Afterwards, the next line contains an integer $kk$, which denotes the number of citizens. It is followed by $kk$ lines. The $ii$th line stores two integers $A_{i}A\_i$ and $B_{i}B\_i$, for $i=0,\mathrm{.}\mathrm{.}\mathrm{.},k-1i\; =\; 0,\; .\; .\; .\; ,\; k\; -\; 1$.

출력

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