가희와 쓰레기 놀이

가희는 친구들과 함께 쓰레기 수집 놀이를 하고 있습니다. 이 놀이를 이해하는 데 필요한 용어를 설명하겠습니다.

[그림 1-1(좌), 그림 1-2 (우)] object 1에서 object 2로 연결하는 연결 관계

먼저 연결 관계란 object에서 object를 연결하는 관계를 의미합니다. 예를 들어, [그림 1-1], [그림 1-2]는 object 1에서 object 2로 연결하는 관계를 나타냅니다. 연결 관계는 약한 연결 관계와, 강한 연결 관계가 있습니다. 이 중, object 1에서 object 2로 연결하는 약한 연결 관계는 [그림 1-1]에, 1에서 2로 연결하는 강한 연결 관계는 [그림 1-2]에 표시되어 있습니다.

가희와 친구들이 수행할 수 있는 연산에 대한 설명은 아래와 같습니다.

• M
  • root로부터 강한 연결 관계를 통해서만 도달할 수 있는 object만 남기고 나머지 object를 모두 제거합니다.
• m
  • root로부터 강한 연결, 혹은 약한 연결 관계를 통해서 도달할 수 있는 object만 남기고 나머지 object를 모두 제거합니다.
• MADE object_id is_root
  • id가 object_id인 object를 추가합니다. is_root의 값이 ROOT이면 해당 object는 root임을 의미합니다.
• ADD ref_id object_id_1 -> object_id_2
  • object_id가 object_id_1인 객체에서 object_id가 object_id_2인 객체를 연결하는, 연결 관계 id가 ref_id인 약한 연결 관계를 추가합니다.
• ADD ref_id object_id_1 => object_id_2
  • object_id가 object_id_1인 객체에서 object_id가 object_id_2인 객체를 연결하는, 연결 관계 id가 ref_id인 강한 연결 관계를 추가합니다.
• REMOVE ref_id
  • 연결 관계 id가 ref_id인 연결 관계를 제거합니다.

M과 m 연산이 일어날 때마다, 놀이에 있는 모든 object에 대해, root로부터 도달이 가능한지를 판단하게 됩니다. root에서 object x가 도달 가능하다는 것은, 아래 조건 중 하나 이상을 만족합니다.

• object x는 root입니다.
• root에서 조건을 만족하는 연결 관계를 거쳐서 object x에 도달할 수 있습니다.

[그림 2-1 (좌), 그림 2-2 (우)]

[그림 2-1], [그림 2-2]에서 root는 노란색으로 칠해져 있습니다. [그림 2-1]은 1에서 2로 연결하는 강한 연결 관계와 2에서 3으로 연결하는 강한 연결 관계가 있음을 나타냅니다. root로부터 도달 가능한 object는 1, 2, 3입니다. [그림 2-2]는 1에서 2로 연결하는 강한 연결 관계와 2에서 3으로 연결하는 약한 연결 관계가 있음을 나타냅니다. 강한 연결 관계나 약한 연결 관계를 통해서 root로부터 도달 가능한 object는 1, 2, 3입니다. 하지만, 강한 연결 관계를 통해서만 도달할 수 있는 object는 1과 2뿐입니다. root인 1에서 root가 아닌 3으로 가기 위해서는 2에서 3으로 연결하는 약한 연결 관계를 반드시 통해야 하기 때문입니다.

이 놀이의 규칙은 다음과 같습니다.

• 게임이 시작되기 전에는 생성된 object 중에 root 역할을 하는 object가 있을 수도 없을 수도 있습니다.
• 게임이 시작되기 전에는 object와 object를 연결하는 어떠한 연결 관계도 존재하지 않습니다.
• 가희와 친구들은 게임이 진행되는 동안 여러 연산을 할 수 있습니다.

object가 제거될 때, 제거된 object로부터 다른 object를 연결하는 연결 관계와 다른 object에서 제거된 object, 그리고 제거된 object로부터 제거된 object로 연결되는 연결 관계들이 모두 제거됩니다. 게임을 시작하기 전 생성된 object들과 게임 중에 가희와 친구들이 한 연산들이 시간 순서대로 주어집니다. 가희와 친구들이 연산을 수행할 때마다, 연산을 수행하고 남은 object의 수를 출력해 주세요.

첫 번째 줄에 게임이 시작되기 전 생성된 object의 개수 O와 게임에서 가희와 친구들이 수행한 연산의 개수 E가 공백으로 구분되어 주어집니다.

다음 O개의 줄에는 object_id와 is_root가 공백으로 구분되어 주어집니다.

이때 is_root는 해당 object가 root라면 ROOT, 아니라면 -로 주어지며, 주어지는 object_id는 모두 다릅니다.

다음 E개의 줄에는 문제에서 설명한 연산 중 하나가 발생한 시간 순서대로 주어집니다.

M과 m 연산이 주어질 때마다 해당 연산을 수행하고 난 후에 남아 있는 object의 개수를 한 줄에 하나씩 출력해 주세요.

• 1 ≤ O ≤ 2 × 105
• 1 ≤ E ≤ 2 × 105
• 객체 id가 object_id인 객체가 생성된 상태에서 id가 object_id인 객체를 생성하는 연산은 주어지지 않습니다.
• 연결 번호 ref_id인 연결 관계가 생성된 상태에서 연결 번호가 ref_id인 연결 관계를 생성하는 연산은 주어지지 않습니다.
• 연결 번호 ref_id인 연결 관계가 없는 상태에서 연결 번호가 ref_id인 연결 관계를 삭제하는 연산은 주어지지 않습니다.
• object_id_1과 object_id_2를 연결하는 연결 관계를 추가할 때 객체 고유 번호가 object_id_1인 object와 고유 번호가 object_id_2인 object는 항상 존재합니다. 
• 1 ≤ 연산 M과 m을 하는 횟수의 총합 ≤ 20
• object_id와 ref_id는 1 이상 109 이하 정수입니다.
• 놀이가 시작되기 전 생성 되어 있는 O개의 객체 고유 번호는 중복되지 않습니다. 

root가 없는 경우가 있거나, 자신이 자신을 가리키는 self-loop가 있는 경우도 있음을 조심하세요.