P16854 [HackerEarth] As all of us know Brienne has swore an oath to keep Arya stark safe and sound.They live in the historic "Seven Kingdoms".
普及
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
100 15 49 93 86 54 50 64 59 7 88 47 70 38 21 26 35 29 44 1 7 40 84 36 65 6 27 19 42 26 66 29 15 5 71 27 11 80 40 51 13 12 52 44 19 94 100 52 10 100 58 34 18 60 68 33 77 97 48 68 36 79 74 8 90 7 12 43 76 65 17 76 56 85 69 33 60 7 4 31 51 53 67 11 78 92 62 73 72 61 47 72 2 40 54 98 82 59 24 38 81 20 39 71 73 37 34 44 79 81 41 15 95 58 80 99 75 61 29 9 8 50 25 91 31 1 53 77 89 31 30 39 22 41 83 18 9 23 61 78 5 62 87 33 20 26 23 86 43 25 99 26 32 98 93 88 38 21 46 87 91 82 97 84 37 88 55 98 94 96 85 95 57 95 14 3 16 17 28 75 45 74 96 1 92 14 33 51 98 28 63 46 64 88 26 69 6 95 3 100 1 73 69 1 38 7 0 17 60 1 30 20 0 25 34 0 10 27 1 58 52 1 16 29 0 86 58 0 88 3 0 33 3 0 86 43 0 86 94 0 33 17 1 83 96 1 56 93 1 53 34 0 100 52 0 17 77 1 28 60 1 89 63 0 55 84 0 70 44 1 19 79 1 85 60 1 58 87 0 53 85 1 6 39 1 10 83 1 90 9 1 11 74 0 9 97 1 55 42 0 88 81 1 56 80 0 9 37 0 5 11 0 80 55 1 50 97 1 10 92 1 8 7 1 19 98 1 20 68 1 78 83 0 7 1 0 37 13 0 30 15 0 14 47 1 2 96 1 59 19 0 35 71 1 34 89 1 47 11 0 8 41 1 5 63 1 30 53 1 59 42 1 98 25 0 84 31 0 68 17 0 23 2 0 5 22 1 25 80 1 53 76 0 93 54 1 86 25 1 87 64 0 53 30 1 59 38 1 52 2 0 94 19 0 12 59 0 14 1 1 52 94 1 48 59 1 47 49 1 22 89 0 86 43 0 13 31 0 60 23 0 12 21 1 51 88 0 73 78 1 11 65 0 53 67 0 36 48 0 3 32 1 28 60 0 64 46 1 61 7 1 13 69 0 24 83 1 64 38 0 62 14 1 63 61 1 54 29 1 53 67 0 2 69 0 3 61 0 81 2
样例输出
NO NO NO NO YES 119 NO NO NO NO NO NO YES 17 YES 21 YES 3 YES 80 NO NO YES 3 YES 125 NO NO NO YES 13 NO YES 20 YES 17 NO YES 8 YES 21 NO NO NO NO NO NO NO NO YES 8 NO YES 18 NO NO YES 11 NO YES 3 NO YES 17 NO YES 2 YES 9 NO NO YES 13 NO NO YES 16 NO NO NO YES 7 NO NO YES 18 NO NO NO NO YES 7 NO YES 4 NO YES 42 NO YES 106 NO NO YES 145 NO NO YES 11 NO YES 107 NO YES 3 NO NO NO YES 33 NO YES 11 NO YES 10 NO YES 117 NO YES 18 NO YES 21 NO YES 13 NO NO NO NO NO NO NO YES 93 NO YES 4 NO NO YES 16 YES 11 YES 3 NO NO YES 2 NO YES 16 YES 2 YES 20 NO NO NO YES 65 NO YES 12 NO YES 3 NO YES 6 YES 78 YES 2 YES 14 NO NO NO NO NO YES 5 YES 11 NO NO NO NO NO YES 9 NO YES 3 NO NO NO NO NO NO NO YES 17 YES 25 NO YES 11 NO YES 14 NO NO NO YES 18 NO NO NO YES 10 NO YES 3 NO YES 18 NO NO NO NO NO NO NO YES 7 YES 17 NO YES 12 NO NO NO YES 8 YES 7 YES 9 NO YES 14 NO NO NO YES 18 NO NO NO NO NO NO NO NO NO YES 125 YES 2 NO NO NO NO NO YES 9 NO NO YES 21 NO NO NO YES 6 YES 58 NO NO YES 76 NO NO YES 7 NO YES 3 NO YES 14 YES 2 NO NO NO YES 10 NO NO YES 9 NO NO NO NO YES 6 YES 18 NO NO YES 3 NO YES 12 NO NO YES 14 YES 21 NO YES 16 NO NO NO NO YES 107 YES 98 NO NO NO YES 18 NO NO NO NO NO NO NO NO NO NO YES 2 NO NO NO NO NO NO NO NO NO NO NO NO YES 11 NO NO NO NO YES 17 NO NO NO NO NO NO YES 185 NO NO YES 21 NO NO NO NO YES 8 NO NO YES 68 YES 6 NO YES 12 NO NO NO NO NO NO YES 8 NO NO NO YES 21 YES 11 NO YES 3 YES 17 NO NO NO NO YES 6 NO NO NO YES 5 NO NO YES 3 YES 19 NO NO NO YES 6 NO YES 19 NO NO YES 11 YES 10 NO NO NO YES 5 NO NO NO YES 18 YES 2 NO YES 17 NO NO YES 5 NO NO YES 9 YES 18 NO NO NO YES 18 YES 5 NO YES 12 NO NO YES 2 NO YES 15 NO YES 16 NO NO NO YES 147 NO YES 4 NO YES 17 NO YES 13 NO YES 18 NO NO YES 3 NO NO YES 6 YES 5 NO NO NO NO YES 17 NO NO NO NO NO YES 6 YES 17 YES 15 NO NO NO YES 14 YES 151 NO NO NO NO YES 19 NO NO NO NO YES 8 NO YES 4 NO NO YES 6 NO YES 12 NO YES 19 YES 3 NO NO YES 6 NO NO NO YES 9 NO NO YES 5 YES 20 NO NO NO NO YES 10 YES 10 NO NO NO YES 88 YES 15 YES 5 NO NO NO NO YES 9 NO YES 17 NO NO YES 17 NO YES 3 NO NO YES 12 NO YES 13 YES 17 NO NO NO YES 27 NO YES 2 NO NO NO NO NO NO NO NO NO NO YES 3 NO YES 12 NO NO NO YES 9 YES 7 YES 3 NO NO NO YES 2 NO NO NO YES 2 YES 17 NO NO NO NO YES 16 YES 4 NO NO YES 4 NO NO NO NO YES 76 NO NO NO NO YES 10 NO NO YES 80 NO NO YES 6 YES 17 NO YES 10 NO NO NO NO NO NO NO NO NO NO YES 8 YES 14 NO NO YES 16 YES 8 NO YES 19 NO NO NO NO NO NO YES 4 NO NO YES 2 YES 19 NO NO NO YES 17 YES 2 YES 2 YES 20 NO YES 10 NO NO NO NO NO NO NO NO YES 14 YES 13 NO NO NO NO NO NO NO NO NO YES 91 NO NO NO NO NO NO NO YES 20 YES 16 YES 11 YES 169 YES 17 NO NO NO NO NO YES 7 NO NO NO NO NO NO YES 12 YES 14 NO NO NO NO YES 14 NO NO NO YES 10 YES 5 NO NO NO NO YES 12 NO YES 12 NO YES 16 YES 14 NO NO NO NO NO NO NO YES 9 NO YES 5 NO NO NO YES 14 NO YES 8 NO NO NO NO YES 12 NO NO NO YES 2 NO YES 4 NO NO YES 7 YES 18 YES 17 NO NO NO YES 98 YES 20 NO NO NO YES 6 NO NO YES 14 NO NO YES 63 NO NO YES 13 NO YES 16 NO NO NO YES 7 YES 11 NO NO NO NO YES 15 YES 5 YES 21 YES 11 YES 3 NO NO NO NO NO NO YES 14 NO NO NO NO NO YES 8 NO YES 21 NO NO YES 31 NO NO NO YES 12 NO NO NO NO NO NO NO YES 17 NO NO YES 6 YES 10 NO YES 9 YES 8 NO YES 2 NO NO YES 16 YES 14 NO NO NO NO YES 18 YES 3 YES 6 YES 6 YES 16 NO NO NO NO NO YES 19 NO NO NO NO NO NO YES 11 YES 17 NO NO NO YES 115 NO YES 2 NO NO NO NO NO NO NO NO NO YES 3 NO NO NO NO NO YES 12 NO YES 6 NO YES 11 NO YES 17 NO NO NO YES 17 NO YES 4 YES 4 NO NO NO NO YES 6 NO NO NO NO YES 13 YES 6 NO NO NO NO NO YES 16 YES 6 NO NO YES 95 NO NO NO NO YES 14 NO NO NO NO YES 21 NO NO NO NO YES 10 NO NO YES 15 NO YES 11 NO YES 18 YES 16 NO YES 6 NO NO YES 19 YES 7 NO NO NO NO YES 3 YES 2 YES 2 NO YES 13 NO NO NO NO NO NO NO YES 3 NO NO NO NO NO NO NO YES 13 NO NO YES 8 YES 89 NO YES 3 NO NO NO NO NO NO YES 18 YES 4 NO NO NO NO NO NO NO NO YES 3 NO NO YES 19 NO NO NO NO NO NO YES 16 NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 11 YES 3 YES 12 NO YES 16 YES 9 YES 7 YES 65 NO NO NO NO YES 21 YES 10 YES 7 YES 14 YES 37 YES 14 NO YES 19 YES 10 NO NO NO NO NO NO NO NO NO NO NO NO NO YES 18 NO YES 4 NO NO YES 4 NO NO YES 13 NO NO NO YES 7 NO NO NO YES 17 YES 8 NO NO NO NO NO NO