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

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

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

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

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

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

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

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