25242번 - 가희와 지하철

가희는 노선이 N개 있는 서울 지하철의 매력에 푹 빠졌습니다. 그래서 Q일 동안 출발지에서 목적지까지 서울 지하철만 타고 가려고 합니다.

그런데, 가희는 출발지에서 목적지까지 가장 시간이 적게 걸리는 방법으로 이동하려고 합니다. 가희를 도와주세요.

단, 한 역에서 인접 역까지 소요 시간은 2분으로 같고, 다른 노선으로 환승하는 시간은 무시합니다.

첫 번째 줄에 N과 Q가 공백으로 구분되어 주어집니다.

두 번째 줄부터 N개의 줄에 노선의 역 개수 s와 노선에 있는 역 이름들이 주어집니다.

이때, 역 이름은 해당 노선의 1번 역부터 s번 역까지 공백으로 구분되어 주어지며, 각 역은 아래 조건에 맞습니다.

• 하행의 시발역은 1번 역이고, 종착역은 s번 역이며, 상행의 시발역은 s번 역이고, 종착역은 1번 역입니다.
• 하행에서 x번 역의 다음 역은 x+1번 역이며, 종착역에 도착한 후에는 운행을 종료합니다.
• 상행에서 x+1번 역의 다음 역은 x번 역이며, 종착역에 도착한 후에는 운행을 종료합니다.

예를 들어 3 ab cd ef로 노선이 주어지는 경우, 해당 노선의 상행, 하행은 아래와 같이 운행합니다.

• 하행은 1번역인 ab역에서 운행을 시작해서, cd역, ef역 순으로 멈춥니다. ef역에 도착한 후에는 운행을 종료합니다.
• 상행은 3번역인 ef역에서 운행을 시작해서, cd역, ab역 순으로 멈춥니다. ab역에 도착한 후에는 운행을 종료합니다.

다음 Q개의 줄에는 출발지와 목적지가 공백으로 구분되어 주어집니다.

Q개의 줄에 답을 출력해 주세요. 만약, 갈 수 없다면 -1을 출력해 주세요.

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• 각 노선에는 최소 둘 이상의 역이 있으며, 같은 이름의 역이 중복해서 나오지 않습니다.
• 환승역은 20개 이하입니다.
• 루프선, 순환선, 지선은 없으며, 다른 지역에 있는 동명의 역 (ex. 양평)도 없습니다.
• 역명은 대소문자로만 이루어져 있으며, 길이는 8 이하입니다.
• 1 ≤ N개의 노선에 있는 역의 수의 총합 ≤ 2 × 10⁵