题目描述

Given a list $X$, consisting of the numbers $(1, 2, \ldots, N)$, an increasing subsequence is a subset of these numbers which appears in increasing order, and a decreasing subsequence is a subset of those numbers which appears in decreasing order. For example, $(5, 7, 8)$ is an increasing subsequence of $(4, 5, 3, 7, 6, 2, 8, 1)$.

Nearly 80 years ago, two mathematicians, Paul Erdős and George Szekeres proved a famous result: $X$ is guaranteed to have either an increasing subsequence of length at least $\sqrt{N}$ or a decreasing subsequence of length of at least $\sqrt{N}$. For example, $(4, 5, 3, 7, 6, 2, 8, 1)$ has a decreasing subsequence of length 4: $(5, 3, 2, 1)$.

I am teaching a combinatorics class, and I want to "prove" this theorem to my class by example. For every number $X[i]$ in the sequence, I will calculate two values:

• $A[i]$: The length of the longest increasing subsequence of $X$ that includes $X[i]$ as its largest number.
• $B[i]$: The length of the longest decreasing subsequence of $X$ that includes $X[i]$ as its largest number.

The key part of my proof will be that the pair $(A[i], B[i])$ is different for every i, and this implies that either $A[i]$ or $B[i]$ must be at least $\sqrt{N}$ for some i. For the sequence listed above, here are all the values of $A[i]$ and $B[i]$:

$i$	$X[i]$	$A[i]$	$B[i]$
0	4	1	4
1	5	2
2	3	1	3
3	7	3	4
4	6		3
5	2	1	2
6	8	4
7	1

I came up with a really interesting sequence to demonstrate this fact with, and I calculated $A[i]$ and $B[i]$ for every $i$, but then I forgot what my original sequence was. Given $A[i]$ and $B[i]$, can you help me reconstruct $X$?

$X$ should consist of the numbers $(1, 2, \ldots, N)$ in some order, and if there are multiple sequences possible, you should choose the one that is lexicographically smallest. This means that $X[0]$ should be as small as possible, and if there are still multiple solutions, then $X[1]$ should be as small as possible, and so on.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, each consisting of three lines.

The first line of each test case contains a single integer $N$. The second line contains $N$ positive integers separated by spaces, representing $A[0], A[1], \dots, A[N-1]$. The third line also contains $N$ positive integers separated by spaces, representing $B[0], B[1], \dots, B[N-1]$.

输出格式

For each test case, output one line containing "Case #x: ", followed by $X[0], X[1], \dots X[N-1]$ in order, and separated by spaces.

2
1
1
1
8
1 2 1 3 3 1 4 1
4 4 3 4 3 2 2 1

Case #1: 1
Case #2: 4 5 3 7 6 2 8 1

提示

Limits

• $1 \leq T \leq 30$.
• It is guaranteed that there is at least one possible solution for $X$.

Small dataset (9 Pts, Test set 1 - Visible)

• $1 \leq N \leq 20$.

Large dataset (15 Pts, Test set 2 - Hidden)

• $1 \leq N \leq 2000$.