The Melancholy of Problem Setter solution codechef
Roughly speaking, this problem asks you to create the checker of the problem used in December CookOff.
You are given a tree with
For each integer
'R' is for Red,
'G' is for Green and
'B' is for Blue.
The input is called valid if for all pairs of Blue vertices simple path between and ., there is at least one Red vertex and one Green vertex on the
Your task is to validate the input for given
Yes if the input is valid, otherwise
- The first line of input contains one positive integer , the number of test cases. The description of test cases follows.
- The first line of each test case contains one positive integer , the number of vertices of the tree.
- The second line of each test case contains a string , denoting the colors of the vertices.
- Each of the following lines contains two space-separated integers and , denoting an edge between vertices and in the tree.
For each test case, output a single line containing
Yes if the input is valid, and
You may print each character of the string in uppercase or lowercase (for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be treated as identical).
- The sum of for each test case is at most
consists of three types of characters,
- The input graph forms a tree
Sample Input 1
5 4 BRGB 3 2 1 2 4 3 3 RGB 1 2 2 3 1 B 2 BB 1 2 4 BRGB 3 2 1 2 4 2
Sample Output 1
Yes Yes Yes No No
- Test case 1:
- The only pair is .
- Test case 3:
- There are no pairs.
- Test case 5:
- The only pair is . There are no Green vertices on the path between and .