Terry and Jom's Game on a Rooted Graph

Terry and Jom are playing a game on an undirected, connected graph with n vertices and m edges. The graph has a designated root vertex \( r \). The game is played under the following rules:

• Terry (the first player) moves first.
• On each turn, the current player may either move along exactly one edge or choose to stay (i.e. sleep) without moving.
• Terry is not allowed to move to a vertex which is currently occupied by Jom. (Note that if Terry moves into a vertex \( u \) and then Jom moves into \( u \) in the same round, it is legal—only if Terry deliberately walks into an already occupied vertex is the move forbidden.)

There are \( q \) queries. Each query provides starting positions \( a \) for Terry and \( b \) for Jom. Terry's objective is to eventually reach the root \( r \).

Game Analysis:

Assume that both players play optimally. Jom’s best strategy is to reach the root as fast as possible and then wait there in order to block Terry (since once Jom is at \( r \), Terry cannot move into \( r \) because Terry cannot move onto a vertex occupied by Jom).

If we let \( d(v, r) \) denote the shortest distance from vertex \( v \) to the root \( r \), then if Terry starts at \( a \) and Jom starts at \( b \), Terry can move along a shortest path towards \( r \), using one move per edge. Similarly, Jom can try to reach \( r \) by following a shortest path. Note that the turns alternate with Terry moving first.

Thus, if Terry requires \( t = d(a, r) \) moves to reach \( r \), then by the time Terry is about to make his \( t^{th} \) move, Jom would have already moved \( t-1 \) times. If Jom’s shortest distance \( j = d(b, r) \) satisfies \( j \le t-1 \), then Jom can reach \( r \) before or exactly when Terry is ready to move there and block him. Otherwise, if \( d(a, r) \le d(b, r) \) (taking into account the turn order), Terry can always reach \( r \) on his turn before Jom has occupied \( r \).

Conclusion:

Terry can reach the root \( r \) if and only if \( d(a, r) \le d(b, r) \). In each query, output "Yes" if Terry can reach \( r \) and "No" otherwise.

inputFormat

The input begins with a line containing three integers: \( n \) (number of vertices), \( m \) (number of edges), and \( r \) (the root vertex).

Then follow \( m \) lines, each containing two integers \( u \) and \( v \), representing an undirected edge between vertices \( u \) and \( v \).

The next line contains an integer \( q \) denoting the number of queries.

Each of the following \( q \) lines contains two integers \( a \) and \( b \): the starting positions of Terry and Jom respectively.

outputFormat

For each query, output a single line with either "Yes" if Terry can reach the root \( r \), or "No" otherwise.

sample

5 5 3
1 3
2 3
3 4
4 5
2 5
3
1 2
4 1
5 2

Yes
Yes
No

</p>