Існує неорієнтований граф з ~N~ вершинами, пронумерованими від 1 до ~N~, кількість ребер на початку рівна 0.

Обробіть ~Q~ запитів у порядку їх слідування. Після обробки кожного запиту виведіть кількість вершин, які не з'єднані ребром з іншими вершинами.

~I~-й запит ~q_i~ належить до одного з двох наступних типів:

– 1 ~u~ ~v~: з'єднати вершину ~u~ і вершину ~v~ ребром. Гарантується, що коли задається цей запит, вершина ~u~ та вершина ~v~ не з'єднані ребром.

– 2 ~v~: видаліть усі ребра, які з'єднують вершину ~v~ та інші вершини. (Сама вершина ~v~ не видаляється.)

Обмеження

• ~2 \le N \le 3 \cdot 10^5~
• ~1 \le Q \le 3 \cdot 10^5~
• Для кожного запиту першого типу ~1 \le u,v \le N~ і ~u \neq v~.
• Для кожного запиту другого типу ~1 \le v \le N~.
• Безпосередньо перед подачею запиту першого типу між вершинами ~u~ і ~v~ немає ребра.
• Усі значення у вхідних даних є цілими числами.

Input

Перший рядок вхідного потоку містить цілі числа ~N, Q~.

Наступні ~Q~ рядків містять запити ~q_i~.

Output

У вихідний потік вивести ~Q~ рядків. В ~i~-му рядку ~(1 \le i \le Q)~ має бути записано кількість вершин, які не з'єднані ребром з іншими вершинами.

Приклад вхідних 1:

Після першого запиту вершина 1 і вершина 2 з'єднані одна з одною ребром, але вершина 3 не з'єднана з іншими вершинами. Таким чином, 1 виводимо в першому рядку.

Після третього запиту всі пари різних вершин з'єднуються ребром.

Четвертий запит просить видалити всі ребра, які з'єднують вершину 1 та інші вершини, зокрема, видалити ребро між вершиною 1 і вершиною 2, а також між вершиною 1 і вершиною 3. У результаті вершина 2 і вершина 3 з'єднані одна з одною, тоді як вершина 1 не з'єднана ребром з іншими вершинами. Таким чином, виводимо 0 і 1 в третьому і четвертому рядках відповідно.

Sample Input 1

3 7
1 1 2
1 1 3
1 2 3
2 1
1 1 2
2 2
1 1 2

Sample Output 1

1
0
0
1
0
3
1

Sample Input 2

2 1
2 1

Sample Output 2

2