지하철

Stockholm의 지하철은 매우 비효율적이다. 현재의 지하철 노선이 건설되었을 때와 비교해 도시의 모습이 달라졌기 때문에, 일부 구간은 이용량이 지나치게 많은 반면 어떤 노선은 거의 이용되지 않는다.

따라서 시의회는 지하철을 재건하기로 결정했다. 현재 시스템은 $N$개의 역으로 이루어져 있으며, $N - 1$쌍의 역이 선로로 연결되어 있어 지하철로 임의의 두 역 사이를 이동할 수 있다. 시의회는 동일한 $N$개의 역으로 이루어지지만 서로 다른 $N - 1$개의 선로를 사용하는 새로운 계획을 세웠다(여전히 모든 역이 연결되도록 한다).

혼잡한 지하철의 운행 차질을 최소화하기 위해 재건은 한 번에 선로 하나씩 진행해야 한다. 매주 주말마다 선로 하나를 폐쇄하고 새 선로 하나를 건설해야 한다. 이는 선로가 항상 $N - 1$개임을 의미한다. 또한 주말 동안 공사가 끝난 뒤에는 항상 임의의 두 역 사이를 이동할 수 있어야 한다.

이 조건들을 만족하도록 새로운 지하철망을 건설하는 방법을 찾는 것이 과제이다. 계획에 필요한 주말의 수는 가능한 한 적어야 한다.

채점

제출한 풀이는 여러 서브태스크를 대상으로 채점된다. 하나의 서브태스크는 여러 테스트 케이스로 구성된다. 한 서브태스크의 점수를 얻으려면 해당 서브태스크에 속한 모든 테스트 케이스를 통과해야 한다.

서브태스크 | 점수 | 제한

1 | 33 | $N \leq 10$

2 | 33 | $N \leq 1000$

3 | 34 | 추가 제한 없음

첫째 줄에 정수 $N$ ($1 \leq N \leq 10^5$)이 주어진다. 다음 $N - 1$개의 줄에는 현재 지하철 시스템의 선로가 주어진다. 각 선로는 공백으로 구분된 두 정수 $a$, $b$로 나타낸다. 두 정수는 해당 선로가 연결하는 역에 0부터 매긴 번호이며, $0 \leq a, b \leq N-1$을 만족한다. 주어진 선로들을 차례로 이용해 임의의 두 역 사이를 이동할 수 있다.

다음 $N - 1$개의 줄에는 새로운 지하철 시스템에 포함되어야 하는 선로가 같은 형식으로 주어진다.

먼저 건설 계획에 필요한 주말의 수 $K$를 출력한다. 그다음 시간 순서대로 각 주말에 대해 한 줄씩, $K$개의 줄을 출력한다. 각 줄에는 네 정수 $a_1, b_1, a_2, b_2$를 출력한다. 이는 $a_1$와 $b_1$를 연결하는 선로를 폐쇄하고, $a_2$와 $b_2$를 연결하는 선로를 건설해야 한다는 뜻이다.