401569: GYM100495 A Crystals

Magicians at our University want to be alchemists. They work with crystals - they can mix some set of crystals and get another set of crystals. Of course, it is needed that these changes comply with the rules because to change the set of crystals would be impossible otherwise even for magicians!

As in real life, a lot of work is needed to do to change sets of crystals. Therefore, each rule has a fixed amount of work it requires to apply.

Magicians buy potato chips and find some magical crystals in the packages. There can't exist more than one crystal of the same type, because the stronger crystal of the same type consumes the weaker and, finally, the one crystal is left.

There is a special set of crystals called "the dream set". When magician owns all crystals of the dream set and nothing more, he is very proud of that (equally to a kid who collects all puponauts).

You are given the set magician owns initially, the dream set and the rules. You need to answer whether it is possible to get only the dream set and to print the minimal needed amount of work to get it. They will decide themselves if it is worth doing.

Notes:

• a magician can pick all his set or only a part of it when applying the rules, while he should get exactly the dream set in the end;
• a magician can apply any number of rules and as many times as he likes.

For example, if he owns crystals {1, 2, 3} and the rule is that we can change {2, 3} to {3, 4}, the magician can get {1, 3, 4} if he wants. But that would not satisfy him if the dream set was {1, 4}.

The first line contains the number of test cases T (1 ≤ T ≤ 50).

In the first line of every test case there are two integers n (1 ≤ n ≤ 12) and m (1 ≤ m ≤ 1000) - the number of different types of crystals and the number of rules.

The set of crystals is described with the number of its elements size (1 ≤ size ≤ n) and then size number of distinct integers, which shows the types of crystals belonging to the set (0 ≤ type ≤ n - 1). All numbers are separated by spaces.

In the second line of every test case there is an initial set of crystals owned by a magician.

In the the third line there is the dream set.

In the following m lines the rules are described as “work S1 S2” - (1 ≤ work ≤ 10⁹), S1 and S2 are the sets of crystals. The integer amount of work is needed to be done to change the set S1 to the set S2.

For each test case output one line containing “Case #tc: YES work” or “Case #tc: NO” where tc is the number of the test case (starting from 1), “YES” or “NO” shows whether is it possible to get the dream set of crystals and work is the minimal amount of work which is needed to be done to get this set.

2
1 1
1 0
1 0
1 1 0 1 0
3 1
2 0 1
1 2
1000000000 1 1 1 2

Case #1: YES 0
Case #2: NO