## POLICEMEN - Police Men

There is a country of cities and n-1 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 (≤ ≤ 104)  then n-1 lines each contains two integers which means there is a road between city u and v

Then an integer q (1 ≤ q  104) 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:
51 21 32 44 541 21 15 42 3
Output:
NOYES 1YES 4YES 1```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e5+5;
const int LG = log2(MAXN) + 1;

int n;
int level[MAXN], par[MAXN][LG];

void dfs(int u, int parent){
level[u] = level[parent] + 1;
par[u][0] = parent;
for(auto v : adj[u]){
if(v == parent)	continue;
dfs(v, u);
}
}

int lca(int u, int v){
if(level[u] < level[v])	swap(u, v);
int log = log2(level[u]);
for(int i = log; i >= 0; i--)
if(level[u]-level[v] >= (1 << i))
u = par[u][i];
if(u == v)
return u;
for(int i = log; i >= 0; i--){
if(par[u][i] != -1 && par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}

int main(){
io;
cin >> n;
for(int i = 0;i < n-1; i++){
int a, b;
cin >> a >> b;
}
memset(par, -1, sizeof par);
level[0] = -1;
dfs(1, 0);
for(int j = 1; j < LG; j++){
for(int i = 1; i <= n; i++){
if(par[i][j-1] != -1)
par[i][j] = par[par[i][j-1]][j-1];
}
}
int q;
cin >> q;
while(q--){
int a, b;
cin >> a >> b;
int pos_thief = a;
int pos_police = b;
if(level[a] < level[b])
cout << "NO" << endl;
else{
cout << "YES" << " ";
cout << lca(a, b> << endl;
}
}
return 0;
}``````
Copy The Code &

Input

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

Output

cmd
NO
YES 1
YES 4
YES 1