지하철 스페셜 저지 서브태스크 1초 128MB
문제
스톡홀름의 지하철은 매우 비효율적이다.
도시는 지하철이 지어진 때와 다른 모습이 되어 있었고,
때문에 지하철은 사람으로 붐비는 노선과 한산한 노선이 공존하는 곳이 되었다.
그런 이유에서, 의회는 지하철을 다시 짓기로 결심했다.
현재, 지하철은 N개의 역과, N-1개의 두 역을 연결하는 철로로 되어있으며,
임의의 두 도시는 철로만을 사용하여 이동할 수 있게 되어 있다.
의회는 기존 N개의 역을 다른 N-1개의 철로로 연결하는 노선도를 개발하였다.
새로운 노선도 또한 임의의 두 도시를 철로만으로 이동할 수 있다.
지하철의 혼잡도를 최소로 하기 위해, 재건축은 한 번에 하나의 철로만 할 수 있다. 매 주말마다,
하나의 철로가 철거되고, 하나의 철로가 새로 지어진다.
즉, 항상 N-1개의 철로가 존재한다.
또한, 재건축이 끝난 뒤에는 항상 임의의 두 도시를 철로만으로 이동할 수 있게 해야 한다.
당신은 위의 조건을 만족하면서, 지하철을 새로운 노선도로 바꾸기 위한 재건축 방법을 찾아야 한다.
물론 당신의 계획은 되도록 빠르게 진행되어야 한다.
입력
첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 100 000)
다음 N-1개의 줄에는 현재 지하철의 노선도가 주어진다.
각 철로는 0과 N-1 사이의 두 정수 a, b가 공백을 사이에 두고 주어진다.
이는 a와 b가 철로로 이어져 있다는 것을 의미한다.
트리는 연결되어 있음이 주어진다.
다음 N-1개의 줄에는 새로운 노선도의 정보가 같은 형식으로 주어진다.
출력
첫 번째 줄에, 계획의 소요 시간 K가 주어진다.
다음 K개의 줄에, 재건축 계획을 시간순서로 출력한다.
재건축 계획은 a1, b1, a2, b2으로 출력해야 하며,
이는 a1, b1을 잇는 철로를 철거하면서 a2, b2를 잇는 철로를 짓는다는 것을 의미한다.
예제 #1
3
0 1
1 2
0 1
0 2
1
2 1 2 0
예제 #2
4
0 1
0 2
0 3
0 1
1 2
2 3
2
3 0 3 2
0 2 1 2
로그인해야 코드를 작성할 수 있어요.