Поиск корабля
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Стражи Галактики получили сигнал бедствия с разрушенного Таносом корабля. Им нужно как можно скорее обнаружить корабль и спасти находящегося на нем Тора.

Способ перемещения корабля весьма необычен. Существует n различных точек во Вселенной, пронумерованных от 1 до n, между которыми происходит перемещение корабля. Также существует m кротовых нор, i-я из которых соединяет собой точки с номерами ai и bi. Обратите внимание, что кротовая нора может соединять точку с саму с собой, а также между двумя точками может быть более одной кротовой норы. Перемещение на корабле по каждой из кротовых нор занимает ровно один час.

Изначально корабль находился в точке с номером s. Стражи думают, что Тор пытался направить корабль к одной из точек, но по пути вынужден был остановиться. У них есть q предположений, i-е из которых состоит в следующем: Тор, начав свой путь в точке с номером s, двигался по одному из кратчайших путей в точку с номером vi, однако, переместившись по кротовым норам ki раз, корабль остановился и перестал двигаться дальше. Кратчайший путь — это путь, который содержит минимальное возможное количество кротовых нор.

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

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

Первая строка входных данных содержит три целых числа n, m и s — количество точек, кротовых нор и номер стартовой точки соответственно (1 ≤ n, m ≤ 50 000; 1 ≤ s ≤ n).

Каждая из следующих m строк содержит по два целых числа ai и bi — номера точек, соединенных i-й кротовой норой (1 ≤ ai, bi ≤ n).

Следующая строка содержит единственное число q — количество предположений Стражей (1 ≤ q ≤ 50 000).

Каждая из следующих q строк содержит по два целых числа vi и ki — предполагаемый номер точки, куда направлялся Тор, и количество совершенных им перемещений по кротовым норам (1 ≤ vi ≤ n; 1 ≤ ki ≤ m).

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

Для каждого из предположений выведите в отдельной строке результат проверки этого предположения, а именно:

Пример

Входные данные
7 7 1
1 2
1 3
2 4
3 4
1 5
2 6
4 7
5
4 1
6 1
7 1
7 2
5 2
Выходные данные
-1
2
-1
4
0