Alice와 Bob은 각각 정수가 하나씩 적힌 $2n$장의 카드를 가지고 있으며, $1$부터 $n$까지의 각 정수는 정확히 두 장의 카드에 적혀 있습니다. 처음에 Alice와 Bob은 각각 $n$장의 카드를 들고 있습니다.
두 사람은 카드 게임을 하려고 하며, Alice가 먼저 시작합니다. 매 턴마다 현재 차례인 플레이어는 손에 있는 카드 중 한 장을 카드 더미의 맨 위에 놓습니다. 만약 카드 더미에 같은 숫자가 적힌 카드가 두 장 있게 되면, 현재 플레이어는 $1$점을 얻고 그 두 장의 카드와 그 사이에 있는 모든 카드를 제거하여 버림 더미에 놓습니다.
Alice가 카드를 내는 순서가 주어질 때, Bob은 Alice의 점수를 최소화하기 위해 자신의 카드를 어떤 순서로 내야 할까요?
입력
첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다.
각 테스트 케이스에 대해, 첫 번째 줄에 정수 $n$ ($1 \le n \le 5 \times 10^5$)이 주어집니다.
두 번째 줄에 Alice가 순서대로 내는 카드에 적힌 숫자를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어집니다. 어떤 숫자도 $a_i$에 두 번을 초과하여 나타나지 않음이 보장됩니다.
모든 테스트 케이스에서 $n$의 합은 $5 \times 10^5$을 초과하지 않음이 보장됩니다.
출력
각 테스트 케이스마다 첫 번째 줄에 Alice가 얻을 수 있는 최소 점수를 나타내는 정수를 출력합니다.
두 번째 줄에 Bob이 순서대로 내는 카드를 나타내는 $n$개의 정수 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$)을 출력합니다. 이때 $1$부터 $n$까지의 각 정수는 $a_i$와 $b_i$를 합친 수열에서 정확히 두 번씩 나타나야 합니다.
예제
입력
3 3 1 2 3 5 3 1 4 1 5 5 1 4 5 1 4
출력
0 1 2 3 0 2 3 2 4 5 1 3 2 2 3 5
노트
세 번째 테스트 케이스에서 게임은 다음과 같이 진행됩니다:
| 단계 | 플레이어 | 낸 카드 | 아래에서 위로 본 카드 더미 | Alice의 점수 | Bob의 점수 |
|---|---|---|---|---|---|
| $1$ | Alice | $1$ | $[1]$ | $0$ | $0$ |
| $2$ | Bob | $3$ | $[1, 3]$ | $0$ | $0$ |
| $3$ | Alice | $4$ | $[1, 3, 4]$ | $0$ | $0$ |
| $4$ | Bob | $2$ | $[1, 3, 4, 2]$ | $0$ | $0$ |
| $5$ | Alice | $5$ | $[1, 3, 4, 2, 5]$ | $0$ | $0$ |
| $6$ | Bob | $2$ | $[1, 3, 4]$ | $0$ | $1$ |
| $7$ | Alice | $1$ | $[]$ | $1$ | $1$ |
| $8$ | Bob | $3$ | $[3]$ | $1$ | $1$ |
| $9$ | Alice | $4$ | $[3, 4]$ | $1$ | $1$ |
| $10$ | Bob | $5$ | $[3, 4, 5]$ | $1$ | $1$ |