컴퓨터 네트워크

문제

$N$개의 컴퓨터가 있다. 컴퓨터끼리 통신을 해야 하는데, 사용하는 프로토콜이 같은 컴퓨터끼리만 통신할 수 있다. 프로토콜의 종류로는 총 $M$개가 있고 각 컴퓨터가 사용하는 프로토콜의 개수는 $1$개 이상이다.

예를 들어 $1$번 컴퓨터는 $1$, $2$번 프로토콜을 사용하고, $2$번 컴퓨터는 $2, 3$번 프로토콜을, $3$번 컴퓨터는 $3$번 프로토콜을 사용한다고 가정해 보자. $1$번 컴퓨터와 $2$번 컴퓨터는 $2$번 프로토콜을 사용하여 직접 통신할 수 있다. 두 컴퓨터가 사용하는 프로토콜이 서로 겹치지 않으면 두 컴퓨터는 직접 소통할 수 없다. 그 대신에 통신할 수 있는 다른 컴퓨터를 거쳐서 간접적으로 소통할 수 있다. $1$번 컴퓨터와 $3$번 컴퓨터가 서로 소통하고자 한다면, $2$번 컴퓨터를 거쳐서 소통할 수 있다. $1$번 컴퓨터와 $2$번 컴퓨터가 $2$번 프로토콜을 사용하고, $2$번 컴퓨터와 $3$번 컴퓨터가 $3$번 프로토콜을 사용해 소통할 수 있기 때문이다.

민용이는 문득 두 컴퓨터가 통신하기 위해 거쳐야 하는 다른 컴퓨터의 최소 개수를 구하고 싶어졌다. 민용이의 궁금증을 해결해 주자!

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2\le N, M\le 1\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐, 각 줄에 순서대로 $i$번 컴퓨터가 사용하는 프로토콜이 주어진다. 처음 주어지는 정수는 $i$번 컴퓨터가 사용하는 프로토콜의 개수 $C_i$이고, 다음 $C_i$개의 정수는 $i$번 컴퓨터가 사용하는 프로토콜 번호 $P$가 공백으로 구분되어 주어진다. ($1\le C_i, P\le M;$)

셋째 줄에 민용이의 질문 $Q$가 주어진다. ($1\le Q\le 500\,000$)

넷째 줄부터 $Q$개의 줄에 걸쳐, 각 줄에 두 정수 $x$, $y$가 주어진다. 두 컴퓨터가 통신을 하기 위해 거쳐야 하는 최소 컴퓨터의 개수를 구해야 한다. ($1\le x, y\le N; x\neq y$)

출력

각 줄에 두 컴퓨터가 통신을 하기 위해 거쳐야 하는 다른 컴퓨터의 최소 개수를 출력한다. 만약 두 컴퓨터가 통신을 할 수 없다면 대신 -1를 출력한다.

예제 입력 1

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

예제 출력 1

0
1
-1