Capital Queries

0

0 votes
Hard, Tree, DFS
Problem

A country has n cities. These n cities are connected using n - 1 bidirectional roads, such that it is possible to go from any city to any other city using these roads. City m is considered to be the capital of the country. The president of the country has asked your help in q queries.

In each query, you will be given two cities u and v. You need to find whether the shortest path from city u to city v passes through the capital of the city. 

See sample case for better understanding

 

Input format:

First line contains two integers n and m, denoting the number of cities and the capital city.

Next n - 1 lines contains two integers u and v, denoting that there is a road between city u and city v.

Next line contains an integer q, denoting the number of queries.

Next q lines contain two integers u and v, describing the query.

Output format:

For each query, print "YES"(without quotes) if the shortest path from city u to city v passes through the capital, else print "NO"(without quotes). .

 

Constraints:

1 <= n, q <= 100000(1e5)

1 <= u, v, m <= n

 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In first query, shortest path between city 5 and 4 is: 5 -> 3 -> 4, which doesnot pass through capital city 2. Hence, answer is "NO".

In second query, shortest path is: 1 -> 2 -> 3 -> 4, which passes through capital. Hence, answer is "YES".

In third query, shortest path is 1 -> 2, which passes through capital and so answer is "YES".

In fourth query, shortest path is 2 -> 3, which passes through capital ans so answer is "YES".

Editor Image

?