В сказочной стране Айландлэнде правит добрый и мудрый король.
На данный момент, Айландлэнд состоит из $n$ островов, пронумерованных числами от $1$ до $n$, на каждом из которых живут жители. Никакие два острова не связаны между собой мостами, поэтому жителям приходится добираться от одного острова до другого вплавь.
Иногда на каком-то из островов происходит наводнение, и тогда все жители этого острова переселяются жить на какой-то другой остров. При этом сам остров остаётся на месте и через него можно путешествовать или переселиться на него в будущем.
Король решил начать строить мосты между островами, но строительство мостов - дело достаточно непредсказуемое. Король получает донесения двух видов:
1) В донесении первого вида сообщается, что между островами $u_i$ и $v_i$ удалось построить мост. Движение по мосту возможно в обоих направлениях.
2) В донесении второго вида сообщается, что на острове $u_i$ произошло наводнение и все его жители (если они были) переселились на остров $v_i$.
_Таким образом, каждое донесение задаётся тремя параметрами: своим типом и упорядоченной парой островов._
Королю необходимо планировать будущие расходы, поэтому после каждого донесения ему интересно знать, какое минимальное количество мостов необходимо дополнительно построить, чтобы из любого заселённого (на текущий момент) острова можно было по суше добраться до любого другого заселённого острова.
*Обратите внимание, что в задаче требуется ввести много данных!*
В первой строке записаны два целых числа $n$ и $q$ ($2 <= n <= 3 * 10^5$, $1 <= q <= 3 * 10^5$) - количество островов и количество донесений соответственно.
Следующие $q$ строк содержат по три целых числа $t_i$, $u_i$, $v_i$ - информацию об $i$-м донесении ($1 <= t_i <= 2$, $1 <= u_i, v_i <= n$).
При этом $t_i$ задаёт тип донесения ($t_i = 1$ означает, что донесение о новом мосте, а $t_i = 2$ означает, что донесение о наводнении), а $u_i$ и $v_i$ означают номера островов в тех же обозначениях, что и в условии задачи.
Гарантируется, что $u_i eq.not v_i$ для любого $i$.
Выведите $q$ чисел, где $i$-е число означает минимальное количество мостов, которое необходимо дополнительно построить, чтобы из любого заселённого острова можно было добраться по суше до любого другого заселённого острова, на момент после $i$-го донесения.
Заметим, что между двумя островами может быть построен более, чем один мост.
## Входные Данные
В первой строке записаны два целых числа $n$ и $q$ ($2 <= n <= 3 * 10^5$, $1 <= q <= 3 * 10^5$) - количество островов и количество донесений соответственно.Следующие $q$ строк содержат по три целых числа $t_i$, $u_i$, $v_i$ - информацию об $i$-м донесении ($1 <= t_i <= 2$, $1 <= u_i, v_i <= n$).При этом $t_i$ задаёт тип донесения ($t_i = 1$ означает, что донесение о новом мосте, а $t_i = 2$ означает, что донесение о наводнении), а $u_i$ и $v_i$ означают номера островов в тех же обозначениях, что и в условии задачи.Гарантируется, что $u_i eq.not v_i$ для любого $i$.
## Выходные Данные
Выведите $q$ чисел, где $i$-е число означает минимальное количество мостов, которое необходимо дополнительно построить, чтобы из любого заселённого острова можно было добраться по суше до любого другого заселённого острова, на момент после $i$-го донесения.
## Примеры
Входные данные5 5
1 1 2
1 2 3
1 1 3
1 4 5
1 1 4
Выходные данные3 2 2 1 0 Входные данные5 6
2 1 2
2 2 1
2 1 3
2 5 4
2 4 3
2 3 1
Выходные данные3 3 2 1 0 0 Входные данные9 11
1 1 2
1 3 4
1 5 6
2 6 4
2 5 3
1 7 8
1 1 8
1 5 9
2 9 5
2 1 2
2 1 3
Выходные данные7 6 5 5 4 3 2 2 2 2 2
## Примечание
Заметим, что между двумя островами может быть построен более, чем один мост.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $ be the number of solutions.
Let $ T = (T_1, T_2, \dots, T_N) $, where $ T_i \in \mathbb{Z}^+ $ is the worst-case runtime of solution $ i $.
Let $ S \in \{0, 1, ?\}^N $ be a string describing the type of each solution:
- $ S_i = 0 $: bad solution,
- $ S_i = 1 $: good solution,
- $ S_i = ? $: questionable solution.
Let $ X \in \mathbb{Z}^+ $ be a time limit.
**Constraints**
1. $ 1 \leq N \leq 1000 $
2. $ 1 \leq T_i \leq 10^6 $ for all $ i \in \{1, \dots, N\} $
3. $ 1 \leq Q \leq 1000 $
4. For each query, $ |S| = N $ and $ S_i \in \{0, 1, ?\} $
**Objective**
For each query string $ S $, find the **minimum** positive integer $ X $ such that:
- All **good** solutions satisfy $ T_i \leq X $,
- All **bad** solutions satisfy $ T_i > X $,
- **Questionable** solutions impose no constraint.
If no such $ X $ exists, output $-1$.