← 返回题目列表

Codeforces · 1657/F

F. 树上的话

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

给定一棵由 $$$n$$$ 个顶点和 $$$q$$$ 三元组 $$$(x_i, y_i, s_i)$$$ 组成的树,其中 $$$x_i$$$ 和 $$$y_i$$$ 是从 $$$1$$$ 到 $$$n$$$ 的整数,$$$s_i$$$ 是具有长度的字符串等于从 $$$x_i$$$ 到 $$$y_i$$$ 的简单路径上的顶点数。

您希望在每个顶点上写一个小写拉丁字母,对于给定的三元组中的每个 $$$q$$$,至少满足以下条件之一:

- 如果您按照在 $$$x_i$$$ 到 $$$y_i$$$ 的简单路径上出现的顺序写出顶点上的字母,您将得到字符串 $$$s_i$$$;
- 如果您按照在该路径上出现的顺序写出从 $$$y_i$$$ 到 $$$x_i$$$ 的简单路径上顶点上的字母,您将得到字符串 $$$s_i$$$。

找到任何可能的方法在每个顶点上写一个字母来满足这些约束,或者报告这是不可能的。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \le n \le 4 \cdot 10^5$$$; $$$1 \le q \le 4 \cdot 10^5$$$) — 分别是树中的顶点数和三元组数。

然后是 $$$n - 1$$$ 行;其中第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — 第 $$$i$$$ 条边的端点。这些边形成一棵树。

然后是 $$$q$$$ 行;其中第$$$j$$$包含两个整数$$$x_j$$$和$$$y_j$$$,以及一个由小写拉丁字母组成的字符串$$$s_j$$$。 $$$s_j$$$ 的长度等于 $$$x_j$$$ 和 $$$y_j$$$ 之间简单路径上的顶点数。

输入的附加约束:$$$\sum \limits_{j=1}^{q} |s_j| \le 4 \cdot 10^5$$$。

输出

如果无法满足所有三元组的条件,则打印 NO。否则,在第一行打印 YES,在第二行打印一串 $$$n$$$ 小写拉丁字母;字符串的第 $$$i$$$ 个字符应该是您在第 $$$i$$$ 个顶点上写的字母。如果有多个答案,请打印其中任何一个。

示例

输入 #1

3 2
2 3
2 1
2 1 ab
2 3 bc

输出 #1

YES
abc

输入 #2

3 2
2 3
2 1
2 1 ab
2 3 cd

输出 #2

NO

输入 #3

10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 ab
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba

输出 #3

YES
baaaaaaaaa

输入#4

10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 aa
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba

输出#4

NO