Colorful Wizards
In the fairyland, cities are interconnected by two-way roads. From any city, you can travel to any other city, either directly or via other cities. Notably, no road connects a city to itself, and there is at most one road between any two distinct cities.
In this land, there are two wizards: one yellow and one blue. When the yellow wizard travels a road, he paints it yellow, while the blue wizard paints it blue. If yellow paint is applied over blue, or vice versa, the resulting color is green, which both wizards dislike.
This year, a wizard conference is taking place in the capital city (city f). The wizards want to determine the minimum number of roads they will need to repaint green in order to reach the capital. Initially, all roads are unpainted.
The initial locations of the yellow and blue wizards are not predetermined. Therefore, the problem needs to be solved for k potential starting positions.
Input
The first line contains two integers: the number of cities n (1 ≤ n ≤ 100) and the number of roads m (1 ≤ m ≤ 500). The second line contains the number of the capital city f (1 ≤ f ≤ n). The following m lines describe the roads, with each line containing two integers a[i] and b[i], indicating a road between cities a[i] and b[i]. The next line contains the integer k (1 ≤ k ≤ 100), representing the number of possible initial placements for the wizards. The subsequent k lines each contain two integers, specifying the initial cities of the yellow and blue wizards, respectively.
Output
For each of the k scenarios, output the minimum number of roads that must be painted green for the wizards to reach the capital.