Colored Wizards
A fairy-tale country represents itself a number of cities connected by roads with a two-way traffic. From any city in the country you can get to any other city either directly or through other cities. It is known that in a fairytale country there are no roads connecting the city with itself and between any two different cities there is no more than one road.
Yellow and blue wizards live in the fairy-tale country. The yellow wizard, passing along the road, repaints it in yellow, blue wizard repaints the road in blue. As you know, after applying yellow color on blue, or blue paint on yellow, the paints mix and turn into green color, which is the most unloved color of both wizards.
This year a conference of wizards is held in the capital of the country (city F) . Therefore, yellow and blue wizards want to know what minimal number of roads they will have to recolour in green to get to the capital. Initially, all roads are not painted.
The initial position of the yellow and blue wizards is not known in advance. Therefore, it is necessary to solve this problem for k possible cases of their initial locations.
Input
First line contains integers n (1 ≤ n ≤ 10^5) and m (1 ≤ m ≤ 500000) - the number of cities and roads in fairy-tale country. Third line contains an integers F (1 ≤ F ≤ n) - number of the city that is a capital of the country. Next m lines contain the description of roads in the country. Each of m lines contains two integers a[i] and b[i] meaning that there exist a road between a[i] and b[i]. Next line contains integer k (1 ≤ k ≤ 10^5) - the number of possible initial locations for wizards. Each of the next k lines contains two integers - the city numbers where initially located yellow and blue wizards.
Output
For each of the k tests print the minimum number of roads that will have to be painted green by wizards in order to get to the capital.