Words on Tree

Description:

Input:

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$$$.

Output:

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.

Sample Input:

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

Sample Output:

YES
abc

Sample Input:

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

Sample Output:

NO

Sample Input:

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

Sample Output:

YES
baaaaaaaaa

Sample Input:

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

Sample Output:

NO