Colored Wizards - 2#1933
A fairytale country consists of several cities connected by two-way roads. From any city in the country, you can reach any other city, either directly or through other cities. There are no roads connecting a city to itself, and there is at most one road between any pair of distinct cities.
Yellow and blue wizards live in this country. When the yellow wizard travels along a road, he paints it yellow. When the blue wizard travels along a road, he paints it blue. If a blue-painted road is painted yellow (or a yellow-painted road is painted blue), the colors mix, and the road turns green—the least favorite color of both wizards.
This year, a wizard conference is held in the capital (city ). Both yellow and blue wizards want to reach the capital and wish to know the minimal number of roads that must be painted green for both to arrive at the capital. Initially, all roads are unpainted.
The initial positions of the yellow and blue wizards are not known in advance, so you must answer this question for possible starting scenarios.
The first line contains two integers (1 \le n \le 10^5) and (1 \le m \le 500\,000) — the number of cities and roads.
The second line contains an integer (1 \le F \le n) — the number of the capital city.
Each of the next lines contains two integers a_i and b_i (1 \le a_i, b_i \le n), indicating a road between cities a_i and b_i.
The next line contains an integer (1 \le k \le 10^5) — the number of possible initial wizard placements.
Each of the following lines contains two integers — the cities where the yellow and blue wizards initially are.
For each of the scenarios, output the minimal number of roads that must be painted green so that both wizards can reach the capital.
Example 1