Gearbox

Time limit1sMemory limit128 MB

Summary

Given gears of unknown teeth counts grouped on rods and pairs of interlocked gears, decide whether every rod can turn for any assignment of teeth counts to gear types.

Level: Medium7 of 10
Topics: Graph, DFS, Union-find, Implementation
Solved: No attempts yet

Problem

Jake decided to take the gearbox of his car apart and put it back together "for learning purposes". A gearbox is a box containing many gears, cogs and sprockets (as well as several springs and pinions). All of these parts mesh together in intricate ways, so Jake is not completely sure whether every part is back in its correct position.

All gears are mounted on metal rods. When one gear on a rod turns, every gear on that rod turns by the same angle. The rods are held together by springs and plastic bars, and Jake is confident he got that part right. The cogs and sprockets, on the other hand, are not connected to anything — they are free to rattle around inside the box.

The only problem is that some gears are interlocked, which could cause the main drive shaft to jam. These gears use modern InfiniTeeth technology, so it is impossible to count the number of teeth on a gear. Instead, every gear has a type number, and gears of the same type have the same number of teeth. According to the manual, all rods must be able to turn regardless of how many teeth each gear type has. Jake therefore concludes that if this holds for his gearbox, then it is definitely assembled correctly.

When two gears are interlocked, their rods turn in opposite directions, and the angular speeds are inversely proportional to the teeth counts. For example, if two rods carry three gears and the two upper gears are interlocked, the rods spin in opposite directions; if one gear has 36 teeth and the gear it meshes with has 24 teeth, then the rod holding the 24-tooth gear turns 1.5 times faster.

Input

The first line contains a positive integer: the number of test cases. Each test case is given as follows:

A line with three integers $n_g$ , $n_r$ and $n_i$ (all $< 10^5$ ): the number of gears, rods and interlockings.
$n_g$ lines, each with two integers $t_i$ and $r_i$ ( $0 < t_i < 100$ , $0 \le r_i < n_r$ ): the type number of gear $i$ and the index of the rod it sits on.
$n_i$ lines, each with two integers $a_j$ and $b_j$ ( $0 \le a_j < b_j < n_g$ ): gears $a_j$ and $b_j$ are interlocked.

Output

For each test case, print a single line containing ok if the gearbox is definitely assembled correctly, or jammed otherwise.

Examples4

Example 1

Input

Expected output

ok
ok
jammed
jammed

Example 2
Input
```
1
1 1 0
5 0
```
Expected output
```
ok
```
Example 3
Input
```
1
2 1 1
3 0
3 0
0 1
```
Expected output
```
jammed
```
Example 4
Input
```
1
3 3 2
1 0
1 1
1 2
0 1
1 2
```
Expected output
```
ok
```