Piggy(여가 시간에 성간 연결 프로토콜 위원회를 관리하는 인물)는 까다로운 하드웨어 난제에 직면해 있습니다. $n$개의 중계국이 $(n-1)$개의 광섬유 링크로 연결되어 트리 구조를 이루는 최신 통신망이 드디어 배포 준비를 마쳤습니다. 하지만 이 시스템은 매우 신중하게 전원을 켜야 합니다.

활성화 과정은 특정 경로를 따라 레이저 펄스를 발사하는 방식으로 이루어집니다. 경로는 두 정거장 사이의 유일한 단순 경로로 정의됩니다. "양자 역류 간섭(Quantum Backflow Interference)"이라는, 위원회 변호사들을 밤잠 설치게 만드는 현상에 대한 치명적인 위험 때문에 다음 프로토콜을 엄격히 준수해야 합니다.

• 전송 경로는 하나씩 순차적으로 설정되어야 합니다.
• 전력 급증을 방지하기 위해, 새로 설정되는 각 경로는 이미 활성화된 경로들의 집합과 최대 하나의 정거장만을 공유할 수 있습니다.

형식적으로, 현재 활성화된 정거장의 집합을 $S$라고 합시다. 정거장 집합 $V(P)$로 구성된 새로운 경로 $P$에 대해, $|V(P) \cap S| \le 1$이라는 조건이 성립해야 합니다. 경로가 성공적으로 발사되면, 해당 경로상의 모든 정거장은 활성화된 집합 $S$의 일부로 간주됩니다.

당신의 임무는 전체 네트워크의 모든 정거장을 활성화하는 데 필요한 최소 레이저 펄스 수를 결정하고, 법무팀을 만족시킬 수 있는 경로 시퀀스 하나를 제시하는 것입니다.

첫 두 개의 샘플 테스트 케이스에 대한 예시입니다. 케이스 2에서 두 번째 펄스는 첫 번째 펄스와 오직 2번 정거장만을 공유하며, 이는 비간섭 규칙을 만족합니다.

입력

여러 테스트 케이스가 존재합니다. 입력의 첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ ($1 \le T \le 10^4$)가 주어집니다. 각 테스트 케이스에 대하여:

첫 번째 줄에는 그리드 내 정거장의 수인 정수 $n$ ($2 \le n \le 3 \times 10^5$)이 주어집니다.

이어지는 $(n-1)$개의 줄에는 정거장 $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$를 출력하십시오. 그 다음, 시퀀스에서 $i$번째 경로의 끝점을 나타내는 두 정수 $a_i$와 $b_i$를 포함하는 $k$개의 줄을 출력하십시오. 경로가 단일 정거장으로 구성된 경우 $a_i$는 $b_i$와 같을 수 있음에 유의하십시오.

최적의 시퀀스가 여러 개 존재할 경우, 비간섭 프로토콜을 엄격히 따르는 어떤 시퀀스라도 허용됩니다.

예제

입력 1

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
1 3
2
4 5
1 3
3
7 7
1 6
4 5