교통량 (작은 입력)
면접 대비시간 제한2초메모리 제한512 MB
트리와 Q개의 표가 주어질 때, 각 표가 지나는 유일한 경로의 간선마다 이용 횟수를 세고, 가장 많이 이용된 간선을 역 번호가 작은 쌍 순으로 출력한다.
문제
CINERIS라는 도시국가에 철도역이 N개 있고, 역을 잇는 철로는 트리 구조를 이룬다. 서로 다른 두 역을 잇는 경로는 항상 하나뿐이다. 이 나라를 통치하는 정민이는 사람이 가장 많이 지나간 철로 구간이 어디인지 알고 싶다. 지금까지 표가 Q장 팔렸고, 표 한 장에서 알 수 있는 정보는 출발역과 도착역뿐이다.
CINERIS 사람은 모두 최단 경로로 이동한다. 트리에서 두 역을 잇는 경로는 유일하므로, 표 한 장은 출발역과 도착역을 잇는 경로에 놓인 철로를 각각 정확히 한 번 지난다. 출발역과 도착역이 같은 표는 어떤 철로도 지나지 않는다. Q장의 표 정보로 사람이 가장 많이 지나간 철로를 구하라.
입력
첫째 줄에 N과 Q가 공백으로 구분되어 주어진다.
다음 N - 1개의 줄에는 두 정수 a, b가 주어진다. a번 역과 b번 역을 잇는 양방향 철로가 있다는 뜻이다.
다음 Q개의 줄에는 표 한 장의 출발역과 도착역 c, d가 주어진다. 그 표를 산 사람이 c번 역에서 출발해 d번 역에 도착했다는 뜻이다.
, , 이고, 주어지는 철로는 항상 트리를 이룬다.
출력
사람이 가장 많이 지난 철로와 그 철로를 지난 사람 수를 a b c 꼴로 한 줄에 출력한다. a번 역과 b번 역을 잇는 철로를 c명이 지났다는 뜻이며, 두 역 번호는 가 되도록 오름차순으로 쓴다. 사람 수가 최대인 철로가 여러 개면 (a, b)가 사전순으로 가장 작은 것을 출력한다.