| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 171 | 75 | 60 | 44.118% |
신촌의 다섯 대학교인 서강대, 숙명여대, 연세대, 이화여대, 홍익대는 학생들의 원활한 교통을 위한 버스 사업을 운영하고 있다. 각 대학교에는 1ドル$번부터 $X$번까지 총 $X$개의 버스 노선이 존재한다. 서로 다른 대학교가 운영하는 동일한 번호의 버스 노선은 서로 다른 버스 노선이므로, 현재 신촌에는 총 5ドルX$개의 버스 노선이 존재한다.
신촌에는 $N$개의 버스 정류장이 있다. 각 대학교는 $N$개의 버스 정류장에 각 대학교가 운영하는 버스 노선 중 하나를 지정하여 운행한다. 버스 정류장은 1ドル$번부터 $N$번까지 번호가 매겨져 있으며, $i$번 정류장을 지나는 버스 노선의 번호는 서강대, 숙명여대, 연세대, 이화여대, 홍익대 순으로 각각 $A_i,ドル $B_i,ドル $C_i,ドル $D_i,ドル $E_i$이다. 노선의 운영 상태에 따라 1ドル$개의 정류장만 지나는 노선이나, 정류장이 지정되지 않아 운영하지 않는 노선이 존재할 수 있다. 학생들은 특정 버스를 타면 그 버스가 속한 노선에 있는 다른 정류장 중 아무 정류장에서 내릴 수 있다.
여러분은 신촌의 버스 노선 정보를 활용하여 최소 환승 경로를 계산하는 신촌 길찾기 서비스를 개발하고 있다. 아래의 질문 $Q$개에 대한 답을 출력하시오.
-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$개의 줄에 걸쳐 순서대로 출력한다.
5 7 1 1 1 1 1 1 2 3 4 5 3 3 3 3 3 6 6 6 7 7 7 7 7 7 6 3 1 3 1 5 4 5
2 -1 1
5 5 2 2 1 5 2 4 3 5 5 1 4 1 4 4 3 4 3 3 3 3 3 2 3 2 5 3 5 2 1 4 5 3
2 2 2