You are given a tree with $n$ nodes, labeled $1, 2, \dots, n$. Each node $i$ ($1 \le i \le n$) has a positive integer weight $b_i > 0$. For every tree edge connecting nodes $u$ and $v$, the edge weight is $w_{uv} = b_u + b_v$.

Given the structure of the tree and the weight of each edge, you need to determine whether there exists a set of node weights that satisfies the conditions. If they exist, output any such set of node weights.

Input

The first line contains a positive integer $n$ ($1 \le n \le 2 \times 10^5$), representing the number of nodes.

The next $n-1$ lines each contain three integers $u, v, w_{uv}$ ($1 \le u, v \le n$, $1 \le w_{uv} \le 10^9$), representing a tree edge connecting nodes $u$ and $v$ with weight $w_{uv}$.

Output

If no such set of node weights exists, output a single line containing the string NO.

Otherwise, first output a single line containing the string YES, then output $n$ positive integers $b_1, \dots, b_n$ on the second line, representing the set of node weights you found. You must ensure that for all $1 \le i \le n$, $b_i \le 10^9$.

If there are multiple sets of weights that satisfy the conditions, you may output any one of them.

Examples

Input 1

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

Output 1

YES
3 2 1 1 5

Input 2

4
1 2 5
2 3 9
3 4 4

Output 2

NO

Note

For the first example, it can be verified that the given weights satisfy the conditions. Note that $w_{34} = b_3 + b_4 = 2$, so $b_3$ and $b_4$ must both be $1$, which then allows the weights of the other nodes to be determined.

For the second example, note that $b_2 + b_3 = w_{23} = 9 = w_{12} + w_{34} = b_1 + b_2 + b_3 + b_4$, which implies $b_1 + b_4 = 0$. This contradicts $b_1 > 0$ and $b_4 > 0$, therefore no such set of node weights exists.