농장 업데이트

Farmer John은 $N$개의 농장을 운영한다 ($1\le N\le 10^5$). 농장에는 $1\ldots N$의 번호가 붙어 있다. 처음에는 농장 사이를 잇는 도로가 하나도 없고, 모든 농장이 우유를 생산하고 있다.

경제 상황이 변하기 때문에 Farmer John은 $Q$개의 업데이트 연산 ($0\le Q\le 2\cdot 10^5$)을 순서대로 수행해야 한다. 업데이트 연산은 다음 세 가지 형태 중 하나이다.

• (D x) 활성 상태인 농장 $x$를 비활성화한다. 그러면 $x$는 더 이상 우유를 생산하지 않는다.
• (A x y) 활성 상태인 두 농장 $x$와 $y$ 사이에 도로를 추가한다.
• (R e) 이전에 추가된 $e$번째 도로를 제거한다 ($e = 1$은 처음 추가된 도로이다).

우유를 생산하고 있거나, 도로를 따라 이동해 다른 활성 농장에 도달할 수 있는 농장 $x$를 "관련 있는" 농장이라고 한다. 각 농장 $x$에 대해, $i$번째 업데이트 이후 $x$가 관련 있는 최대 $i$ ($0\le i\le Q$)를 구하시오.

첫째 줄에 $N$과 $Q$가 주어진다. 다음 $Q$개의 줄에는 다음 형태 중 하나의 업데이트가 주어진다.

D x
A x y
R e

R 형태의 업데이트에서 $e$는 지금까지 추가된 도로의 개수 이하이고, 두 R 형태 업데이트가 같은 $e$ 값을 갖지 않음이 보장된다.

$N$개의 줄을 출력한다. 각 줄에는 $0\ldots Q$ 범위의 정수를 하나씩 출력한다.

이 예제에서 도로는 $(2,3), (1,2), (2,4)$ 순서로 제거된다.

• 농장 $1$은 $(1,2)$가 제거되기 직전까지 관련 있다.
• 농장 $2$는 $(2,4)$가 제거되기 직전까지 관련 있다.
• 농장 $3$은 $(2,3)$이 제거되기 직전까지 관련 있다.
• 농장 $4$와 $5$는 모든 질의 이후에도 활성 상태이다. 따라서 둘 다 계속 관련 있고, 둘의 출력은 $Q$이다.