Ancient Artifact Pairing

In a distant galaxy, cosmic archaeologists have discovered n ancient artifacts on a planet in a neighboring system. The artifacts are numbered from 1 to n. Each artifact has k different integer parameters. The i-th artifact has parameters \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\). It is known that all artifacts have distinct first parameters, i.e. for any two artifacts \(i \neq j\), \(a_{i,1} \neq a_{j,1}\), while the other parameters might repeat.

The scientists found an ancient inscription that suggests a way to activate the artifacts. According to the inscription, a pairing scheme is valid if and only if there exist numbers \(b_1, b_2, \dots, b_k\) (one for each parameter) such that for every pair of artifacts \((i,j)\) in the pairing, for every index \(t\) with \(1 \le t \le k\) it holds that either \[ a_{i,t} \le b_t \le a_{j,t} \quad\text{or}\quad a_{i,t} \ge b_t \ge a_{j,t}, \] i.e. \(b_t\) lies in the closed interval between \(a_{i,t}\) and \(a_{j,t}\).

Your task is to determine whether there exists a valid pairing scheme that pairs all the n artifacts (note that n is even) and, if one exists, to output such a pairing.

Hint: Since the first parameter is distinct for all artifacts, a natural idea is to sort the artifacts by \(a_{i,1}\). One promising pairing is to match the artifact with the smallest \(a_{i,1}\) with the one having the largest \(a_{i,1}\), the second smallest with the second largest, and so on. For each parameter \(t\), if you denote a pair by \((i,j)\) and define its interval as \([\min\{a_{i,t},a_{j,t}\}, \max\{a_{i,t},a_{j,t}\}]\), then a valid pairing must satisfy \[ \max_{\text{pairs}}\{\min(a_{i,t}, a_{j,t})\} \le \min_{\text{pairs}}\{\max(a_{i,t}, a_{j,t})\} \] for every \(t\); in that case, you may choose any \(b_t\) from the resulting intersection.

inputFormat

The first line contains two integers n and k (with n even), representing the number of artifacts and the number of parameters, respectively.

The next n lines each contain k integers. The i-th line gives the parameters \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\) of the i-th artifact.

outputFormat

If a valid pairing exists, output “YES” on the first line. Then output n/2 lines, each containing two integers representing the indices of the paired artifacts.

If no valid pairing scheme exists, simply output “NO”.

sample

4 2
1 3
4 2
2 1
5 4

NO