28925번 - Поиск корабля 다국어

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

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

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

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

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

Каждая из следующих $m$ строк содержит по два целых числа $a_i$ и $b_i$ --- номера точек, соединенных $i$-й кротовой норой ($1 \le a_i, b_i \le n$).

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

Каждая из следующих $q$ строк содержит по два целых числа $v_i$ и $k_i$ --- предполагаемый номер точки, куда направлялся Тор, и количество совершенных им перемещений по кротовым норам ($1 \le v_i \le n$; $1 \le k_i \le m$).

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

• Если описанной в предположении ситуации быть не могло (например, если не существует пути от точки $s$ до точки $v_i$), выведите число $0$;
• Если описанная в предположении ситуация могла быть, и в данный момент существует более одной точки, в которой может находиться корабль, выведите число $-1$;
• В противном случае, то есть если положение корабля может быть определено однозначно, выведите номер точки, в которой согласно этому предположению должен располагаться корабль.