가희와 쓰레기 놀이

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

[그림 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에서 object_id가 object_id_2인 object를 잇는, 연결 관계 id가 ref_id인 약한 연결 관계를 추가합니다.
• ADD ref_id object_id_1 => object_id_2
  • object_id가 object_id_1인 object에서 object_id가 object_id_2인 object를 잇는, 연결 관계 id가 ref_id인 강한 연결 관계를 추가합니다.
• REMOVE ref_id
  • 연결 관계 id가 ref_id인 연결 관계를 제거합니다.

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

• 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 \le O \le 2 \times 10^5$
• $1 \le E \le 2 \times 10^5$
• object_id인 object가 이미 생성되어 있는 상태에서 같은 object_id의 object를 생성하는 연산은 주어지지 않습니다.
• ref_id인 연결 관계가 이미 생성되어 있는 상태에서 같은 ref_id의 연결 관계를 생성하는 연산은 주어지지 않습니다.
• ref_id인 연결 관계가 없는 상태에서 그 연결 관계를 삭제하는 연산은 주어지지 않습니다.
• object_id_1과 object_id_2를 잇는 연결 관계를 추가할 때, object_id_1인 object와 object_id_2인 object는 항상 존재합니다.
• M과 m 연산을 하는 횟수의 총합은 $1$ 이상 $20$ 이하입니다.
• object_id와 ref_id는 $1$ 이상 $10^9$ 이하의 정수입니다.
• 게임 시작 전에 생성되어 있는 O개의 객체 고유 번호는 중복되지 않습니다.

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