Colored Wizards#188
A fairy-tale country consists of cities connected by bidirectional roads. Any city can be reached from any other, either directly or via other cities. There are no roads connecting a city to itself, and there is at most one road between any two distinct cities.
Yellow and blue wizards live in this country. When a yellow wizard travels along a road, they paint it yellow; a blue wizard paints a road blue. If a wizard travels along a road already painted by the other wizard (yellow on blue or blue on yellow), the colors mix and the road becomes green — the least favorite color of both wizards. Initially, all roads are unpainted.
This year, a wizard conference is being held in the capital (city ). The yellow and blue wizards wish to know, for each possible pair of starting cities, the minimum number of roads that must inevitably be painted green as both wizards travel to the capital. Their starting cities are not fixed in advance.
Therefore, for given pairs of starting cities (one for the yellow wizard, one for the blue), find the answer for each such pair.
The first line contains two integers: (1 \leq n \leq 10^5) and (1 \leq m \leq 500\,000) — the number of cities and roads.
The second line contains a single integer (1 \leq F \leq n) — the number of the capital city.
Each of the next lines contains two integers a_i and b_i (1 \leq a_i, b_i \leq n), indicating that there is a road between cities a_i and b_i.
The next line contains an integer (1 \leq k \leq 10^5) — the number of wizard starting pairs.
Each of the following lines contains two integers — the starting cities of the yellow and blue wizards, respectively.
For each of the cases, output a single integer — the minimum number of roads that will inevitably become green if both wizards, starting from their respective cities, reach the capital.
Example 1