Descendant of Descendants

0

0 votes
Medium
Problem

Dr Sankey is given a tree with N nodes and N1 edges.He is also given Q queries.In each query two nodes will be given.He has to print "YES" if the lowest common ancestor of the the given nodes is either one of the two given nodes,else "NO".Help him find the correct answer.
Root of tree is supposed to be 1.
Lowest common ancestor:Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

INPUT:
First line will contain N i.e number of nodes.
The following N1 lines contains a pair of integers x and y which denotes a edge between the node x and node y. 
Next line will contain Q i.e no of queries.
The following Q lines will contain two integers a and b.

OUTPUT:
For each query print the required answer in new line.

CONSTRAINTS:
1<=N<=100000
1<=Q<=1000000    
1<=a,b<=N

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?