Monkey in the Labyrinth

A hungry monkey wants to eat a banana. The monkey and the banana are in a labyrinth made of rooms and the corridors connecting them. Each room is in one of two states: locked or unlocked. If a room is locked, the monkey cannot enter it, but can still leave it. Unlocked rooms can be entered and left freely.

Some rooms contain a switch. Pressing a switch flips the states of a fixed group of rooms all at once: locked rooms in that group become unlocked, and unlocked rooms become locked. The same switch always flips the states of the same group of rooms.

When the monkey enters a room that has a switch, it may press that switch if it chooses to.

Write a program that helps the monkey find the room with the banana as quickly as possible, that is, find the smallest number of corridors the monkey must pass through to reach the banana, possibly by pressing some switches along the way.

The input describes the rooms and corridors of the labyrinth, the initial state of every room, the list of switches, and, for each switch, the list of rooms whose states it changes.

The first line contains two integers: N, the total number of rooms (1 ≤ N ≤ 100), and S, the number of switches, i.e. the number of rooms that have a switch (1 ≤ S ≤ 8). The switches are located in the rooms numbered from 1 to S.

The next N lines describe the rooms. The description of room i is given on line (i+1). It begins with 0 if the room is initially unlocked, or 1 if it is initially locked. Then comes an integer K, the number of rooms connected to this room by a corridor, followed by those K room numbers. Numbers on the same line are separated by spaces.

The following S lines describe the switches, from the first to the S-th. Each line begins with an integer L, the number of rooms in the group whose states this switch changes, followed by the L room numbers of that group.

The last line contains two integers A and B. A is the number of the room where the monkey starts its search, and B is the number of the room that contains the banana.

Print, on a single line, the smallest number of corridors the monkey must pass through to reach the banana.

Note: Every test case has a solution; that is, there is always a way to get from room A to room B.