피기(여가 시간에 성간 연결 프로토콜 위원회를 관리함)는 까다로운 하드웨어 난제에 직면해 있습니다. $n$개의 중계소가 $(n - 1)$개의 광섬유 링크로 연결되어 트리 구조를 이루는 최신 통신망이 마침내 배치를 앞두고 있습니다. 하지만 이 시스템은 극도로 신중하게 전원을 켜야 합니다.
활성화 과정은 특정 경로를 따라 레이저 펄스를 발사하는 방식으로 진행됩니다. 경로란 두 중계소 사이의 유일한 단순 경로로 정의됩니다. 위원회의 변호사들이 밤잠을 설치게 만드는 현상인 "양자 역류 간섭(Quantum Backflow Interference)"의 치명적인 위험 때문에, 다음 프로토콜을 엄격히 준수해야 합니다:
- 전송 경로는 하나씩 차례대로 구축해야 합니다.
- 전력 급증을 방지하기 위해, 새로 구축하는 각 경로는 이전 경로들에 의해 이미 활성화된 중계소 집합과 최대 하나의 중계소만 공유할 수 있습니다.
형식적으로, 현재 활성화된 중계소들의 집합을 $S$라 합시다. 중계소 집합 $V(P)$로 이루어진 새로운 경로 $P$에 대하여 $|V(P) \cap S| \le 1$ 조건이 성립해야 합니다. 한 경로에 성공적으로 펄스가 발사되면, 그 경로 위의 모든 중계소는 활성화된 집합 $S$에 포함된 것으로 간주됩니다.
여러분의 임무는 전체 네트워크의 모든 중계소를 활성화하는 데 필요한 레이저 펄스의 최소 횟수를 구하고, 법무팀을 만족시킬 수 있는 그러한 경로들의 수열을 하나 제시하는 것입니다.

처음 두 예제 테스트 케이스의 그림입니다. Case 2에서 두 번째 펄스는 첫 번째 펄스와 중계소 $2$만 공유하므로 비간섭 규칙을 만족함에 유의하세요.
입력
입력은 여러 개의 테스트 케이스로 구성됩니다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 각 테스트 케이스에 대하여:
첫째 줄에 통신망의 중계소 개수를 나타내는 정수 $n$ ($2 \le n \le 3 \times 10^5$)이 주어집니다.
다음 $(n - 1)$개의 줄 중 $i$번째 줄에는 두 정수 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)가 주어지며, 이는 중계소 $u_i$와 중계소 $v_i$ 사이의 양방향 광섬유 링크를 나타냅니다.
주어지는 링크들은 트리를 이루며, 모든 테스트 케이스에서 $n$의 합은 $3 \times 10^5$을 넘지 않음이 보장됩니다.
출력
각 테스트 케이스마다 첫째 줄에 경로의 최소 개수 $k$를 출력합니다. 이어서 $k$개의 줄에 걸쳐, 각 줄에 수열의 $i$번째 경로의 양 끝점을 나타내는 두 정수 $a_i$와 $b_i$를 출력합니다. 경로가 단일 중계소로 이루어진 경우 $a_i$와 $b_i$가 같을 수 있습니다.
최적의 수열이 여러 개 존재한다면, 비간섭 프로토콜을 엄격히 따르는 것 중 아무것이나 출력해도 됩니다.
예제
입력
3 3 1 2 2 3 5 1 2 2 3 2 4 2 5 7 1 2 1 3 2 4 2 5 3 6 3 7
출력
1 1 3 2 4 5 1 3 3 7 7 1 6 4 5