finding-arya-stark

As all of us know Brienne has swore an oath to keep Arya stark safe and sound.They live in the historic "Seven Kingdoms".
Seven Kingdoms has a unique architecture with total N cities. The King's landing is the capital city having address = 1. Rest of the cities in seven Kingdoms have some unique address and are connected by roads and there is always a unique path between any two cities. Note that the King's Landing is also included in these cities.

The thing is arya has went missing and Its Breinne's job to find her . Arya can be in any of the city in the Seven Kingdoms including the King's Landing. As , Brienne has limited resources, for finding arya, she either goes towards the King's landing (she stops when she reaches there), or she moves away from the King's Landing in any possible path till the last city on that path.

Arya is in some city (say X) and Brienne is starting the search from her city (say Y). If Brienne reaches city  X, then he surely finds Arya.

Given Q queries, you need to tell Breinne if it is possible for her to find arya or not.If possible then the minimum number of cities she needs to search before she finds her be denoted by c.

The queries can be of the following two types:

0 X Y : Breinne moves towards the King's Landing.

1 X Y : Breinne moves away from the King's Landing.

INPUT :

The first line of the input contains a single integer N, total number of cities in the Seven Kingdoms. Next N-1 lines contain two space separated integers A and B denoting a road between the cities at address A and B.
Next line contains a single integer Q denoting the number of queries.
Following Q lines contain three space separated integers representing each query as explained above.

OUTPUT :

Print "YES c" or "NO" for each query depending on the answer to that query. Where c is the variable defined above.

CONSTRAINTS :

1 ≤ N ≤ 10^5  +1

1 ≤ A,B ≤ N

1 ≤ Q ≤ 5*10^5  +1

1 ≤ X,Y ≤ N

NOTE :
Large Input size.  fast I/O methods.

Author : Jinesh Shah

SAMPLE INPUT
6
1 2
2 3
3 4
3 6
2 5
4
0 2 6
1 6 2
0 5 6
1 1 4

SAMPLE OUTPUT
YES 3
YES 3
NO
NO

Source: hackerearth | Difficulty: MEDIUM


Solutions: