Bacon Number

Carlinhos adora filmes, e recentemente tem estado fascinado com o número de Bacon, mais conhecido como Bacon Number, que é definido da seguinte forma.

• O número de Bacon do ator Kevin Bacon é igual a 0;

• Se o menor número de Bacon de um ator com quem $X$ tenha aparecido em um mesmo filme for $b$, o número de bacon do ator $X$ é $b + 1$.

Ou seja, o número de Bacon mede o menor caminho entre qualquer ator e o ator Kevin Bacon, em que dois atores são conectados se eles apareceram juntos em um mesmo filme. Carlinhos está interessado em um problema mais geral: dados dois atores, como conectá-los através de filmes e atores intermediários? São dados $N$ filmes, e, para cada filme, quais dos $M$ atores existentes atuaram nele. Carlinhos quer responder $Q$ consultas: na i-ésima delas, queremos computar alguma forma de conectar o ator $x_i$ com o ator $y_i$ . Devemos achar alguma sequência $x_i = a_1 , f_1 , a_2 , f_2 , . . . , f_{k−1} , a_k = y_i$ , em que $1 ≤ a_j ≤ N$ são atores e $1 ≤ f_j ≤ M$ são filmes, e o ator $a_j$ atuou nos filmes $f_{j−1}$ e $f_j$ , ou indicar que não existe tal sequência.

Na primeira linha da entrada, são fornecidos dois inteiros $N (1 ≤ N ≤ 100)$ e $M (1 ≤ M ≤ 10^6)$, o número de filmes e o número de atores. Seguem $N$ linhas. Na i-ésima delas, o primeiro inteiro $n_i$ $(1 ≤ n_i ≤ M )$ denota o número de atores no filme $i$. Seguem $n_i$ números em ordem crescente separados por espaço: os ı́ndices, de $1$ a $M$ , dos atores que atuaram no filme $i$. Na próxima linha, leia um número $Q (1 ≤ Q ≤ 10^4 )$: o número de consultas. As próximas $Q$ linhas descrevem as consultas. Na i-ésima delas, leia dois números $x_i$ , $y_i$ $(1 ≤ x_i ̸= y_i ≤ M )$, os atores que queremos conectar. É garantido que o número total de atores nos filmes é no máximo $10^6$. Isto é, $ n_i ≤ 10^6$ .

Para cada uma das consultas, se não existe sequência, imprima uma linha com −1. Caso contrário, imprima duas linhas. Na primeira, o número de atores $k_i (2 ≤ k_i ≤ 10^6 )$ em alguma maneira de conectar $x_i$ e $y_i$ . Na segunda, imprima a sequência como descrita, com $k_i$ atores e $k_i − 1$ filmes, de maneira alternada. Se houver mais de uma maneira de conectar os atores, imprima qualquer uma delas.