Граф? Ви впевнені?

Спочатку є $n$ вершин і немає жодних ребер. Кожне додане ребро має ціле число $c_i$ на ньому. Ми визначаємо простий шлях між двома вершинами $a$ та $b$, які належать до однієї компоненти, як найкоротший шлях від $a$ до $b$. Розглянемо простий шлях між двома вершинами як гарний, якщо кожне значення на цьому шляху має парну кількість входжень. Вам потрібно відповісти на $q$ запитів $4$ типів:

• $1uvc$ ($1\le c\le 4\cdot 10^9$) — додати ребро, яке з'єднує вершини $u$ та $v$ зі значенням $c$ на ньому

• $2uv$ — сказати, чи є простий шлях між вершинами $u$ та $v$ гарним. Якщо між ними немає шляху, виведіть $-1$

• $3u$ — сказати кількість пар вершин $a$ та $b$ ($1\le a<b\le n$), таких що вони належать до однієї компоненти з $u$ та простий шлях між ними вважається гарним

• $4$ — сказати кількість пар вершин $a$ та $b$ ($1\le a<b\le n$), таких що простий шлях між ними вважається гарним, і існує шлях від $a$ до $b$.

Гарантується, що в усіх запитах першого типу ребро з'єднує дві різні компоненти.

Вхідні дані

Перший рядок містить два цілі числа $n$ ($1\le n\le 2\cdot 10^5$) та $q$ ($1\le q\le 2\cdot 10^5$) — кількість вершин та запитів відповідно.

Кожен з наступних $q$ рядків містить опис запиту. Перше ціле число $t_i$ визначає тип запиту.

• $t_i=1$ визначає запит першого типу і за ним йдуть $3$ цілі числа $u$, $v$ ($1\le u\ne v\le n$), $c$ ($1\le c\le 4\cdot 10^9$)

• $t_i=2$ визначає запит другого типу і за ним йдуть $2$ цілі числа $u$, $v$ ($1\le u,v\le n$)

• $t_i=3$ визначає запит третього типу і за ним йде $1$ ціле число $u$ ($1\le u\le n$)

• $t_i=4$ визначає запит четвертого типу.

Вихідні дані

Для кожного запиту другого типу виведіть

• -1, якщо простого шляху не існує

• YES, якщо простий шлях вважається гарним

• NO в іншому випадку.

Для кожного запиту третього або четвертого типу виведіть одне ціле число — відповідь на відповідний запит.

Відповіді на запити повинні бути виведені в тому ж порядку, в якому вони з'являються у вхідних даних.

Приклади

Оцінювання

1. ($5$ балів): для всіх $t_i=1$ $u_i=1$;

2. ($5$ балів): $n,q\le 20$;

3. ($7$ балів): $n,q\le 1000$;

4. ($3$ бали): $t_i\le t_{i+1}$, $t_i\le 2$, $c=1$;

5. ($6$ балів): $t_i\le t_{i+1}$, $t_i\le 2$, $c\le 8$;

6. ($11$ балів): $t_i\le t_{i+1}$, $t_i\le 2$;

7. ($9$ балів): $q=n$, $t_i=1$ для $1\le i<n$, $t_q=4$;

8. ($17$ балів): існує ціле число $e$ таке, що всі $t_i=1$ для всіх $1\le i\le e$, і для всіх $e<j\le q$ $t_i\ne 1$;

9. ($9$ балів): $c\le 1000$, граф та тести генеруються випадковим чином, тобто для кожної вершини $v$ ($2\le v\le n$) ми випадково вибираємо $p_v$ ($1\le p_v<v$), потім ми генеруємо випадкову перестановку $perm$ та робимо $v=per{m}_v$, $p_v=per{m}_{p_v}$. Тип запиту вибирається випадково (ми не виберемо перший тип, якщо немає ребер для додавання). Усі значення в запитах вибираються випадково;

10. ($28$ балів): без додаткових обмежень.