Сказочная страна представляет собой множество городов, соединенных дорогами с двухсторонним движением. Причем из любого города страны можно добраться в любой другой город либо непосредственно, либо через другие города. Известно, что в сказочной стране не существует дорог, соединяющих город сам с собой и между любыми двумя разными городами, существует не более одной дороги.
В сказочной стране живут желтый и синий волшебники. Желтый волшебник, пройдя по дороге, перекрашивает ее в желтый цвет, синий — в синий. Как известно, при наложении желтой краски на синюю, либо синей краски на желтую, краски смешиваются и превращаются в краску зеленого цвета, который является самым нелюбимым цветом обоих волшебников.
В этом году в столице страны (городе F) проводится конференция волшебников. Поэтому желтый и синий волшебники хотят узнать, какое минимальное количество дорог им придется перекрасить в зеленый цвет, чтобы добраться в столицу. Изначально все дороги не покрашены.
Начальное положение желтого и синего волшебников заранее не известно. Поэтому необходимо решить данную задачу для К возможных случаев их начальных расположений.

Входные данные
Первая строка входного файла содержит целые числа: N (1 ≤ N ≤ 100000) и M (1 ≤ M ≤ 500000) — количество городов и дорог в волшебной стране соответственно. Третья строка содержит одно целое число F (1 ≤ F ≤ N) — номер города, являющегося столицей сказочной страны. В следующих M строках, находится описание дорог страны. В этих M строк записано по два целых числа Ai и Bi, означающих, что существует дорога, соединяющая города Ai и Bi. Следующая строка содержит целое число K (1 ≤ K ≤ 100000) — количество возможных начальных расположений волшебников. Далее следуют K строк, каждая из которых содержит два целых числа— номера городов, в которых изначально находится желтый и синий волшебники соответственно.
Выходные данные
Для каждого из K случаев, ваша программа должна вывести минимальное количество дорог, которое придется покрасить в зеленый цвет волшебникам для того, чтобы добраться в столицу.