#P18669. Puzzle: Kusabi
Puzzle: Kusabi
Puzzle: Kusabi
“随机猜测每个符号所对应的含义,成功的概率只有 16.7%。”——Freddie Hand
Grammy 是一位解谜高手。今天,她正在玩一种 Kusabi 谜题的变体。
给定一棵以顶点 为根的树,树上部分顶点写有汉字标记。根顶点 没有标记。有标记的顶点可以写着“长”(输入记作 Chang)、“短”(Duan)或“同”(Tong)。你需要把所有有标记的顶点两两配对,并标记每对顶点之间最短路径上的所有边,满足:
- 每个有标记的顶点必须与另一个有标记的顶点恰好配对一次。
- 写着“长”的顶点到根的距离,必须严格大于其配对顶点到根的距离。
- 写着“短”的顶点到根的距离,必须严格小于其配对顶点到根的距离。
- 写着“同”的顶点到根的距离,必须等于其配对顶点到根的距离。
- 树上的每条边至多被标记一次。
这里距离是树上路径的边数。限制针对边,路径可以经过同一个顶点。每对的两个端点都必须满足各自标记的要求。
下面第一张是只有线索的原题图,第二张是一个可行解。红色边表示被某对顶点的路径标记的边。


Grammy 当然知道如何解开这个谜题,不过她决定考考你。请你求出一个解,或者判断无解。
输入格式
第一行包含一个整数 ,,表示顶点数。
接下来 行,每行包含两个整数 和一个字符串 ,表示顶点 与 之间有一条边,且顶点 的标记类型为 。其中
$$1\le p_i<i\le n,\qquad t_i\in\{\texttt{Chang},\texttt{Duan},\texttt{Tong},\texttt{-}\}.$$- 表示该顶点没有标记。保证这些行按 的顺序给出。保证至少有一个有标记的顶点;根顶点 没有标记。
输出格式
如果不存在解,输出一行 NO。
否则第一行输出 YES,随后每行输出两个整数 ,表示一对配对顶点。输出必须使所有有标记的顶点恰好出现一次,并满足所有条件。如果存在多个解,输出任意一个。
样例输入 1
8
2 1 -
3 1 -
4 2 Tong
5 2 Tong
6 3 Duan
7 3 -
8 7 Chang
样例输出 1
YES
6 8
5 4
样例输入 2
10
2 1 Duan
3 2 Duan
4 2 -
5 4 Chang
6 2 Chang
7 1 Duan
8 6 Tong
9 6 Tong
10 3 Chang
样例输出 2
YES
9 8
3 10
2 6
7 5