Gahee and the Garbage Game

Gahee is playing a garbage collection game with her friends. This section explains the terms needed to understand the game.

[Figure 1-1 (left), Figure 1-2 (right)] A connection from object 1 to object 2

A connection is a relation that links one object to another. For example, [Figure 1-1] and [Figure 1-2] show relations from object 1 to object 2. There are two kinds of connections, weak and strong. Among these, the weak connection from object 1 to object 2 is shown in [Figure 1-1], and the strong connection from 1 to 2 is shown in [Figure 1-2].

Gahee and her friends can perform the following operations.

• M
  • Keeps only the objects that can be reached from the root through strong connections only, and removes all other objects.
• m
  • Keeps only the objects that can be reached from the root through strong or weak connections, and removes all other objects.
• MADE object_id is_root
  • Adds an object with id object_id. If is_root is ROOT, the object is a root.
• ADD ref_id object_id_1 -> object_id_2
  • Adds a weak connection with connection id ref_id that links the object with object_id object_id_1 to the object with object_id object_id_2.
• ADD ref_id object_id_1 => object_id_2
  • Adds a strong connection with connection id ref_id that links the object with object_id object_id_1 to the object with object_id object_id_2.
• REMOVE ref_id
  • Removes the connection with connection id ref_id.

Each time an M or m operation happens, the game checks whether every object is reachable from the root. An object x is reachable from the root if at least one of the following holds.

• Object x is a root.
• Object x can be reached from the root through connections that satisfy the condition.

[Figure 2-1 (left), Figure 2-2 (right)]

In Figure 2-1 and Figure 2-2, the root is colored yellow. Figure 2-1 has a strong connection from 1 to 2 and a strong connection from 2 to 3. The objects reachable from the root are 1, 2, and 3. Figure 2-2 has a strong connection from 1 to 2 and a weak connection from 2 to 3. The objects reachable from the root through strong or weak connections are 1, 2, and 3. However, only 1 and 2 can be reached through strong connections alone. To reach 3 from the root 1, the path must pass through the weak connection from 2 to 3.

The rules of the game are as follows.

• Before the game starts, some created objects may be a root and some may not.
• Before the game starts, there are no connections between objects.
• During the game, Gahee and her friends can perform various operations.

When an object is removed, every connection from the removed object to another object, every connection from another object to the removed object, and every connection from a removed object to a removed object are all removed. The objects created before the game and the operations performed during the game are given in chronological order. Each time Gahee and her friends perform an operation, print the number of objects remaining after the operation.

The first line contains O, the number of objects created before the game starts, and E, the number of operations performed during the game, separated by a space.

The next O lines each contain an object_id and is_root, separated by a space. is_root is ROOT if the object is a root, and - otherwise. All given object_id values are different.

The next E lines each contain one of the operations described in the problem, in chronological order.

Print the number of objects remaining after each M or m operation, one per line.

• $1 \le O \le 2 \times 10^5$
• $1 \le E \le 2 \times 10^5$
• An operation that creates an object with an object_id that already exists is not given.
• An operation that creates a connection with a ref_id that already exists is not given.
• An operation that removes a connection with a ref_id that does not exist is not given.
• When adding a connection between object_id_1 and object_id_2, the objects with those ids always exist.
• The total number of M and m operations is at least $1$ and at most $20$.
• object_id and ref_id are integers from $1$ to $10^9$.
• The $O$ object ids created before the game are not duplicated.

Be careful that there may be no root at all, and that an object may have a self-loop that points to itself.