Board Game Strategy

Alice and Bob are playing an interesting board game. The board has n positions labeled from 0 to n-1. Before the game begins, Bob picks a starting position and Alice chooses her target position. The game is played in rounds, and in each round the following occurs:

• Alice’s move: Depending on the current position u, there are several options available. Each option is a set S of positions. Alice picks one of these available sets.
• Bob’s move: From the set S chosen by Alice, Bob selects one position v and moves the gamepiece there. This position becomes the starting position for the next round.

At the start of the game, both players secretly choose a position. Bob’s choice is the starting position and Alice’s choice is her winning target. Alice wins if, by following an optimal strategy, she can force Bob to move the gamepiece to her chosen target before she runs out of money. (For this problem, ignore monetary issues and assume the game ends immediately when the gamepiece reaches Alice’s target.)

Both players play optimally: Alice will always choose an option which leads to her eventual win if one exists, while Bob will always try to delay or avoid that outcome. For each situation described by a starting position and a target, your task is to determine whether Alice can force a win and, if so, the minimum number of rounds required.

The game can be modeled as a directed hypergraph where each vertex represents a board position and edges correspond to the sets of moves available at that position. A state (position) is winning for Alice if there exists at least one option (set of moves) such that each move in that option leads (in one round) to a winning state, with the target state defined as winning with 0 rounds remaining.

The optimal number of rounds from any state u can be defined by the recurrence below in \(\LaTeX\) form:

[ \text{dp}(u) = \begin{cases} 0, & \text{if } u = t,\ 1 + \min_{S \in \mathcal{O}(u),, \forall v \in S:, \text{dp}(v) < \infty} \max_{v \in S},\text{dp}(v), & \text{if } u \neq t, \ \infty, & \text{otherwise.} \end{cases} ]

If \(\text{dp}(u) = \infty\), then Alice cannot guarantee a win from position \(u\); otherwise, the value of \(\text{dp}(u)\) is the minimum number of rounds required. You are asked to answer several queries, each consisting of a start position and a target position.

inputFormat

The first line contains a single integer n (the number of positions, labeled from 0 to n-1).

Then follow n blocks, one for each position from 0 to n-1:

• The first line of a block contains an integer k, the number of options available at that position.
• Each of the next k lines starts with an integer s (the number of positions in the option) followed by s space-separated integers representing the positions in that option.

The next line contains an integer q, the number of queries.

Each of the next q lines contains two space-separated integers: start and target.

outputFormat

For each query, output a single line. If Alice can force a win starting from the given position, print the minimum number of rounds required; otherwise, print impossible.

sample

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

2