1. #include <iostream>
2. #include <fstream>
3. #include <algorithm>
4. #include <vector>
5.  
6. int main() {
7.         int n, dim;
8.         std::cin >> n >> dim;
9.  
10.         std::vector<std::vector<int>> a(n, std::vector<int>(dim + 1, 0));
11.  
12.         for (int i = 0; i < n; i++) {
13.                 a[i][0] = i + 1;
14.                 for (int j = 1; j < dim + 1; j++) {
15.                         std::cin >> a[i][j];
16.                         a[i][j] *= 2;
17.                 }
18.         }
19.  
20.         int* b = new int[dim + 1]();
21.         int mid1, mid2;
22.         for (int i = 1; i < dim + 1; i++) {
23.                 std::nth_element(a.begin(), a.begin() + n / 2, a.end(),
24.                         [&](const std::vector<int>& left, const std::vector<int>& right) {
25.                                 return left[i] < right[i];
26.                         }
27.                 );
28.  
29.                 std::nth_element(a.begin(), a.begin() + n / 2 - 1, a.begin() + n / 2,
30.                         [&](const std::vector<int>& left, const std::vector<int>& right) {
31.                                 return left[i] < right[i];
32.                         }
33.                 );
34.  
35.                 mid1 = a[n / 2 - 1][i];
36.                 mid2 = a[n / 2][i];
37.                 b[i] = int((long long (mid1) + long long(mid2)) / 2);
38.         }
39.  
40.         int powdim = pow(3, dim);
41.         std::vector<std::vector<int>> group(powdim);
42.  
43.         int code, digit;
44.         for (int i = 0; i < n; i++) {
45.                 code = 0;
46.  
47.                 for (int j = 1; j < dim + 1; j++) {
48.                         digit = (a[i][j] < b[j]) ? 0 : ((a[i][j] == b[j]) ? 1 : 2);
49.  
50.                         code = code * 3 + digit;
51.                 }
52.  
53.                 group[code].push_back(a[i][0]);
54.         }
55.  
56.         const int SOURCE = powdim;
57.         const int SINK = powdim + 1;
58.  
59.         int** cap = new int*[powdim + 2];
60.         int** flow = new int*[powdim + 2];
61.         std::vector<std::vector<int>> next(powdim + 2);
62.         for (int i = 0; i < powdim + 2; i++) {
63.                 cap[i] = new int[powdim + 2]();
64.                 flow[i] = new int[powdim + 2]();
65.         }
66.  
67.         int fstdigit;
68.         for (code = 0; code < powdim; code++) {
69.                 fstdigit = code / (powdim / 3);
70.  
71.                 if (!group[code].empty()) {
72.                         if (fstdigit == 0) {
73.                                 cap[SOURCE][code] = group[code].size();
74.                                 next[SOURCE].push_back(code);
75.                                 next[code].push_back(SOURCE);
76.                         }
77.                         else {
78.                                 cap[code][SINK] = group[code].size();
79.                                 next[code].push_back(SINK);
80.                                 next[SINK].push_back(code);
81.                         }
82.                 }
83.         }
84.  
85.         bool compat;
86.         int cop1, cop2, dig1, dig2;
87.         for (int c1 = 0; c1 < powdim / 3; c1++) {
88.                 for (int c2 = 2 * powdim / 3; c2 < powdim; c2++) {
89.                         cop1 = c1;
90.                         cop2 = c2;
91.                         compat = true;
92.  
93.                         for (int i = 1; i < dim + 1; i++) {
94.                                 dig1 = cop1 % 3;
95.                                 dig2 = cop2 % 3;
96.                                 cop1 /= 3;
97.                                 cop2 /= 3;
98.  
99.                                 if ((dig1 == 0 && dig2 == 0) || (dig1 == 2 && dig2 == 2)) {
100.                                         compat = false;
101.                                         break;
102.                                 }
103.                         }
104.  
105.                         if (compat) {
106.                                 cap[c1][c2] = std::min(group[c1].size(), group[c2].size());
107.                                 next[c1].push_back(c2);
108.                                 next[c2].push_back(c1);
109.                         }
110.                 }
111.         }
112.  
113.         int* height = new int[powdim + 2]();
114.         int* excess = new int[powdim + 2]();
115.         for (int c = 0; c < powdim; c++)
116.                 height[SOURCE] += (!group[c].empty()) ? 1 : 0;
117.  
118.         height[SOURCE]++;
119.  
120.         std::vector<std::vector<int>> heightExcessCodes(1 + 2 * height[SOURCE]);
121.         for (int c = 0; c < powdim; c++) {
122.                 if (cap[SOURCE][c] > 0) {
123.                         excess[c] = cap[SOURCE][c];
124.                         flow[SOURCE][c] = cap[SOURCE][c];
125.                         flow[c][SOURCE] = -cap[SOURCE][c];
126.                         heightExcessCodes[height[c]].push_back(c);
127.                 }
128.         }
129.  
130.         int h, f, extra, minHeight;
131.         while (true) {
132.                 h = heightExcessCodes.size() - 1;
133.  
134.                 while (h >= 0 && heightExcessCodes[h].empty())
135.                         h--;
136.  
137.                 if (h < 0)
138.                         break;
139.  
140.                 f = heightExcessCodes[h].back();
141.                 heightExcessCodes[h].pop_back();
142.  
143.                 while (true) {
144.                         for (int to : next[f]) {
145.                                 if (height[to] < height[f] && flow[f][to] < cap[f][to]) {
146.                                         extra = std::min(cap[f][to] - flow[f][to], excess[f]);
147.  
148.                                         if ((excess[to] == 0) && to != SINK && to != SOURCE)
149.                                                 heightExcessCodes[height[to]].push_back(to);
150.  
151.                                         flow[f][to] += extra;
152.                                         flow[to][f] = -flow[f][to];
153.                                         excess[f] -= extra;
154.                                         excess[to] += extra;
155.  
156.                                         if (excess[f] == 0)
157.                                                 break;
158.                                 }
159.                         }
160.  
161.                         if (excess[f] == 0)
162.                                 break;
163.  
164.                         minHeight = 2 * height[SOURCE];
165.                         for (int to : next[f]) {
166.                                 if (flow[f][to] < cap[f][to])
167.                                         minHeight = std::min(minHeight, height[to]);
168.                         }
169.  
170.                         height[f] = minHeight + 1;
171.                 }
172.         }
173.  
174.         if (excess[SINK] != n / 2) {
175.                 std::cout << "NO";
176.                 return 0;
177.         }
178.  
179.         std::cout << "YES" << '\n';
180.  
181.         int id1, id2;
182.         for (int c1 = 0; c1 < powdim / 3; c1++) {
183.                 for (int c2 = 2 * powdim / 3; c2 < powdim; c2++) {
184.                         while (flow[c1][c2] > 0) {
185.                                 flow[c1][c2]--;
186.  
187.                                 id1 = group[c1].back();
188.                                 group[c1].pop_back();
189.  
190.                                 id2 = group[c2].back();
191.                                 group[c2].pop_back();
192.  
193.                                 std::cout << id1 << ' ' << id2 << '\n';
194.                         }
195.                 }
196.         }
197.  
198.         delete[] b;
199.         delete[] height;
200.         delete[] excess;
201.  
202.         for (int i = 0; i < powdim + 2; i++) {
203.                 delete[] flow[i];
204.                 delete[] cap[i];
205.         }
206.         delete[] flow;
207.         delete[] cap;
208.        
209.         return 0;
210. }