题目描述

译自 ROI Regional 2019 Day2 T4. Разбиение на пары

宇宙考古学家在邻近星系的一颗行星上发现了 $n$ 件古代文物，并将它们编号为 $1$ 到 $n$。每件文物有 $k$ 个不同的参数，每个参数都是一个整数。文物 $i$ 的参数为 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, k}$。发现所有文物的第一个参数都是不同的：对于所有 $i \neq j$，都有 $a_{i, 1} \neq a_{j, 1}$，但其他参数可能相同。

科学家们还发现了一段文字，根据这段文字，要激活文物，需要将它们按特定方式配对。配对是有效的，如果对于每个参数 $t$ 从 $1$ 到 $k$，可以选择一个数 $b_{t}$，使其在每对文物的第 $t$ 个参数值之间。也就是说，如果文物 $i$ 和 $j$ 配对，必须满足 $a_{i, t} \leq b_{t} \leq a_{j, t}$ 或 $a_{i, t} \geq b_{t} \geq a_{j, t}$。

现在，科学家们想知道这段文字是否解读正确。为此，需要检查是否存在有效的配对方式，使得每个文物恰好属于一个配对。

编写一个程序，根据文物的参数描述，确定是否可以将它们有效配对。如果可以，输出配对方式。

输入格式

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 2 \cdot 10^5$，$n$ 为偶数，$1 \leq k \leq 7$），表示文物数量和参数数量。

接下来的 $n$ 行中，每行包含 $k$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, k}$（$-10^9 \leq a_{i, j} \leq 10^9$，所有 $a_{i, 1}$ 都不同），表示文物的参数。

输出格式

如果不存在有效的配对方式，输出 NO。

否则，第一行输出 YES。接下来输出 $n / 2$ 行，每行包含两个整数，表示配对的文物编号。每个文物只能出现一次。

如果存在多个有效的配对方式，可以输出任意一个。

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

YES
1 4
2 6
3 5

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

NO

数据范围与提示

详细子任务附加限制及分值如下表所示。