CF513D1 Constrained Tree

你需要找到一个大小为 $n$ 的二叉树，使其满足给定的 $c$ 个约束条件。假设未知二叉树的节点按照先序遍历的顺序从 $1$ 开始编号。对于第 $i$ 个约束，给定两个编号 $a_{i}$ 和 $b_{i}$，以及一个方向（左或右）。如果方向为左，则 $b_{i}$ 是以 $a_{i}$ 的左孩子为根的子树中的某个节点；如果方向为右，则 $b_{i}$ 是以 $a_{i}$ 的右孩子为根的子树中的某个节点。

输入的第一行包含两个整数 $n$ 和 $c$。接下来的 $c$ 行，每行包含两个整数 $a_{i}$、$b_{i}$（$1 \leq a_{i}, b_{i} \leq n$）以及一个字符串 "LEFT" 或 "RIGHT"，表示 $b_{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$。

输出为一行。 输出任意一个满足所有约束条件的二叉树的中序遍历结果。中序遍历结果应为 $n$ 个用空格分隔的节点编号，节点编号为先序编号。 如果不存在满足条件的二叉树，输出 "IMPOSSIBLE"（不带引号）。

以第一个样例测试为例。我们需要找到一个有 $3$ 个节点的二叉树，满足以下两个约束：编号为 $2$ 的节点在编号为 $1$ 的节点的左子树中；编号为 $3$ 的节点在编号为 $1$ 的节点的右子树中。只有一种满足这些约束的三节点二叉树，其中序遍历为 $(2,1,3)$。 先序遍历顺序为“根–左子树–右子树”。中序遍历顺序为“左子树–根–右子树”。 关于中序遍历和先序遍历的更多信息，请参见 [http://en.wikipedia.org/wiki/Tree\_traversal](http://en.wikipedia.org/wiki/Tree_traversal)。 由 ChatGPT 4.1 翻译