#D8512. Courage Test
Courage Test
Courage Test
P "Today is the recording of a program of a liver test project."
O-type Chieri "Ki, Kimo no good ..."
Kanako Shimura "Is Chieri-chan okay?"
Akane Tsukino "As expected, Mr. P! It's a wonderful commentary that clearly shows the situation in one line! Come on! Let's run toward the fireball!"
P "The rules are simple, we just work together to visit all the shrines in this area."
Akane "It's orthodox! Let's run toward the shrine immediately!"
Kanako "But there were many shrines that had to be visited at one of the highest density of shrines in Japan ..."
Kanako "But it's encouraging to have Akane!"
P "By the way, everyone starts from a different shrine, and merging is also prohibited. Then Chieri and Kanako should follow the initial position."
Chieri "Uh ..."
Kanako "Oh, it's okay if you bring some sweets!"
Chieri "I'll do my best ..."
Akane "Producer! What should I do!"
P "You are lively"
Akane "Eh"
P "Sit down"
madder""
Constraints
- 2 ≤ n ≤ 105
- 1 ≤ ai, bi, u, v ≤ n
- u ≠ v
- ai <bi
- (ai, bi) ≠ (aj, bj) (i ≠ j)
Input
The input is given in the following format.
n u v a1 b1 a2 b2 ... an−1 bn−1
The first line is given three integers n, u, v separated by blanks. From the 2nd line to the nth line, two integers ai and bi are given, separated by blanks.
Output
Output "Yes" if the rule can be satisfied, and "No" if it cannot be satisfied on one line.
Examples
Input
4 1 4 1 2 2 3 3 4
Output
Yes
Input
8 3 6 1 2 2 4 3 4 4 5 5 6 6 7 7 8
Output
No
Input
4 2 3 1 2 2 3 3 4
Output
Yes
Input
6 1 5 1 2 1 4 2 3 4 5 3 6
Output
No
inputFormat
Input
The input is given in the following format.
n u v a1 b1 a2 b2 ... an−1 bn−1
The first line is given three integers n, u, v separated by blanks. From the 2nd line to the nth line, two integers ai and bi are given, separated by blanks.
outputFormat
Output
Output "Yes" if the rule can be satisfied, and "No" if it cannot be satisfied on one line.
Examples
Input
4 1 4 1 2 2 3 3 4
Output
Yes
Input
8 3 6 1 2 2 4 3 4 4 5 5 6 6 7 7 8
Output
No
Input
4 2 3 1 2 2 3 3 4
Output
Yes
Input
6 1 5 1 2 1 4 2 3 4 5 3 6
Output
No
样例
4 2 3
1 2
2 3
3 4Yes