공장들
시간 제한6초메모리 제한512 MB
가중 트리에서 쿼리마다 주어지는 두 공장 집합 사이 최단 거리를 구합니다.
문제
IOI 왕국에는 번부터 번까지 번호가 붙은 도시가 개 있다. 도시는 양방향으로 통행할 수 있는 도로 개로 이어져 있고, 어느 두 도시 사이든 도로를 몇 개 지나 오갈 수 있다.
IOI 왕국에는 특별한 제품을 만드는 회사가 많다. 회사마다 제품을 한 종류만 만들고, 서로 다른 두 회사가 같은 종류의 제품을 만드는 일은 없다. 회사는 저마다 공장을 하나 이상 두고 있으며, 공장은 모두 도시 중 한 곳에 지어져 있다. 한 도시에 여러 회사가 공장을 둘 수도 있다.
회사 가 회사 의 제품을 필요로 할 때가 있다 (). 이때는 의 공장 하나에서 의 공장 하나로 제품을 옮기면 된다. 두 회사는 공장 사이의 거리가 가장 짧아지도록 공장을 고른다.
먼저 도시의 수와 도로 정보가 주어지고, 이어서 질의가 개 주어진다. 번 질의의 뜻은 이렇다. 도시 에 공장을 둔 회사 가 도시 에 공장을 둔 회사 의 제품을 필요로 한다. 질의마다 제품을 옮기는 데 드는 최소 거리를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 과 가 공백을 사이에 두고 주어진다. IOI 왕국에 도시가 개 있고, 질의가 개 주어진다는 뜻이다.
이어지는 개 줄 가운데 번째 줄 ()에는 정수 , , 가 공백을 사이에 두고 주어진다. 도시 와 도시 를 잇는 길이 짜리 도로가 있다는 뜻이다.
그다음 개 줄에 질의가 주어진다. 번 질의 ()의 정보는 번째 줄부터 번째 줄까지다.
번째 줄에는 정수 와 가 공백을 사이에 두고 주어진다. 회사 가 도시 곳에, 회사 가 도시 곳에 공장을 두었다는 뜻이다.
번째 줄에는 정수 개 이 공백을 사이에 두고 주어진다. 회사 가 이 도시들에 공장을 두었다는 뜻이다.
번째 줄에는 정수 개 이 공백을 사이에 두고 주어진다. 회사 가 이 도시들에 공장을 두었다는 뜻이다.
모든 입력은 다음 조건을 만족한다.
- , , ()
- ()
- 도로를 따라 어느 도시에서든 나머지 모든 도시로 갈 수 있다.
- , ()
- (), ()
- 한 질의에 나오는 은 모두 서로 다르다.
출력
질의의 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.
힌트
예제의 세 질의는 다음과 같이 풀린다.
- 0번 질의에서 회사 는 도시 0번과 6번에, 회사 는 도시 3번과 4번에 공장을 두었다. 도시 3번의 공장에서 도시 6번의 공장까지가 가장 가깝고, 그 거리는 12이다.
- 1번 질의에서 회사 은 도시 0번, 1번, 3번에, 회사 은 도시 4번과 6번에 공장을 두었다. 도시 6번의 공장에서 도시 1번의 공장까지가 가장 가깝고, 그 거리는 3이다.
- 2번 질의에서 회사 는 도시 2번에, 회사 는 도시 5번에 공장을 두었다. 도시 5번의 공장에서 도시 2번의 공장까지의 거리는 11이다.