Critical Leaf Nodes in a Two‐Player Game Tree

In a deterministic two‐player game with perfect information, the game tree is a rooted tree in which each node represents a game state. If node B is a child of node A, then a decision at state A can lead to state B. At every node exactly one player makes a decision, and the two players (called Black and White) alternate their moves along any branch of the tree; that is, two adjacent nodes in the tree always belong to different players. In this problem the final outcome of every game is a win for Black or a win for White (draws do not occur).

The root’s decision maker is Black. At every node the outcome is determined by the following rules. Suppose a node has children and let \(P\) be the decision maker at that node. Then:

• If \(P = \text{Black}\): the state is a win for Black if and only if at least one of its children is a win for Black.
• If \(P = \text{White}\): the state is a win for White if and only if at least one of its children is a win for White.

If the outcomes of all the leaf nodes were known, it would be straightforward to determine the winner at the root by propagating the results upward. Here, however, the outcomes of the leaves are unknown and have to be decided.

For a given set \(S\) of leaf nodes, if by assigning the win for Black to every leaf in \(S\> it can be deduced that the root becomes a win for Black, then we call \(S\) a Black winning set. Among all Black winning sets, one with minimum cardinality is called a minimal Black winning set. Similarly, minimal White winning sets are defined.

A leaf node which appears in both some minimal Black winning set and some minimal White winning set is termed a critical leaf node. Given a game tree, your task is to identify all critical leaf nodes.

Note on the decision process:

• For a leaf node \(v\), if we assign it a win for a player \(P\), the cost is \(1\) (i.e. one leaf is used).
• For an internal node whose decision maker is \(P\), the minimal cost to secure a win for \(P\) is the minimum among the costs of its children when evaluated for \(P\).
• For an internal node where the decision maker is not \(P\), the minimal cost is the sum of the minimal costs of all its children (since every branch is required to aid in forcing a win for \(P\)).

You need to compute, for each player (Black and White), a minimal winning set of leaves (i.e. a set of leaves with minimum possible size which secures a win for that player at the root) and then report the list of leaf nodes that occur in both some minimal Black winning set and some minimal White winning set. Output these leaf indices in increasing order, separated by spaces.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of nodes in the tree. The nodes are numbered from 1 to \(n\), with node 1 being the root.

Then \(n\) lines follow. Each line describes a node in the following format:
role k child1 child2 ... child_k

Here:

• role is a single character: either B (Black) or W (White), indicating which player makes the decision at that node.
• k is an integer (\(k \ge 0\)) indicating the number of children of this node. If k = 0, the node is a leaf.
• If k > 0, then child1, child2, ..., child_k are the indices of the children of that node.

outputFormat

Output a single line containing the indices of all critical leaf nodes (that is, leaf nodes which can belong to a minimal winning set for both Black and White) in increasing order, separated by a single space.

sample

7
B 2 2 3
W 2 4 5
W 2 6 7
B 0
B 0
B 0
B 0

4 5 6 7