시내 도로 교통 조사

문제 정보

문제

국가의 공무를 수행 중인 재홍이는 새로운 버스 노선을 만들기 위해 시내 도로 교통 정보를 조사하고 있다. 시내에는 교차로가 N개, 도로가 M개 있다. 하나의 도로는 두 교차로를 연결하여, 양쪽에서 서로 이동 가능하게 만든다. 재홍이는 새로운 버스 노선 후보로 결정된 출발 교차로, 종점 교차로 쌍을 여러개 가지고 있다. 이런 출발 교차로에서 종점 교차로까지 이동 가능한 경로는 없을 수도 있고, 한 개 이상일 수도 있다. 이동 가능한 경로가 한 개 이상인 경우, 가장 거리가 짧은 경로를 최단 경로라고 부른다. 재홍이가 해야될 일은 이런 교차로 쌍들에 대해 각각, 최단 경로의 개수를 파악하는 것이다. 재홍이를 도와주자.

입력

첫 번째 줄에는 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 교차로의 개수 N, 도로의 개수 M, 버스 노선 후보로 결정된 교차로 쌍의 개수 Q가 주어진다. (3 <= N <= 100, 1 <= M <= N*(N-1)/2, 1 <= Q <= 20)
그 다음 M개 줄에 각각 도로 정보가 주어진다. 도로 정보는 그 도로에 연결된 두 교차로의 번호 Vi, Ui와 도로의 길이를 나타내는 정수 Di로 주어진다. (1 <= Vi <= N, 1 <= Ui <= N, Vi != Ui, 1 <= Di <= 100) 두 교차로 사이에는 최대 하나의 도로만 존재할 수 있다. 그러므로 모든 교차로 사이에 도로가 있는 경우, N*(N-1)/2개의 도로가 있을 수 있다.
그 다음 Q개 줄에 각각 버스 노선 후보로 결정된 출발 교차로 Ai와 종점 교차로 Bi가 주어진다. (1 <= Ai <= N, 1 <= Bi <= N, Ai != Bi)

출력

각 후보 교차로 쌍마다 한 줄에 하나씩 답을 출력한다. 이동 가능한 경로가 없으면 "no"를, 최단 경로가 하나만 존재하면 "only"를, 최단 경로가 두 개 이상 존재하면 "many"를 출력한다.

예제 입력

2
3 1 3
1 2 50
1 3
2 3
2 1
5 5 5
1 2 5
2 3 4
3 4 2
1 4 10
2 4 5
1 4
2 4
3 4
3 1
2 5

예제 출력

no
no
only
many
only
only
only
no

노트

첫 번째 테스트 케이스에서 1, 2번 교차로에서 3번 교차로로 이동가능한 경로는 없다. 두 번째 테스트 케이스에서 1번 교차로와 4번 교차로 사이에는 길이가 10인 2개의 최단 경로 1->4, 1->2->4가 있다.

1개의 댓글이 있습니다.