CF1657F.Words on Tree

You are given a tree consisting of $n$ vertices, and $q$ triples $(x_i, y_i, s_i)$, where $x_i$ and $y_i$ are integers from $1$ to $n$, and $s_i$ is a string with length equal to the number of vertices on the simple path from $x_i$ to $y_i$.

You want to write a lowercase Latin letter on each vertex in such a way that, for each of $q$ given triples, at least one of the following conditions holds:

• if you write out the letters on the vertices on the simple path from $x_i$ to $y_i$ in the order they appear on this path, you get the string $s_i$;
• if you write out the letters on the vertices on the simple path from $y_i$ to $x_i$ in the order they appear on this path, you get the string $s_i$.

Find any possible way to write a letter on each vertex to meet these constraints, or report that it is impossible.

给你一棵包含 $n$ 个顶点的树，以及 $q$ 个三元组 $(x_i, y_i, s_i)$，其中 $x_i$ 和 $y_i$ 是介于 $1$ 到 $n$ 之间的整数，$s_i$ 是一个字符串，其长度等于从 $x_i$ 到 $y_i$ 的简单路径上的顶点数目。

你需要在每个顶点上写一个小写拉丁字母，使得对每个给定的三元组，以下两个条件中至少有一个成立：

• 若将从 $x_i$ 到 $y_i$ 的简单路径上各顶点所写字母按路径顺序写出，则得到字符串 $s_i$；
• 若将从 $y_i$ 到 $x_i$ 的简单路径上各顶点所写字母按路径顺序写出，则得到字符串 $s_i$。

请找出一种满足上述约束的顶点赋字母方案；若不存在这样的方案，则报告无解。

The first line contains two integers $n$ and $q$ ($2 \le n \le 4 \cdot 10^5$; $1 \le q \le 4 \cdot 10^5$) — the number of vertices in the tree and the number of triples, respectively.

Then $n - 1$ lines follow; the $i$-th of them contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$) — the endpoints of the $i$-th edge. These edges form a tree.

Then $q$ lines follow; the $j$-th of them contains two integers $x_j$ and $y_j$, and a string $s_j$ consisting of lowercase Latin letters. The length of $s_j$ is equal to the number of vertices on the simple path between $x_j$ and $y_j$.

Additional constraint on the input: $\sum \limits_{j=1}^{q} |s_j| \le 4 \cdot 10^5$.

第一行包含两个整数 $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$。

If there is no way to meet the conditions on all triples, print NO. Otherwise, print YES in the first line, and a string of $n$ lowercase Latin letters in the second line; the $i$-th character of the string should be the letter you write on the $i$-th vertex. If there are multiple answers, print any of them.

如果无法满足所有三元组的条件，则输出 NO。否则，第一行输出 YES，第二行输出一个长度为 $n$ 的小写拉丁字母字符串；该字符串的第 $i$ 个字符即为写在第 $i$ 个顶点上的字母。若存在多个合法答案，输出任意一个即可。