Дано орієнтований граф $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