#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/4/problems/E

Repovive

Permute Intervals - Repovive Standard Round 1 (Sponsored by TIG Foundation) | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

4E. Permute Intervals

2500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

You are given $n$ closed intervals $[l_i, r_i]$ .

You want to choose a permutation $p_1, p_2, \ldots, p_n$ of $\{1,2,\ldots,n\}$ such that there exists an array $a_1, a_2, \ldots, a_n$ satisfying:

$l_i \le a_i \le r_i$ for each $1 \le i \le n$ ,
$a_{p_i} \le a_{p_{i+1}}$ for each $1 \le i < n$ .

Among all permutations $p$ for which such an array $a$ exists, output the lexicographically smallest permutation.

It is guaranteed that at least one valid permutation exists.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le l_i \le r_i \le 10^9$

Input

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Explanation

Case 1

Scenario 1: $n=3$ , intervals $[1,3], [2,4], [3,5]$ . Answer: $1\ 2\ 3$ . Witness: $a = [1, 2, 3]$ . Reading in permutation order: $a_1=1 \le a_2=2 \le a_3=3$ . All values in range. The identity permutation works because the intervals already overlap in increasing order. All $6$ permutations are valid (intervals overlap heavily), but $1\ 2\ 3$ is lexicographically smallest.

Case 2

Scenario 2: $n=3$ , intervals $[5,7], [1,3], [2,4]$ . Answer: $2\ 3\ 1$ . Witness: $a = [5, 1, 2]$ . Reading in permutation order: $a_2=1 \le a_3=2 \le a_1=5$ . Interval $1$ has high values $[5,7]$ while intervals $2,3$ have low values, so index $1$ must come last. Only $2$ valid permutations exist: $2\ 3\ 1$ and $3\ 2\ 1$ . Lexicographically smallest is $2\ 3\ 1$ .

Case 3

Scenario 3: $n=4$ , intervals $[2,4], [1,3], [5,7], [1,2]$ . Answer: $1\ 2\ 4\ 3$ . Witness: $a = [2, 2, 5, 2]$ . Reading in permutation order: $a_1=2 \le a_2=2 \le a_4=2 \le a_3=5$ . Interval $3=[5,7]$ has high values so must come last. Among the remaining, index $4=[1,2]$ fits before $3$ . There are $6$ valid permutations; $1\ 2\ 4\ 3$ is lexicographically smallest.

Output

Case 1

1 2 3

Case 2

2 3 1

Case 3

1 2 4 3

You are given $n$ closed intervals $[l_i, r_i]$ .

You want to choose a permutation $p_1, p_2, \ldots, p_n$ of $\{1,2,\ldots,n\}$ such that there exists an array $a_1, a_2, \ldots, a_n$ satisfying:

$l_i \le a_i \le r_i$ for each $1 \le i \le n$ ,
$a_{p_i} \le a_{p_{i+1}}$ for each $1 \le i < n$ .

Among all permutations $p$ for which such an array $a$ exists, output the lexicographically smallest permutation.

It is guaranteed that at least one valid permutation exists.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le l_i \le r_i \le 10^9$

t

\left. \begin{array}{l} n \\ l_1 \quad r_1 \\ l_2 \quad r_2 \\ \vdots \\ l_n \quad r_n \end{array} \right\} \times t

\left. \begin{array}{l} p_1 \quad p_2 \quad \cdots \quad p_n \end{array} \right\} \times t