Сказочная страна представляет собой множество городов, соединенных дорогами с двухсторонним движением. Причем из любого города страны можно добраться в любой другой город либо непосредственно, либо через другие города. Известно, что в сказочной стране не существует дорог, соединяющих город сам с собой и между любыми двумя разными городами, существует не более одной дороги.

В сказочной стране живут желтый и синий волшебники. Желтый волшебник, пройдя по дороге, перекрашивает ее в желтый цвет, синий в синий. Как известно, при наложении желтой краски на синюю, либо синей краски на желтую, краски смешиваются и превращаются в краску зеленого цвета, который является самым нелюбимым цветом обоих волшебников.

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

Начальное положение желтого и синего волшебников заранее не известно. Поэтому необходимо решить данную задачу для k возможных случаев их начальных расположений.

Входные данные

Первая строка содержит целые числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 500000) - количество городов и дорог в волшебной стране соответственно. Третья строка содержит одно целое число F (1 ≤ F ≤ n) - номер города, являющегося столицей сказочной страны. В следующих m строках находится описание дорог страны. В этих m строк записано по два целых числа ai и bi, означающих, что существует дорога, соединяющая города ai и bi. Следующая строка содержит целое число k (1 ≤ k ≤ 105) - количество возможных начальных расположений волшебников. Далее следуют k строк, каждая из которых содержит два целых числа - номера городов, в которых изначально находится желтый и синий волшебники соответственно.

Выходные данные

Для каждого из k тестов вывести минимальное количество дорог, которое придется покрасить в зеленый цвет волшебникам для того чтобы добраться в столицу.