codeforces#P1657F. Words on Tree

Words on Tree

Description

You are given a tree consisting of nn vertices, and qq triples (xi,yi,si)(x_i, y_i, s_i), where xix_i and yiy_i are integers from 11 to nn, and sis_i is a string with length equal to the number of vertices on the simple path from xix_i to yiy_i.

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

  • if you write out the letters on the vertices on the simple path from xix_i to yiy_i in the order they appear on this path, you get the string sis_i;
  • if you write out the letters on the vertices on the simple path from yiy_i to xix_i in the order they appear on this path, you get the string sis_i.

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

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

Then n1n - 1 lines follow; the ii-th of them contains two integers uiu_i and viv_i (1ui,vin1 \le u_i, v_i \le n; uiviu_i \ne v_i) — the endpoints of the ii-th edge. These edges form a tree.

Then qq lines follow; the jj-th of them contains two integers xjx_j and yjy_j, and a string sjs_j consisting of lowercase Latin letters. The length of sjs_j is equal to the number of vertices on the simple path between xjx_j and yjy_j.

Additional constraint on the input: j=1qsj4105\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 nn lowercase Latin letters in the second line; the ii-th character of the string should be the letter you write on the ii-th vertex. If there are multiple answers, print any of them.

Input

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

Then n1n - 1 lines follow; the ii-th of them contains two integers uiu_i and viv_i (1ui,vin1 \le u_i, v_i \le n; uiviu_i \ne v_i) — the endpoints of the ii-th edge. These edges form a tree.

Then qq lines follow; the jj-th of them contains two integers xjx_j and yjy_j, and a string sjs_j consisting of lowercase Latin letters. The length of sjs_j is equal to the number of vertices on the simple path between xjx_j and yjy_j.

Additional constraint on the input: j=1qsj4105\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 nn lowercase Latin letters in the second line; the ii-th character of the string should be the letter you write on the ii-th vertex. If there are multiple answers, print any of them.

Samples

输入数据 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