지하철

스톡홀름 지하철은 비효율적으로 운영되고 있다. 현재 노선이 건설되던 당시와 도시의 모습이 달라져서, 일부 구간은 과부하 상태이고 일부 노선은 거의 이용되지 않는다.

이에 시의회는 지하철을 재건설하기로 했다. 현재 시스템은 $N$개의 역으로 이루어져 있으며, $N - 1$쌍의 역이 선로로 연결되어 있어서 임의의 두 역 사이를 지하철로 이동할 수 있다. 시의회는 같은 $N$개의 역에 대해, 모든 역이 연결되도록 하는 또 다른 $N - 1$개의 선로 집합으로 이루어진 새로운 계획을 세웠다.

이용객이 많은 지하철의 혼잡을 최소화하기 위해, 재건설은 한 번에 하나의 선로씩 진행해야 한다. 매 주말마다 정확히 하나의 선로를 폐쇄하고 하나의 새로운 선로를 건설한다. 따라서 선로는 항상 $N - 1$개가 유지된다. 또한 각 주말의 공사가 끝난 뒤에도 임의의 두 역 사이를 이동할 수 있어야 한다.

새로운 지하철 네트워크를 위 조건을 만족하면서 건설하는 방법을 찾아라. 계획에 필요한 주말 수를 가능한 한 적게 해야 한다.

첫 번째 줄에는 정수 $N$이 주어진다. $N$은 $1$ 이상이다. 다음 $N - 1$개의 줄에는 현재 지하철 시스템의 선로가 주어진다. 각 선로는 공백으로 구분된 두 정수 $a$ $b$로 기술되며, 선로가 연결하는 역의 번호이다. 역 번호는 $0$부터 $N - 1$까지이며 $0$부터 시작한다. 이들 선로를 이용해서 임의의 두 역 사이를 이동할 수 있다.

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

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

각 주말이 끝난 뒤에는 선로가 정확히 $N - 1$개이며 모든 역이 연결되어 있어야 하고, 마지막 주말이 끝난 뒤의 네트워크는 목표 네트워크와 일치해야 한다. 조건을 만족하는 계획 중에서 주말 수가 가장 적은 것을 출력한다.