题目描述

假设$n$个男生,$n$个女生(总共$2 \times n$人)。每个男生与每个女生都列了一张属于自己的表,这张表上面是他对$n$个异性好感度的排名。

男生是主动的,女生是被动的。男生会按照自己的那张具有优先度的表,向最喜欢的女生表白。

• 若被表白的女生没有男朋友,他们将会在一起。
• 若有男朋友,女生会选择她更喜欢的男生作为她男朋友(根据她手上的那张具有优先度的表)。

若男生失败了,就会找下一个最喜欢的女生。

(未到法定年龄人员均请勿模仿)。

每个人都有一个编号,男生为$1,2,...,n$,女生为$n+1,n+2,...,2×n$。现给出每个人列出的表,从$1$号男生开始表白,求$n$号男生表白完时,每个人的对象情况。(可证明每人一定会有)

输入格式

第一行,一个非负整数$n$。 接下来$2×n$行,每行$n$个整数,表示第$i$个人列的表。

输出格式

$n$行,每行为两个整数$a$和$b$,表示$a$和$b$在一起了(按$\color{red} b$的大小排序(出题人就是个女权。不按套路出牌))(呕

4
5 8 7 6
7 8 5 6
6 7 8 5
7 5 8 6
1 4 2 3
3 2 4 1
4 2 1 3
4 2 3 1

1 5
3 6
4 7
2 8

数据范围

$0≤n≤\frac{1000}{2}$