给定一棵由 $$$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