Given a directed graph $G$ with $n$ nodes and $n-1$ directed edges, and a positive integer $k \le n$, it is guaranteed that the graph $G$ is connected when its edges are treated as undirected (i.e., it forms a tree).

There are $q$ operations. There are five types of operations, with parameters as follows:

• 1 x y: Reverse the direction of the edge between node $x$ and node $y$. It is guaranteed that an edge exists between node $x$ and node $y$.
• 2 a: Reverse the direction of all incoming edges of node $a$.
• 3 b: Reverse the direction of all outgoing edges of node $b$.
• 4 c: Reverse the direction of all incoming and outgoing edges of node $c$.
• 5 p: Update the value of $k$ to $p$.

Here, an incoming edge of node $u$ is a directed edge ending at $u$, and an outgoing edge of node $u$ is a directed edge starting at $u$.

You need to maintain this directed graph and, before the first operation and after each operation, determine whether all nodes except node $k$ can reach node $k$ via the current directed edges. If so, output YES, otherwise output NO.

Input

The first line contains three integers $n, k, q$ ($2 \le n \le 10^6$, $0 \le q \le 10^6$, $1 \le k \le n$).

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing a directed edge from node $u_i$ to node $v_i$ ($1 \le u_i, v_i \le n$).

The next $q$ lines each contain 2 to 3 positive integers representing an operation. The meanings and formats are as defined above ($1 \le x, y, a, b, c, p \le n$).

It is guaranteed that the graph $G$ is connected when its edges are treated as undirected (i.e., it forms a tree), and it is guaranteed that an edge exists between node $x$ and node $y$ when performing the first type of operation.

Output

Output $q+1$ lines. Before the first operation and after each operation, determine whether all nodes except node $k$ can reach node $k$ via the current directed edges. If so, output YES, otherwise output NO.

Examples

Input 1

10 10 10
9 10
1 5
3 9
8 9
4 9
7 9
5 4
2 10
6 7
4 5
3 2
3 1
1 10 2
1 5 1
1 4 5
5 4
2 9
1 9 3
2 9

Output 1

YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO

Input 2

10 4 10
8 9
2 4
10 5
9 4
3 2
1 2
5 4
6 4
7 8
1 2 1
1 2 1
5 10
1 5 4
1 10 5
3 4
1 5 4
5 2
1 5 10
1 4 5

Output 2

YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO