견우와 직녀
시간 제한1초메모리 제한1024 MB
가중치 트리 두 개에서 각각 정점 하나씩을 골라 길이 1인 간선으로 이어, 두 트리 정점 사이 모든 거리 합이 최소가 되게 하려 한다.
문제
견우는 정점의 개수가 인 무향 가중치 트리 에 살고 있고, 직녀는 정점의 개수가 인 무향 가중치 트리 에 살고 있다.
두 사람은 각자 다른 트리에 살고 있으므로 만날 수 없다... 슬픔에 빠진 두 사람을 위해 옥황상제는 매년 7월 7일이 되면 오작교를 이어 두 사람이 만날 수 있게 해주려고 한다.
오작교는 길이가 인 간선이며 옥황상제는 두 사람이 만나기 쉽도록 의 모든 정점과 의 모든 정점 사이의 거리의 합이 최소가 되도록 이어주려고 한다.
견우와 직녀를 위해 7월 7일이 되면 어떤 정점에서 오작교가 이어지는지 알려주도록 하자!
입력
첫째 줄에 의 정점 개수 이 주어진다.
다음 개의 줄에 걸쳐 의 간선이 a b c와 같은 형식으로 주어진다. 이는 의 번 정점과 번 정점 사이의 거리가 라는 것을 뜻한다.
다음 줄에 의 정점 개수 이 주어진다.
다음 개의 줄에 걸쳐 의 간선이 a b c와 같은 형식으로 주어진다. 이는 의 번 정점과 번 정점 사이의 거리가 라는 것을 뜻한다.
주어지는 입력은 모두 정수다.
출력
첫째 줄에 오작교가 이어지게 되는 의 정점 번호와 의 정점 번호를 공백을 사이에 두고 차례대로 출력한다. 가능한 경우가 여러 가지라면 그 중 아무거나 출력한다.
둘째 줄에 오작교가 이어진 후 의 모든 정점과 의 모든 정점 사이의 거리의 합을 출력한다.
힌트
의 모든 정점과 의 모든 정점 사이의 거리의 합을 수학적으로 정의하면 다음과 같다.
\[ \sum_{u \in E} \sum_{v \in W} dist(u, v) \]