CF513D2.Constrained Tree

You need to find a binary tree of size n that satisfies a given set of c constraints. Suppose that the nodes of the unknown binary tree are labeled using a pre-order traversal starting with 1. For the i-th constraint you are given two labels, a__i and b__i and a direction, left or right. In case of left direction, b__i is an element of the subtree rooted at a__i's left child. Similarly in the case of right direction b__i is an element of the subtree rooted at a__i's right child.

你需要构造一棵大小为 $n$ 的二叉树，使其满足给定的 $c$ 个约束条件。假设该未知二叉树的节点按照先序遍历顺序标号，起始编号为 $1$。对于第 $i$ 个约束，你将获得两个标号 $a_i$ 和 $b_i$，以及一个方向（left 或 right）。若方向为 left，则 $b_i$ 必须属于以 $a_i$ 的左子节点为根的子树中的某个节点；类似地，若方向为 right，则 $b_i$ 必须属于以 $a_i$ 的右子节点为根的子树中的某个节点。

The first line of input contains two integers n and c. The next c lines contain 2 integers a__i, b__i (1 ≤ a__i, b__i ≤ n) and either "LEFT" or "RIGHT" denoting whether b is in the subtree rooted at a__i's left child or in the subtree rooted at a__i's right child.

The problem consists of multiple subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem D1 (9 points), the constraints 1 ≤ n ≤ 100, 1 ≤ c ≤ 50 will hold.
• In subproblem D2 (8 points), the constraints 1 ≤ n ≤ 1000000, 1 ≤ c ≤ 100000 will hold.

输入的第一行包含两个整数 $n$ 和 $c$。接下来的 $c$ 行每行包含两个整数 $a_i$、$b_i$（满足 $1 \leq a_i, b_i \leq n$）以及字符串 "LEFT" 或 "RIGHT"，表示节点 $b_i$ 位于以 $a_i$ 的左子节点为根的子树中，还是位于以 $a_i$ 的右子节点为根的子树中。

本题包含多个子问题。各子问题对输入的约束条件不同。你将根据正确解决各个子问题的情况获得相应分数。各子问题的描述如下：

• 子问题 D1（9 分）：约束条件为 $1 \leq n \leq 100$，$1 \leq c \leq 50$。
• 子问题 D2（8 分）：约束条件为 $1 \leq n \leq 1000000$，$1 \leq c \leq 100000$。

Output will be on a single line.

Any binary tree that satisfies the constraints will be accepted. The tree's nodes should be printed out as n space separated labels representing an in-order traversal, using the pre-order numbers as labels of vertices.

If there are no trees that satisfy the constraints, print "IMPOSSIBLE" (without quotes).

输出在一行内。

任何满足约束条件的二叉树均可接受。树的节点应以中序遍历顺序打印，输出为 n 个用空格分隔的标签，这些标签即为各顶点的先序编号。

若不存在满足约束条件的树，则输出 "IMPOSSIBLE"（不带引号）。

Consider the first sample test. We need to find a tree with 3 nodes that satisfies the following two constraints. The node labeled 2 with pre-order traversal should be in the left subtree of the node labeled 1 with pre-order traversal; the node labeled 3 with pre-order traversal should be in the right subtree of the node labeled 1. There is only one tree with three nodes that satisfies these constraints and its in-order traversal is (2, 1, 3).

Pre-order is the "root – left subtree – right subtree" order. In-order is the "left subtree – root – right subtree" order.

For other information regarding in-order and pre-order, see http://en.wikipedia.org/wiki/Tree_traversal.

考虑第一个样例测试。我们需要找到一棵包含 3 个节点的树，使其满足以下两个约束条件：在先序遍历中编号为 2 的节点应位于编号为 1 的节点的左子树中；在先序遍历中编号为 3 的节点应位于编号为 1 的节点的右子树中。唯一满足这些约束条件的三节点树，其中序遍历结果为 $(2,\,1,\,3)$。

先序遍历的顺序是“根节点 – 左子树 – 右子树”；中序遍历的顺序是“左子树 – 根节点 – 右子树”。

有关中序遍历和先序遍历的其他信息，请参见 http://en.wikipedia.org/wiki/Tree_traversal。