eolymp
Competitions

2011 Зимняя Школа, Харьков, День 8, День Виталия Гольдштейна

Цветные волшебники

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

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

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

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

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

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

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

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

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
6 6
1
1 2
2 3
3 4
4 2
4 5
3 6
2
5 6
6 6
Output example #1
1
2
Author Vitaly Goldstein
Source Winter School, Kharkov, 2011, Day 9