32433번 - Bacon Number 스페셜 저지다국어

문제

Carlinhos loves movies, and recently he has been fascinated by the Bacon Number, which is defined as follows.

• The Bacon number of the actor Kevin Bacon is equal to 0ドル$;
• If the smallest Bacon number of an actor with whom $X$ has appeared in the same movie is $b,ドル the bacon number of the actor $X$ is $b + 1$.

That is, the Bacon number measures the shortest path between any actor and the actor Kevin Bacon, in which two actors are connected if they appeared together in the same movie.

Carlinhos is interested in a more general problem: given two actors, how to connect them through intermediate movies and actors? Given $N$ movies, and, for each movie, which of the existing $M$ actors acted in it. Carlinhos wants to answer $Q$ queries: in the $i$-th of them, we want to compute some way to connect actor $x_i$ with actor $y_i$. We must find some sequence $x_i = a_1, f_1, a_2, f_2, \dots , f_{k-1}, a_k = y_i,ドル where 1ドル ≤ a_j ≤ N$ are actors and 1ドル ≤ f_j ≤ M$ are movies, and actor $a_j$ acted in movies $f_{j-1}$ and $f_j,ドル or indicate that no such sequence exists.

입력

In the first line of the input, two integers $N$ (1ドル ≤ N ≤ 100$) and $M$ (1ドル ≤ M ≤ 10^6$) are given, the number of movies and the number of actors.

$N$ lines follow. In the $i$-th line, the first integer $n_i$ (1ドル ≤ n_i ≤ M$) denotes the number of actors in movie $i$. Next, $n_i$ numbers in ascending order separated by spaces: the indices, from 1ドル$ to $M,ドル of the actors who acted in movie $i$.

The next line, contains an integer $Q$ (1ドル ≤ Q ≤ 10^4$): the number of queries.

The next $Q$ lines describe the queries. In the $i$-th of them, read two numbers $x_i,ドル $y_i$ (1ドル ≤ x_i \ne y_i ≤ M$), the actors we want to connect. It is guaranteed that the total number of actors in the movies is at most 10ドル^6$. That is, $\sum_{i}{n_i} ≤ 10^6$.

출력

For each of the queries, if there is no sequence, print a line with -1. Otherwise, print two lines. In the first line, print the number of actors $k_i$ (2ドル ≤ k_i ≤ 10^6$) in some way to connect $x_i$ and $y_i$. In the second, print the sequence as described, with $k_i$ actors and $k_i - 1$ movies, alternating. If there is more than one way to connect the actors, print any of them.

제한

힌트