시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 449 | 221 | 133 | 45.085% |
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 ≤ 222222, 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
University > KAIST > 2016 Spring RUN@KAIST Programming Contest E2번