У Фермера Джона имеется \(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\)-го обновления.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) и
\(Q\). Каждая из последующих
\(Q\) строк содержит обновление
одного из видов
D x
A x y
R e
Гарантируется, для обновления типа R что \(e\) не более количества дорог, которые
были добавлены и никакие две команды R не будут иметь одно и то же значение \(e\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N\) строк, каждая из которых содержит одно целое число в интервале \(0\ldots Q\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|