该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

现在有一棵结点数为 $n$ 的二叉树，每个结点从 $1$ 到 $n$ 进行编号，编号为 $1$ 的结点是根结点。

你具有权重分配权，你手里有 $1,2,\cdots,n-1,n$ 共 $n$ 个可分配的权重。你需要将所有权重一一分配到二叉树的每一个结点上，分配结果要满足以下条件：

• 每个权重只能分配给一个结点；
• 每个结点都要被分配权重；
• 每个结点的权重要大于其左右孩子的权重（如果有孩子的话）；
• 同一结点的左右孩子中，左孩子的权重小于右孩子的权重（如果有孩子的话）。

完成分配后，请你输出每个结点所分配的权值。

如果无法分配，请输出 $-1$ 。

二叉树：二叉树是每个节点最多有两个子树的树结构。

输入格式

第一行是一个整数 $n$ $(1\leq n\leq 10^5)$ ，代表该二叉树的结点个数。

接下来 $n-1$ 行，每行有两个整数 $x,y$ $(1\leq x,y\leq n)$ 以及一个字母 $c$ (L 或 R)，代表 $x$ 与 $y$ 之间有一条边，且 $x$ 是 $y$ 的父节点，$y$ 是 $x$ 的儿子。当 $c$ 为 L 时，代表 $y$ 是 $x$ 的左儿子；当 $c$ 为 R 时，代表 $y$ 是 $x$ 的右儿子。

输入的数据确保是一棵合法的二叉树。

输出格式

输出 $n$ 个用空格隔开的整数，第 $i$ 个整数代表 $i$ 号结点所分配的权值。

答案可能不唯一，满足题目条件即可。

样例

5
1 3 R
1 5 L
5 2 L
5 4 R

5 1 4 2 3

5
1 2 L
1 4 R
2 3 L
2 5 R

5 3 1 4 2

限制与提示

• 样例一，树的结构以及每个点所分配权值如下：