신촌 길찾기 서비스

신촌의 다섯 대학교인 서강대, 숙명여대, 연세대, 이화여대, 홍익대는 학생들의 원활한 교통을 위한 버스 사업을 운영하고 있다. 각 대학교에는 $1$번부터 $X$번까지 총 $X$개의 버스 노선이 존재한다. 서로 다른 대학교가 운영하는 동일한 번호의 버스 노선은 서로 다른 버스 노선이므로, 현재 신촌에는 총 $5X$개의 버스 노선이 존재한다.

신촌에는 $N$개의 버스 정류장이 있다. 각 대학교는 $N$개의 버스 정류장에 각 대학교가 운영하는 버스 노선 중 하나를 지정하여 운행한다. 버스 정류장은 $1$번부터 $N$번까지 번호가 매겨져 있으며, $i$번 정류장을 지나는 버스 노선의 번호는 서강대, 숙명여대, 연세대, 이화여대, 홍익대 순으로 각각 $A\_i$, $B\_i$, $C\_i$, $D\_i$, $E\_i$이다. 노선의 운영 상태에 따라 $1$개의 정류장만 지나는 노선이나, 정류장이 지정되지 않아 운영하지 않는 노선이 존재할 수 있다. 학생들은 특정 버스를 타면 그 버스가 속한 노선에 있는 다른 정류장 중 아무 정류장에서 내릴 수 있다.

여러분은 신촌의 버스 노선 정보를 활용하여 최소 환승 경로를 계산하는 신촌 길찾기 서비스를 개발하고 있다. 아래의 질문 $Q$개에 대한 답을 출력하시오.

• $U$번 정류장에서 $V$번 정류장으로 이동하기 위해 이용해야 하는 버스 노선은 최소 몇 개인지 출력하시오. 만약 이동할 수 없다면 -1을 출력하시오.

첫 번째 줄에는 정류장의 수 $N$, 각 대학교의 버스 노선의 수 $X$가 공백으로 구분되어 주어진다. $(2 \leq N \leq 100\\,000;$ $1 \leq X \leq 100)$

다음 $N$개의 줄에 걸쳐, $i$번째 줄에 $i$번 정류장을 지나는 버스 노선의 정보를 의미하는 $A\_i$, $B\_i$, $C\_i$, $D\_i$, $E\_i$가 공백으로 구분되어 주어진다. $(1 \leq A\_i, B\_i, C\_i, D\_i, E\_i \leq X)$

다음 줄에는 질문의 수 $Q$가 주어진다. $(1 \leq Q \leq 100\\,000)$

다음 $Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 질문에 대한 정보로 시작 정류장과 도착 정류장의 번호를 의미하는 $U\_i$, $V\_i$가 공백으로 구분되어 주어진다. $(1 \leq U\_i, V\_i \leq N;$ $U\_i \neq V\_i)$

각 질문에 대한 답을 $Q$개의 줄에 걸쳐 순서대로 출력한다.