Treasure

Time limit3sMemory limit128 MB

Summary

Given clockwise-ordered corridors between vaults and guards following the right-hand rule, find which guards eventually collect all pieces of information.

Level: Medium7 of 10
Topics: Graph, Simulation, Math, Implementation
Solved: No attempts yet

Problem

An old king hid a treasure inside his castle and kept its location secret. Yet every time he went to war he feared that he might die and the treasure would be lost forever. So he chose trustworthy guards and confided to each of them a separate piece of the information needed to find the treasure.

The king ordered the guards to wander through the underground vaults beneath the castle following the right-hand rule. The vaults are joined by corridors. Outside the vaults the corridors never cross, though one may run beneath another. No corridor leads back to the vault it starts from, and any two vaults are joined by at most one corridor. The right-hand rule means that after a guard enters a vault, it leaves along the next corridor to the right: at every vault the corridors are listed in clockwise order, and the guard departs through the corridor that comes immediately after (clockwise) the one it entered through.

The guards begin at different corridor entrances. Several guards may start from the same vault, but no two of them enter the same corridor at once.

The guards obey their orders faithfully until the king returns. Whenever two or more guards are in the same vault at the same moment, they share all the treasure information they know. They share it even if none of them learns anything new. Guards that start in the same vault share what they know at the very start (time 0). Guards that merely pass one another inside a corridor do not talk.

Walking through a corridor takes time equal to its length, and the time spent inside a vault is negligible. The guards keep walking without ever stopping.

Write a program that determines which guards could ever come to know all the information needed to find the treasure.

Input

The first line contains an integer n (2 ≤ n ≤ 100): the number of vaults, numbered 1 to n.

Each of the next n lines describes the corridors leaving one vault, in clockwise order. Line i+1 describes vault i: it begins with the number of corridors d leaving that vault (1 ≤ d ≤ n-1), followed by d pairs of integers. Each pair describes one corridor: the vault it leads to, then its length (from 1 to 100). Every corridor is two-way and has the same length in both directions.

The next line contains two integers k and l (1 ≤ k ≤ 100, 1 ≤ l ≤ 100): the number of guards and the number of information pieces. Guards are numbered 1 to k, and information pieces are numbered 1 to l.

Each of the next k lines describes one guard (guard i on line i). The line gives the vault the guard starts in, the vault it moves to first, an integer m (0 ≤ m ≤ l) telling how many pieces the guard already knows, and then those m piece numbers.

Output

On the first line, print the number of guards who could ever know all the information needed to find the treasure.

On the following lines, print the numbers of those guards in ascending order, one per line.

Hint

Examples3

Example 1

Input

4
3 2 3 3 4 4 1
2 1 3 3 1
3 4 3 1 4 2 1
2 1 1 3 3
3 4
1 4 2 2 3
3 1 2 1 2
3 4 2 3 4

Expected output

2
2
3

Example 2

Input

Expected output

2
1
2

Example 3
Input
```
2
1 2 4
1 1 4
1 2
1 2 2 1 2
```
Expected output
```
1
1
```