Challenge 24 Electronic Contest Practice

You are given a set of beads and you want to make necklaces using up all of the beads. Each bead has a color and the diameter of the hole in each bead is an integer if measured in millimeters. You also have strings with different diameters. More precisely, you have exactly one string of k millimeter for each positive integer k (but of course you do not have a string of diameter 0). A bead can be strung onto a string if the size of its hole exactly matches the thickness of the string or if the string is exactly one millimeter thinner than the hole in the bead (otherwise the bead would be to loose). But of course you also have to pay attention to aesthetics. You are given a list of pairs of colors that look really awful together. You can not put two beads on the same string if their colors do not match.

Input:

The first line contains a single integer, the number of test cases. Then the first line of each test case consists of three integers: C, the number of possible colours, P the number of incompatible color pairs and B, the number of beads. The next B lines describe the beads. The size and the color of each bead is given. Then each of the next P lines consists of two integers in the range {1, 2, ... ,C}, representing pairs of colors that do not match. From the next line the specification of the next case starts.

Output:

For each test case, you have to output a single line containing the word POSSIBLE or IMPOSSIBLE.

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

Example

Input:
2
3 3 3
3 1
3 2
3 3
1 2
1 3
2 3
2 2 0
5 1
5 2

Output:
IMPOSSIBLE
POSSIBLE