311199: CF1949C. Annual Ants' Gathering

C. Annual Ants' Gatheringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Deep within a forest lies an ancient tree, home to $n$ ants living in $n$ tiny houses, indexed from $1$ to $n$, connected by the branches of the tree.

Once a year, all the ants need to gather to watch the EUC. For this, all ants move along the $n-1$ branches of the tree they live on to meet at the home of one ant.

However, this year the ants could not agree on where to meet and need your help to gather up. You can tell all the ants currently at house $u$ to move to house $v$ if there is a branch directly connecting those two houses. However, the ants ignore your command if there are fewer ants gathered in house $v$ than in house $u$, i.e., if it would be easier for the ants from house $v$ to move. This even holds true if no ant at all is currently in house $v$. You can give this kind of commands as many times as you want.

Is it possible for you to gather all the ants in a single house?

Input

The first line contains one integer $n$ ($1\leq n\leq 200\,000$) — the number of ant homes.

Each of the following $n-1$ lines contains two integers $u$ and $v$ ($1\leq u, v\leq n$) — there is a branch directly connecting the house $u$ and house $v$. It is guaranteed that every ant can reach the house of any other ant just by following the branches of the tree.

Output

Print $\texttt{YES}$ if it is possible to gather all the ants in a single house. Otherwise, print $\texttt{NO}$.

ExamplesInput

7
5 1
3 2
4 6
3 6
7 1
1 3

Output

YES

Input

5
1 4
4 2
3 2
5 3

Output

NO

Input

6
4 5
5 6
6 1
2 6
3 2

Output

YES

Note

In the first sample, you can gather all the ants at house $3$ as follows:

• You tell to the ant at house $4$ to move to house $6$.
• You tell to the ant at house $2$ to move to house $3$.
• You tell to the two ants at house $6$ to move to house $3$ (which already contains two ants).
• You tell to the ant at house $5$ to move to house $1$.
• You tell to the ant at house $7$ to move to house $1$ (which already contains two ants).
• You tell to the three ants at house $1$ to move to house $3$ (which already contains four ants).

In the second sample, it is impossible to gather all the ants in a single house.

题目大意：
森林里有一棵古老的树，树上居住着n只蚂蚁，分别住在n个编号为1到n的小屋里，这些小屋通过树枝相连。每年，所有的蚂蚁都需要聚集在一起观看EUC。为此，所有的蚂蚁沿着树上的n-1个树枝移动，聚集到某一只蚂蚁的家中。然而，今年蚂蚁们无法就聚集地点达成一致，需要你的帮助。你可以告诉目前在屋u中的所有蚂蚁移动到屋v，如果这两栋房子之间有直接的树枝连接。但是，如果屋v中的蚂蚁比屋u中的少，即如果对于屋v中的蚂蚁来说移动更容易，那么蚂蚁们会忽略你的命令。即使目前屋v中根本没有蚂蚁，这也是成立的。你可以尽可能多次地给出这种命令。判断是否可能将所有蚂蚁聚集在同一个屋子里。

输入数据格式：
第一行包含一个整数n（1≤n≤200,000）——蚂蚁家的数量。
接下来的n-1行，每行包含两个整数u和v（1≤u, v≤n）——表示房子u和房子v之间有一条直接的树枝连接。保证每只蚂蚁都可以通过树枝到达任何其他蚂蚁的家。

输出数据格式：
如果可以将所有蚂蚁聚集在同一个屋子里，则打印“YES”。否则，打印“NO”。题目大意： 森林里有一棵古老的树，树上居住着n只蚂蚁，分别住在n个编号为1到n的小屋里，这些小屋通过树枝相连。每年，所有的蚂蚁都需要聚集在一起观看EUC。为此，所有的蚂蚁沿着树上的n-1个树枝移动，聚集到某一只蚂蚁的家中。然而，今年蚂蚁们无法就聚集地点达成一致，需要你的帮助。你可以告诉目前在屋u中的所有蚂蚁移动到屋v，如果这两栋房子之间有直接的树枝连接。但是，如果屋v中的蚂蚁比屋u中的少，即如果对于屋v中的蚂蚁来说移动更容易，那么蚂蚁们会忽略你的命令。即使目前屋v中根本没有蚂蚁，这也是成立的。你可以尽可能多次地给出这种命令。判断是否可能将所有蚂蚁聚集在同一个屋子里。 输入数据格式： 第一行包含一个整数n（1≤n≤200,000）——蚂蚁家的数量。 接下来的n-1行，每行包含两个整数u和v（1≤u, v≤n）——表示房子u和房子v之间有一条直接的树枝连接。保证每只蚂蚁都可以通过树枝到达任何其他蚂蚁的家。 输出数据格式： 如果可以将所有蚂蚁聚集在同一个屋子里，则打印“YES”。否则，打印“NO”。