Description:
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.
Input Format:
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 Format:
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.
Note:
None