POLICEMEN  Police Men
There is a country of n cities and n1 bidirectional roads you can go from any city to another using its roads
You are a police man and there is a theif who is going to escape from the country using an airport in city 1 you are given m queries which of type "a b" which means the thief is in city a and you are in city b you should find if it's possible to catch him before he escape or not and find the city which you will catch him in if it's possible.
You are moving at the same speed the thief moving at and the thief is taking the shortest path to city 1
If you arrived in a city in the same time as the thief you can catch him in it if you arrived before him you can wait for him
If there is more than one city you can catch him in print the nearest one to you.
Input
the first line contains an integer n (1 ≤ n ≤ 10^{4}) then n1 lines each contains two integers which means there is a road between city u and v
then an intger q (1 ≤ q ≤ 10^{4}) and q lines of form a b (1 ≤ a , b ≤ n) which are the thief's position and your position
Output
for each query print YES then a space then the city which you will catch him in if it's possible otherwise print NO
Example
Input: 5
1 2
1 3
2 4
4 5
4
1 2
1 1
5 4
2 3
Output: NO
YES 1
YES 4
YES 1
hide comments
vinay1998:
20180613 08:46:26
AC in one go !!! ( LCA , shortest distance from root ) 

abdou_93:
20160812 08:47:24
"nearest one to you." 

mahmoudbadawy5:
20160725 08:18:21
Sorry but there were a mistake in the data set but I couldn't rejudge the solutions please resubmit your solutions 
Added by:  mahmoudbadawy5 
Date:  20160721 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 
Resource:  Mine 