해킹에서 밀고까지

예술품 거래로는 컴퓨터 과학 대회 상금만으로 생활할 수 없어서, 당신은 미술품 도둑으로 데뷔할 박물관을 골랐다. 그런데 이 박물관은 경비가 삼엄하다. 건물을 순찰하는 경비원이 $K$명 있고, 각자 박물관 안의 단순 닫힌 경로를 따라 돈다.

박물관은 $N$개의 모퉁이와 이를 잇는 $M$개의 복도로 이루어진 지도로 표현된다. 모퉁이에는 1번부터 $N$번까지 번호가 붙어 있다. 당신은 1번 모퉁이에서 출발하고, 목표인 값비싼 전시품은 $N$번 모퉁이에 있다. 어느 모퉁이에서든 다른 모퉁이로 갈 수 있는 것은 확실하다. 하지만 들키지 않고 갈 수 있는지는 알 수 없다. 즉, 경비원과 같은 모퉁이에 서거나 복도에서 경비원과 마주치면 안 된다.

다행히 경비 명부를 구했다. 각 경비원의 출발 위치와 순찰 경로를 알고 있다. 매 분마다 경비원은 현재 모퉁이에서 경로상 다음 모퉁이로 이동한다. 당신은 현재 모퉁이에 머물거나 인접한 모퉁이로 이동할 수 있다. 경비원들의 경로는 서로 교차하지 않으며, 당신의 출발 모퉁이와 목표 모퉁이는 어떤 경로에도 포함되지 않는다.

이 정보를 바탕으로 들키지 않고 목표에 안전하게 도착하는 데 필요한 최소 시간(분)을 구하거나, 그것이 불가능하다고 판단하라.

* 전시품에 도착하면 창문을 열고 전국 대회에서 받은 날개옷을 입고 박물관을 빠져나간다. 따라서 돌아오는 안전한 경로는 계획할 필요가 없다.

† 물론 당신은 경비원에게 손끝 하나 대지 않는 신사 도둑이다!

첫 줄에 정수 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄에는 정수 $u$, $v$ ($1 \le u, v \le N$, $u \ne v$)가 주어지며, 모퉁이 $u$와 $v$를 직접 잇는 복도가 있다는 뜻이다. 두 모퉁이를 직접 잇는 복도는 최대 하나다.

다음 줄에 정수 $K$가 주어진다. 이어서 $K$개의 줄이 주어지며, $i$번째 줄은 $i$번째 경비원의 순찰 경로를 나타낸다. 첫 정수 $\ell_i$는 경로에 있는 서로 다른 모퉁이의 개수이고, 뒤이어 서로 다른 정수 $v_1, \cdots, v_{\ell_i}$가 주어진다. 경비원은 $v_1$에서 출발하여 1분 뒤 $v_2$에 있고, 같은 방식으로 이동한다. $\ell_i$분 뒤에는 다시 $v_1$에 있다.

목표에 안전하게 도착하는 데 필요한 최소 시간(분)을 정수로 한 줄에 출력한다. 그럴 방법이 없으면 impossible을 출력한다.

• $1 \le N \le 250 000$
• $1 \le M \le 3 000 000$
• $3 \le \ell_i \le 1 500$
• $\ell_1 + \cdots + \ell_K \le 2 750$

다음 그림은 위의 첫 번째 예제 상황에 해당한다. 경비원의 출발 모퉁이는 굵게 표시되어 있고, 순찰 경로는 발자국으로 나타나 있다.

최적 경로는 1번 모퉁이에서 1분 기다린 뒤, 지체 없이 2, 5, 마지막으로 6번 모퉁이로 가는 것이다.

두 번째 예제는 박물관 배치가 같지만 경비원의 출발 위치와 방향이 다르다. 가능한 최적 경로는 1에서 2, 3, 4, 5를 거쳐 6으로 가는 것이다.