CF513D2 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 \le a_i, b_i \le n$）以及一个字符串 "LEFT" 或 "RIGHT"，表示 $b_i$ 在 $a_i$ 的左子树或右子树中。 题目分为多个子问题，根据不同的输入限制来计算得分： - 子问题 D1（9 分）：$1 \le n \le 100$，$1 \le c \le 50$。 - 子问题 D2（8 分）：$1 \le n \le 1000000$，$1 \le c \le 100000$。

输出为一行，即一个满足所有约束条件的二叉树的中序遍历节点编号，编号之间用空格分开。如果不存在满足条件的二叉树，请输出 `IMPOSSIBLE`。

考虑一个例子：找一棵有 3 个节点的树，满足两个条件：节点 2 要在节点 1 的左子树中，节点 3 要在节点 1 的右子树中。唯一符合条件的树的中序遍历结果是 $(2, 1, 3)$。 前序遍历顺序是“根-左子树-右子树”，中序遍历是“左子树-根-右子树”。 想了解更多关于遍历的信息，可以访问 [Tree Traversal on Wikipedia](http://en.wikipedia.org/wiki/Tree_traversal)。 **本翻译由 AI 自动生成**