문제
농부 존은 N개의 농장(1≤N≤105)을 운영하고 있으며, 번호는 1…N입니다.
초기에는 이들 농장을 연결하는 도로가 없었고, 각 농장은 우유를 활발히 생산하고 있다.
경제의 동적 특성으로 인해 농부 존은 일련의 Q 업데이트 작업(0≤Q≤2⋅105)에 따라 농장을 변경해야 합니다.
업데이트 작업은 세 가지 가능한 형식으로 제공됩니다.
(D x) 활성 농장 x를 비활성화하여 더 이상 우유를 생산하지 않습니다.
(A x y) 두 활성 농장 x와 y 사이에 도로를 추가합니다.
(R e) 이전에 추가된 eth 도로를 제거합니다(e=1은 추가된 첫 번째 도로입니다).
우유를 적극적으로 생산하거나 일련의 도로를 통해 다른 활성 농장에 도달할 수 있는 농장 x를 "관련" 농장이라고 합니다.
각 팜 x에 대해 i번째 업데이트 이후 x가 해당되도록 최대 i(0≤i≤Q)를 계산합니다.
입력
입력의 첫 번째 줄에는 N과 Q가 포함됩니다. 다음 Q 줄에는 각각 다음 형식 중 하나의 업데이트가 포함됩니다.
D x
A x y
R e
R 유형의 업데이트에 대해 e는 지금까지 추가된 도로의 수 이하이고 R 유형의 두 업데이트는 e의 값이 동일하지 않음이 보장됩니다.
출력
각각 0…Q 범위의 정수를 포함하는 N 줄을 출력하십시오.
예제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
힌트
출처
USACO 2022 January Gold