Стражи Галактики получили сигнал бедствия с разрушенного Таносом корабля. Им нужно как можно скорее обнаружить корабль и спасти находящегося на нем Тора.
Способ перемещения корабля весьма необычен. Существует 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