您需要找到一个大小为 n 的二叉树,它满足给定的一组 c 约束。假设未知二叉树的节点使用从 1 开始的前序遍历进行标记。对于第 i 个约束,您将获得两个标签 ai 和 bi 以及一个方向(左或右)。在左方向的情况下,bi 是以 ai 的左孩子为根的子树的元素。类似地,在右方向的情况下,bi 是以 ai 的右孩子为根的子树的元素。
输入
输入的第一行包含两个整数 n 和 c。接下来的 c 行包含 2 个整数 ai、bi (1 ≤ ai, bi ≤ n) 以及“LEFT”或“RIGHT”,表示 b 是在以 ai 的左子节点为根的子树中还是在以 ai 的右子节点为根的子树中。
该问题由多个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。
- 在子问题 D1(9 点)中,约束 1 ≤ n ≤ 100、1 ≤ c ≤ 50 将成立。
- 在子问题 D2(8 点)中,约束 1 ≤ n ≤ 1000000、1 ≤ c ≤ 100000 将成立。
输出
输出将在一行上。
任何满足约束的二叉树都将被接受。树的节点应打印为 n 个空格分隔的标签,表示有序遍历,使用前序号作为顶点的标签。
如果没有满足约束的树,则打印“IMPOSSIBLE”(不带引号)。
示例
输入 #1
3 2 1 2 LEFT 1 3 RIGHT
输出 #1
2 1 3
输入 #2
3 2 1 2 RIGHT 1 3 LEFT
输出 #2
IMPOSSIBLE
注意
考虑第一个样本测试。我们需要找到一棵有 3 个节点的树,满足以下两个约束。前序遍历标记为2的节点应该在前序遍历标记为1的节点的左子树中;前序遍历的标记为 3 的节点应该位于标记为 1 的节点的右子树中。满足这些约束的三节点树只有一棵,其中序遍历为 (2, 1, 3)。
前序是“根-左子树-右子树”的顺序。中序是“左子树-根-右子树”的顺序。
有关有序和预序的其他信息,请参阅 http://en.wikipedia.org/wiki/Tree_traversal。