codeforces#P1657F. Words on Tree
Words on Tree
Description
You are given a tree consisting of vertices, and triples , where and are integers from to , and is a string with length equal to the number of vertices on the simple path from to .
You want to write a lowercase Latin letter on each vertex in such a way that, for each of given triples, at least one of the following conditions holds:
- if you write out the letters on the vertices on the simple path from to in the order they appear on this path, you get the string ;
- if you write out the letters on the vertices on the simple path from to in the order they appear on this path, you get the string .
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 and (; ) — the number of vertices in the tree and the number of triples, respectively.
Then lines follow; the -th of them contains two integers and (; ) — the endpoints of the -th edge. These edges form a tree.
Then lines follow; the -th of them contains two integers and , and a string consisting of lowercase Latin letters. The length of is equal to the number of vertices on the simple path between and .
Additional constraint on the input: .
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 lowercase Latin letters in the second line; the -th character of the string should be the letter you write on the -th vertex. If there are multiple answers, print any of them.
Input
The first line contains two integers and (; ) — the number of vertices in the tree and the number of triples, respectively.
Then lines follow; the -th of them contains two integers and (; ) — the endpoints of the -th edge. These edges form a tree.
Then lines follow; the -th of them contains two integers and , and a string consisting of lowercase Latin letters. The length of is equal to the number of vertices on the simple path between and .
Additional constraint on the input: .
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 lowercase Latin letters in the second line; the -th character of the string should be the letter you write on the -th vertex. If there are multiple answers, print any of them.