У Фермера Джона є \(N\) ферм, що виробляють молоко (\(1\le N\le 10^5\)), послідовно пронумерованих \(1\ldots N\). Спочатку немає доріг, які з'єднують ці ферми.

ФД має намір зробити серію з \(Q\) змін (\(0\le Q\le 2\cdot 10^5\)) наступних видів

• D x - деактивувати ферму \(x\), отже вона перестане виробляти молоко.
• A x y - побудувати дорогу між двома активними фермами \(x\) та \(y\).
• R e - видалити \(e\)-у дорогу, яка була додана. (\(e = 1\) - перша дорога, яка була додана).

Ферма \(x\) яка активно виробляє молоко або яка досяжна від іншої активної ферми через серію доріг називається "релевантною" фермою. Для кожної ферми \(x\), обчисліть максимум \(i\) (\(0\le i\le Q\)) таких, що \(x\) релевантна після \(i\)-го оновлення.

Формат вхідних даних

Перший рядок введення містить \(N\) та \(Q\). Кожен з наступних \(Q\) рядків містить оновлення одного з видів

D x
A x y
R e

Гарантується, для оновлення типу R що \(e\) не більше кількості доріг, які були додані і жодні дві команди R не будуть мати те саме значення \(e\).

Формат вихідних даних

Виведіть \(N\) рядків, кожен з яких містить одне ціле число в інтервалі \(0 \ldots Q\).

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

5 9
A 1 2
A 2 3
D 1
D 3
A 2 4
D 2
R 2
R 1
R 3

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

7
8
6
9
9

У цьому прикладі видаляються дороги \((2,3), (1,2), (2,4)\) у такому самому порядку.

• Ферма \(1\) релевантна до того, як дорога \((1,2)\) видалена.
• Ферма \(2\) релевантна до того, як дорога \((2,4)\) видалена.
• Ферма \(3\) релевантна до того, як дорога \((2,3)\) видалена.
• Ферми \(4\) та \(5\) активні після всіх запитів. Тому обидві залишаються релевантними після всіх запитів та відповідь для обох \(Q\).

ОЦІНЮВАННЯ:

• У тестах 2 - 5 \(N≤10^3\), \(Q≤2⋅10^3\)
• У тестах 6 – 20 не додаткових обмежень.

Автор: Benjamin Qi