Challenge 24 Electronic Contest Practice

The Retarded Toys Inc. creates building toys for not-thattalented kids. It consists of joints and colored sticks linking the joints together. To lighten the burden on poor kids, they do not have to assemble the sticks and joints together on their own, the game comes already fully assembled. But to give a little freedom, the sticks can be turned in all possible directions, independently to each other around the joints. When assembling a toy, the machine at the factory takes one joint, then takes another one and links it to the first with a stick, then takes another one and links it to one of the joints of the already assembled part.

These games are delivered in space bending magic containers. These non-Euclidean 3D boxes contains holes for the joints and tunnels between certain pairs of holes that can contain sticks (there can be even more than one strictly straight tunnel between a pair of holes, thanks to some dark magic). Each hole and each tunnel can hold any number of joints and sticks respectively. Also, for aesthetic purposes, a set of colors is assigned to each tunnel, and only sticks with one of the given colors can be put in the given tunnel. One of the magical properties of the box is that no any Euclidean rules normally governing lengths in our universe apply to it, that is do not even think about relying on triangle inequality, Pythagoras’ theorem or anything of that sort. They just won’t necessarily hold.

The company has a very special equipment that can stuff a toy into a box if we can assign the joints to the holes so that:

• Each joint is assigned to a hole, but there are no assumptions about the number of joints assigned to a given hole whatsoever.
• If there is stick S between joints A and B, and they are assigned to holes C and D respectively, then there must be a tunnel between C and D that allows for the storage of sticks with the color of S.

How the kids are going to take the toy OUT of the box, is a completely different issue, about which we do not care the slightest bit.

Your task is to write a program, that given the specifications of a toy and a box, decides if the toy fits in the box or not.

Input

The first line contains C, the number of test cases. The following are repeated C times:

• A line containing J, the number of joints in a toy.
• The name of the first joint.
• Each of the next J - 1 lines contain three strings separated by spaces: the identifier
of the joint, the identifier of the joint it is connected to with a stick (can only be one previously mentioned) and the color of the stick.
• Two integers separated by a space: H, the number of holes and T, the number of tunnels.
• Each of the next T lines contain separated by spaces: the indices of the two holes connected by the tunnel (two integers between 0 and H - 1) and a list of allowed colors in the tunnel.

Output

C lines, each containing the word YES or NO.

This is the electronic variant of the problem. Read more here about submitting solutions!

Example

Input
2
3
first
second first red
third first blue
3 3
0 1 blue
0 2 red
1 2 green
3
first
second first red
third first blue
4 4
0 1 blue
1 2 purple
2 3 red
3 0 green
Output
YES
NO