비상 대응 계획 2

ICPC 회사에서 관리자로 일한다. 회사 건물에는 $N$대의 컴퓨터가 있으며 1번부터 $N$번까지 번호가 붙어 있다. $N-1$개의 케이블이 모든 컴퓨터를 하나의 네트워크로 연결하고, 케이블에도 1번부터 $N-1$번까지 번호가 붙어 있다. $i$번 케이블은 컴퓨터 $U_i$와 $V_i$를 잇는다. 각 케이블은 비상 모드로 설정할 수 있으며, 이때 $i$번 케이블은 $U_i$에서 $V_i$로만 데이터를 전달하고 반대 방향으로는 전달하지 않는다. 재난 중에는 모든 케이블이 반드시 비상 모드여야 한다.

네트워크의 취약성을 판단하는 새로운 방법을 찾았다. 재난 중에 네트워크가 취약하지 않도록 새 케이블을 0개 이상 추가할 수 있다. 네트워크가 취약하지 않은 조건은, 같은 케이블로 연결된 모든 $u$와 $v$에 대해 $u$가 $v$보다 앞에 오는 1부터 $N$까지의 순열이 정확히 하나만 존재하는 것이다. 즉, 위상 정렬 결과가 정확히 하나여야 한다.

그림에서 취약하지 않은 네트워크의 유효한 순열은 왼쪽과 오른쪽에 각각 $[1, 2, 3]$과 $[3, 1, 2]$뿐이다. 취약한 네트워크는 왼쪽에 $[1, 2, 3]$과 $[3, 1, 2]$ 두 개가 있고, 오른쪽에는 유효한 순열이 없다.

네트워크를 취약하지 않게 만드는 데 필요한 새 케이블의 최소 개수와, 어떤 컴퓨터 쌍을 연결해야 하는지 구하라. 최소 개수로 연결하는 방법이 여럿이면 어느 것을 골라도 된다. 주어진 제한에서 네트워크를 취약하지 않게 만드는 방법은 항상 존재한다.

첫째 줄에 정수 $N$ ($2 \le N \le 100\,000$)이 주어진다.

이어지는 $N-1$개의 줄에 두 정수 $U_i$와 $V_i$ ($1 \le U_i, V_i \le N$)가 주어진다. 입력으로 주어지는 간선들은 트리를 이룬다.

첫째 줄에 추가할 새 케이블의 최소 개수 $K$를 출력한다. $K$가 0이 아니면 다음 $K$개의 줄에 두 정수 $A_i$와 $B_i$를 출력한다. 이는 새 케이블 $i$가 $A_i$에서 $B_i$로만 데이터를 전달한다는 뜻이다. 해가 여러 개이면 그중 아무거나 출력해도 된다.