B. Tree Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Spyrosaliv and Cow the Cow are playing a game on a tree of size $$$n$$$.

Spyrosaliv will start at node $$$s$$$. Spyrosaliv and Cow the Cow will play in alternating turns, with Spyrosaliv playing first.

Suppose Spyrosaliv is on node $$$u$$$. Spyrosaliv has to choose any node $$$v$$$ such that the edge $$$(u, v)$$$ exists and is not blocked, and move there. If such a node doesn't exist, he loses. If $$$v = d$$$, he wins.

If it's Cow the Cow's turn, he will do these two operations in the following order:

  1. If it is not his first turn and he blocked an edge on his previous turn, unblock it.
  2. Choose an edge that he did not block in his exact previous turn and block it, or do nothing. If it's his first turn, he may block any edge.

If both Spyrosaliv and Cow the Cow play optimally, will Spyrosaliv win the game?

Input

The first line contains exactly three integers: $$$n$$$, $$$s$$$, and $$$d$$$ $$$(2 \le n \le 2 \cdot 10^5$$$, $$$1 \le s, d \le n$$$, $$$s \neq d$$$), the size of the tree, Spyrosaliv's starting node, and Spyrosaliv's destination, respectively.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$, representing an edge $$$(u, v)$$$ in the tree.

The input is guaranteed to give a valid tree, and it is guaranteed that $$$s \neq d$$$.

Output

Output exactly one string: 'YES' if Spyrosaliv will win and 'NO' otherwise. Note that 'yEs', 'Yes', 'nO', and so on, are also acceptable answers.

Examples
Input
5 2 4
1 4
2 5
4 3
3 5
Output
NO
Input
2 1 2
1 2
Output
YES
Note

In the first example, the tree is as follows:

Spyrosaliv starts at node $$$2$$$, and wins if he gets to node $$$4$$$. A possible sequence of moves is as follows:

  • Spyrosaliv moves from node $$$2$$$ to $$$5$$$.
  • Cow the Cow will block edge $$$(5, 3)$$$.
  • Since Spyrosaliv can't move to node $$$3$$$, he will move back to node $$$2$$$.
  • Cow the Cow will unblock edge $$$(5, 3)$$$. Note that it is not allowed for him to block that edge again in this turn. Cow the Cow will block edge $$$(2, 5)$$$.
  • Spyrosaliv cannot make a move; therefore, he loses.

It can be shown that in this example, no matter how Spyrosaliv plays, Cow the Cow has a winning strategy.