Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

2-sat

dfs and similar

dsu

graphs

trees

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Words on Tree

time limit per test

9 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputYou 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

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.

Examples

Input

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

Output

YES abc

Input

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

Output

NO

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

Output

YES baaaaaaaaa

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

Output

NO

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2024 19:02:00 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|