Partition to pairs
Partition to pairs
Space archaeologists discovered on the planet in the neighbouring star system n ancient artefacts, which they numbered from 1 to n. Each artefact has k different parameters, each parameter is characterised by an integer. The artefact i has the parameters ai,1
, ai,2
, ... ai,k
. It turned out that the first parameters for all artefacts are different: for all i ≠ j, ai,1
≠ aj,1
is satisfied, while other parameters for the artefacts may coincide.
Scientists also discovered a text according to which, in order to activate artefacts, they must be specially paired and combined. The partition of artefacts is correct if for each t from 1 to k you can choose such a number bt
that it lies on the interval between the values of t-th parameter of artefacts of each pair. That is, artefacts i and j form a pair, if holds the condition ai,t
≤ bt
≤ aj,t
or the condition ai,t
≥ bt
≥ aj,t
.
Now scientists want to find out if the text is correctly decrypted. To do this, you need to check whether there is a correct splitting of artefacts into pairs. Each artefact must enter exactly one pair in the split.
Write a program that, according to the description of the parameters of the artefacts, determines whether it is possible to split them into pairs so that for each parameter there is a value lying between the values of this parameter of the artefacts of each pair, and in the case of a positive answer displays such partition.
Input
First line contains integers n and k (2 ≤ n ≤ 2 * 105
, n is even, 1 ≤ k ≤ 7) - number of artefacts and number of parameters. Each of the next n lines contains k integers ai,1
, ai,2
, ..., ai,k
- the parameters of artefacts (-109
≤ ai,j
≤ 109
, all values of ai,1
are different).
Output
Print "NO" if the required pairing does not exist.
Otherwise, print "YES" in the first line. Then print n / 2 lines, in each line print two numbers - the numbers of artefacts that make a pair. Each artefact must be displayed exactly once.
If there are several valid pairs of artefacts, output any of them.
6 2 8 6 1 5 6 3 3 1 4 7 7 2
YES 4 1 5 6 2 3
4 3 1 -1 -1 2 1 1 3 -1 1 4 1 -1
NO