시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 99 27 23 31.507%

문제

CINERIS라는 도시국가가 있다. 이 도시국가에는 N개의 철도역이 있고, 역들은 트리 구조로 이어져 있다. 이 도시국가를 통치하는 정민이는 최근에 사람들이 가장 많이 다니는 구간이 어디인지 궁금했다. 지금까지 총 Q개의 표가 팔렸고, 정민이가 각 Q개의 표에서 알아낼 수 있는 정보는 출발역과 도착역의 정보뿐이다.

CINERIS에 살고 있는 사람들은 정민이처럼 모두 똑똑하기 때문에, 최단 거리로 이동했다고 가정한다. 그렇다면, 이 Q개의 정보를 이용하여 사람들이 가장 많이 다니는 구간을 구하여라.

입력

첫 번째 줄에 N, Q가 주어진다.

두 번째 줄부터 N번째 줄까지 각 줄에 두 개의 수 a, b가 주어지는데, 이는 a번 역에서 b번 역으로 가는 양방향 철로가 존재함을 의미한다.

N + 1번째 줄부터 N + Q번째 줄까지는 각 표의 출발역과 도착역의 정보 c, d가 주어진다. 이는 표가 c번 역에서 출발하여 d번 역에 도착하였다는 정보를 가짐을 의미한다.

N, Q의 제한은 다음과 같다:

1 ≤ N ≤ 2222, 1 ≤ Q ≤ 222222

출력

사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하는 구간(철로)임을 의미하고, 그 구간을 지난 사람의 수가 c명이라는 의미이다. 만약 조건을 만족하는 답인 (a, b) 쌍이 여러 개라면, 사전 순으로 가장 작은것을 출력한다.

예제 입력

4 7
1 2
2 3
3 4
1 3
2 4
1 2
3 4
1 4
2 3
1 3

예제 출력

2 3 5

힌트