← 返回题目列表

Codeforces · 513/D1

D1. 约束树

中文机器翻译题面 查看原题

您需要找到一个大小为 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。