에르되시–세케레시

숫자 (1, 2, ..., N)으로 이루어진 목록 X가 주어질 때, 증가 부분 수열은 이 숫자들 가운데 증가하는 순서로 나타나는 부분집합이고, 감소 부분 수열은 이 숫자들 가운데 감소하는 순서로 나타나는 부분집합이다. 예를 들어, (5, 7, 8)는 (4, 5, 3, 7, 6, 2, 8, 1)의 증가 부분 수열이다.

거의 80년 전에 두 수학자 Paul Erdős와 George Szekeres는 유명한 결과를 증명했다. X에는 길이가 적어도 sqrt(N)인 증가 부분 수열이나 길이가 적어도 sqrt(N)인 감소 부분 수열 중 하나가 반드시 존재한다. 예를 들어, (4, 5, 3, 7, 6, 2, 8, 1)에는 길이가 4인 감소 부분 수열 (5, 3, 2, 1)이 있다.

나는 조합론 수업을 가르치고 있으며, 예시를 통해 이 정리를 학생들에게 "증명"하고 싶다. 수열의 모든 수 X[i]에 대해 다음 두 값을 계산한다.

• A[i]: X[i]를 가장 큰 수로 포함하는 X의 가장 긴 증가 부분 수열의 길이.

• B[i]: X[i]를 가장 큰 수로 포함하는 X의 가장 긴 감소 부분 수열의 길이. 내 증명의 핵심은 모든 i에 대해 순서쌍 (A[i], B[i])가 서로 다르다는 것이며, 이로부터 어떤 i에 대해서는 A[i] 또는 B[i] 중 하나가 적어도 sqrt(N)이어야 한다는 결론이 나온다. 위에 나열한 수열에 대한 A[i]와 B[i]의 모든 값은 다음과 같다.

i  |  X[i]  |  A[i]  |  B[i] 
-----+--------+--------+--------
  0  |   4    |   1    |   4
  1  |   5    |   2    |   4
  2  |   3    |   1    |   3
  3  |   7    |   3    |   4
  4  |   6    |   3    |   3
  5  |   2    |   1    |   2
  6  |   8    |   4    |   2
  7  |   1    |   1    |   1

이 사실을 보여 주기 위해 정말 흥미로운 수열을 생각해 냈고, 모든 i에 대해 A[i]와 B[i]를 계산했지만, 그 뒤 원래 수열이 무엇이었는지 잊어버렸다. A[i]와 B[i]가 주어질 때, X를 복원하는 것을 도와줄 수 있는가?

X는 숫자 (1, 2, ..., N)을 어떤 순서로 나열한 것이어야 하며, 가능한 수열이 여러 개라면 사전순으로 가장 작은 것을 선택해야 한다. 이는 X[0]가 가능한 한 작아야 하고, 그래도 해가 여러 개라면 X[1]가 가능한 한 작아야 하며, 이후도 같은 방식임을 뜻한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 30. X에 대해 가능한 해가 적어도 하나 존재함이 보장된다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 20.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 2000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 각각 세 줄로 이루어진 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 N 하나가 주어진다. 둘째 줄에는 A[0], A[1], ..., A[N-1]를 나타내는 N개의 양의 정수가 공백으로 구분되어 주어진다. 셋째 줄에도 B[0], B[1], ..., B[N-1]를 나타내는 N개의 양의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: "에 이어 X[0], X[1], ... X[N-1]를 순서대로 공백으로 구분하여 한 줄에 출력한다.