题目描述

称一个由非零整数构成的序列 $[a_1,a_2,\ldots,a_n]$ 是“括号序列 2”，当且仅当满足如下三者之一：

1. $n=0$；
2. 存在 $1\le k<n$，使得 $[a_1,a_2,\ldots,a_k]$ 和 $[a_{k+1},a_{k+2},\ldots,a_n]$ 都是“括号序列 2”；
3. $a_1=-a_n>0$，且 $[a_2,a_3,\ldots,a_{n-1}]$ 是“括号序列 2”。

给定 $2n$ 个二元组 $(u_i,v_i)$，保证

$$\{u_1,u_2,\ldots,u_{2n}\} = \{v_1,v_2,\ldots,v_{2n}\} = \{1,-1,2,-2,\ldots,n,-n\},$$

你需要找到一个大小为 $2n$ 的排列 $p_1,p_2,\ldots,p_{2n}$，使得下列两个条件同时成立：

$$[u_{p_1},u_{p_2},\ldots,u_{p_{2n}}]$$

是“括号序列 2”；

$$[v_{p_1},v_{p_2},\ldots,v_{p_{2n}}]$$

也是“括号序列 2”。

给出一组构造，或说明无解。

输入格式

第一行包含一个正整数 $n$。

接下来 $2n$ 行，每行两个非零整数 $u_i,v_i$，表示一个二元组。

输出格式

如果不存在满足条件的排列 $p$，输出一行一个整数 $-1$。

否则，输出一行，包含 $2n$ 个整数，表示所求的排列 $p_1,p_2,\ldots,p_{2n}$。如果有多组解，输出任意一组均可。

样例一

输入

2
-2 -2
-1 2
1 1
2 -1

输出

-1

样例二

输入

5
-5 -2
-4 4
-3 -5
-2 5
-1 -4
1 3
2 2
3 -1
4 -3
5 1

输出

6 9 2 5 10 8 7 4 3 1

解释

对于该输出，有：

$$[u_{p_1},u_{p_2},\ldots,u_{p_{2n}}] = [1,4,-4,-1,5,3,2,-2,-3,-5];$$$$[v_{p_1},v_{p_2},\ldots,v_{p_{2n}}] = [3,-3,4,-4,1,-1,2,5,-5,-2].$$

限制与约定

对于所有的测试点，保证：

$$1\le n\le 2\times 10^5,$$

且

$$\{u_1,u_2,\ldots,u_{2n}\} = \{v_1,v_2,\ldots,v_{2n}\} = \{1,-1,2,-2,\ldots,n,-n\}.$$

• 对于前 $10\%$ 的数据，保证 $n\le 10$；
• 对于另外 $5\%$ 的数据，保证 $u_i=v_i$；
• 对于另外 $10\%$ 的数据，保证 $u_i\cdot v_i>0$；
• 对于另外 $20\%$ 的数据，保证 $n\le 100$；
• 对于另外 $30\%$ 的数据，保证 $n\le 2000$。

时间限制：$1.5\text{s}$

空间限制：$512\text{MB}$