A Splay tree is a type of balanced binary search tree. That is, a Splay tree is first and foremost a binary tree: each node has at most two children (a left child and a right child).

There are two basic operations in a Splay tree: left rotation and right rotation. A left rotation promotes a node's right child, while a right rotation promotes a node's left child.

You are given two labeled Splay trees, each with $n$ nodes. You need to transform the initial state into the target state using at most $2n$ left or right rotation operations.

Input

The input is read from standard input.

The first line contains a positive integer $n$, representing the number of nodes.

The next $n-1$ lines each contain three integers $x, y, c$, indicating that node $x$ has a child node $y$. If $c$ is $0$, then $y$ is the left child; otherwise, $y$ is the right child. This tree represents the initial state.

The next $n-1$ lines each contain three integers $x, y, c$, indicating that node $x$ has a child node $y$. If $c$ is $0$, then $y$ is the left child; otherwise, $y$ is the right child. This tree represents the target state.

Output

The output is written to standard output.

The first line should output No or Yes. No indicates that the target state cannot be reached within $2n$ operations, otherwise output Yes.

If you output Yes, the next line should output an integer $times$, representing the number of operations used in your construction.

The following $times$ lines each contain two integers $x, c$. If $c$ is $0$, it represents a left rotation on node $x$; otherwise, it represents a right rotation.

It is guaranteed that the input trees are valid.

Examples

Input 1

3
3 1 0
1 2 1
1 3 1
3 2 0

Output 1

Yes
3
1 0
2 1
3 1

Input 2

2
1 2 0
2 1 0

Output 2

No