Дан ориентированный граф $G$, содержащий $n$ вершин и $\boldsymbol{n-1}$ ориентированных рёбер, и положительное целое число $k$, не превосходящее $n$. Гарантируется, что, если считать все рёбра $G$ неориентированными, граф будет связным (то есть образует дерево).

Нужно выполнить $q$ операций. Есть пять типов операций со следующими параметрами:

• 1 x y: развернуть ребро между вершинами $x$ и $y$. Гарантируется, что между вершинами $x$ и $y$ есть ребро;
• 2 a: развернуть все входящие рёбра вершины $a$;
• 3 b: развернуть все исходящие рёбра вершины $b$;
• 4 c: развернуть все входящие и исходящие рёбра вершины $c$;
• 5 p: изменить значение $k$ на $p$.

Входящее ребро вершины $u$ — это ориентированное ребро, заканчивающееся в $u$, а исходящее ребро вершины $u$ — это ориентированное ребро, начинающееся в $u$.

Поддерживайте этот ориентированный граф и перед первой операцией и после каждой операции определяйте, могут ли все вершины, кроме $k$, достичь вершины $k$ по текущим ориентированным рёбрам. Если могут, выведите YES, иначе выведите NO.

Входные данные

Первая строка содержит три целых числа $n,k,q$ ($2 \le n \le 10^6$, $0 \le q \le 10^6$, $1 \le k \le n$).

Каждая из следующих $n-1$ строк содержит два положительных целых числа $u_i,v_i$, обозначающих ребро между вершинами $u_i$ и $v_i$, а именно ориентированное ребро из вершины $u_i$ в вершину $v_i$ ($1 \le u_i,v_i \le n$).

Каждая из следующих $q$ строк содержит $2\sim3$ положительных целых числа, описывающих одну операцию. Их смысл и формат приведены выше в условии задачи ($1 \le x,y,a,b,c,p \le n$).

Гарантируется, что, если считать все рёбра $G$ неориентированными, граф будет связным (то есть образует дерево), а при выполнении операции первого типа между вершинами $x$ и $y$ существует ребро.

Выходные данные

Выведите всего $q+1$ строк. Перед первой операцией и после каждой операции определите, могут ли все вершины, кроме $k$, достичь вершины $k$ по текущим ориентированным рёбрам. Если могут, выведите YES, иначе выведите NO.

Примеры

Входные данные 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

Выходные данные 1

YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO

Входные данные 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

Выходные данные 2

YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO