,
The Hidden Vertex
Input file: standard input
Output file: standard output
Time limit: 3 seconds
Memory limit: 512 megabytes
Petya and Vasya are playing a game on an undirected graph. The graph has n vertices, numbered from
1 to n, connected by m edges, with the i-th edge connecting vertices ai and bi . Note that an edge can
connect a vertex to itself, and there can be more than one edge between two vertices.
The game proceeds as follows. Petya poses a riddle to Vasya q times. The riddle numbered i is arranged as
follows. Petya places a token at vertex s (this vertex is common for all riddles) and chooses vertex vi . Then
Petya starts moving the token from vertex s to vertex vi along some shortest path, while Vasya cannot
see the movements. After making ki moves along the edges, Petya stops and asks Vasya to determine at
which vertex the token is located.
Help Vasya determine for each riddle: is Petya deceiving him by claiming that he made ki moves, since
there can be no path from s to vi or the shortest path from s to vi is be shorter. If Petya is not deceiving
him, is it true that the vertex where the token is located is uniquely determined, and if so, what is that
vertex?
Input
The first line of input contains three integers n, m, and s — the number of vertices, edges, and the starting
vertex index, respectively (1 ≤ n, m ≤ 50 000; 1 ≤ s ≤ n).
Each of the following m lines contains two integers ai and bi — the vertices connected by the i-th edge
(1 ≤ ai , bi ≤ n).
The next line contains a single integer q — the number of riddles (1 ≤ q ≤ 50 000).
Each of the following q lines contains two integers vi and ki — the vertex towards which Petya is moving
the token, and the number of moves he has made along the edges (1 ≤ vi ≤ n; 1 ≤ ki ≤ m).
Output
For each of the riddles, output the answer on a separate line, namely:
• If the described situation in the riddle could not occur: there is no path from vertex s to vertex vi
or the shortest path is shorter than ki , output the number 0;
• If the described situation in the riddle could occur, and there is currently more than one vertex
where the token could be located, output the number −1;
• Otherwise, that is, if the position of the token can be determined uniquely, output the index of the
vertex where it is located.
Scoring
This problem has four subtasks.
In the first subtask, n ≤ 100, m ≤ 2000, q = 1. It is worth 2 points. The results on the tests cases for this
subtask are available during the contest.
In the second subtask, 1 ≤ n, m ≤ 50 000, q = 1. It is worth 2 points. The results on the tests cases for
this subtask become available only after the contest ends.
In the third subtask, n ≤ 100, m ≤ 2000, q ≤ 50 000. It is worth 3 points. The results on the tests cases
for this subtask become available only after the contest ends.
In the fourth subtask, 1 ≤ n, m ≤ 50 000, q ≤ 50 000. It is worth 3 points. The results on the tests cases
for this subtask become available only after the contest ends.
Page 1 of 2
,
Example
standard input standard output
7 7 1 -1
1 2 2
1 3 -1
2 4 4
3 4 0
1 5
2 6
4 7
5
4 1
6 1
7 1
7 2
5 2
Page 2 of 2