Movie Theater

时间限制：2s
空间限制：512MB

题目描述

一家电影院有 $N$ 个从左到右排成一列的座位，依次编号为 $1,2,\ldots,N$。有 $N$ 个人来访，你要给每人分配一个不同的座位，记人 $i$ 的座位为 $P_i$。人 $i$ 在时刻 $L_i$ 到达，依次经过座位 $1,2,\ldots,P_i-1$ 后坐到 $P_i$；在时刻 $R_i$ 离开，同样经过座位 $1,2,\ldots,P_i-1$。

人 $i$ 的不满度，是在开区间 $(L_i,R_i)$ 内其他人经过座位 $P_i$ 的次数。在使所有人不满度总和最小的所有排列 $P$ 中，求字典序最小的一个。需要处理 $T$ 组测试。

输入格式

第一行包含测试组数 $T$。每组测试先输入一个整数 $N$，随后 $N$ 行每行包含两个整数 $L_i,R_i$。

输出格式

对每组测试输出一行，以空格分隔输出所求排列 $P_1,P_2,\ldots,P_N$。

样例输入 1

3
3
1 5
2 3
4 6
4
1 5
2 6
3 7
4 8
6
6 10
2 11
7 8
1 9
3 4
5 12

样例输出 1

2 1 3
1 2 3 4
2 4 1 5 3 6

数据范围

• $1\le T\le 500$。
• $1\le N\le 500$。
• $1\le L_i<R_i\le 2N$。
• 同一组测试中的 $L_1,\ldots,L_N,R_1,\ldots,R_N$ 两两不同。
• 所有测试中 $N$ 的总和不超过 $500$。