题解何意？

实际上 $b_t$ 就是 $a_{i,t}$ 的中位数，我们只关心数与 $b_t$ 的大小关系。设 $a_{i,t}<b_t$ 为 $0$，$>$ 为 $1$，$=$ 为 $2$，那我们相当于要解决如下问题：

• 有 $n$ 个长度为 $k$ 的 $0/1/2$ 串。你需要将每个 $2$ 替换为 $0/1$，再将这 $n$ 个串匹配，使得匹配的两个串对应位不同。问是否存在完美匹配。

考虑最大流，直接暴力对 $2\times 3^{k-1}$ 种串建图。发现保证了 $a_{i,1}$ 互不相同，那么可以将所有串分为两部分，建成二分图。

以源点一侧为例，若当前这个串有 $2$，那么将最低的那个 $2$ 替换成 $0/1$，连一条流量为 $\inf$ 的边。否则，将这个串与对应的能匹配的串连边。汇点一侧同理。这样总边数为 $\mathcal{O}(3^k)$。用 Dinic 求解最大流即可做到 $\mathcal{O}(27^k)$，可以通过。当然可以像楼下说的那样用 HLPP 做到 $\mathcal{O}(9^k)$，但是太没必要了。

对于构造方案，直接顺着流量推即可。

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int MAXN = 2e5 + 10;
const int MAXM = 5e3;
const int MAXK = 1460;
const int inf = 0x3f3f3f3f;

struct edge {
	int v, c, nxt;
	edge(int v = 0, int c = 0, int nxt = 0) : v(v), c(c), nxt(nxt) {}
} e[MAXM << 1]; int head[MAXK], tot = 1;

inline 
void add(int u, int v, int c) {
	e[++tot] = edge(v, c, head[u]), head[u] = tot;
	e[++tot] = edge(u, 0, head[v]), head[v] = tot;
}

int lst[MAXK], lvl[MAXK];

inline 
bool bfs(int s, int t) {
	memset(lvl, 0xff, sizeof lvl);
	queue<int> q; q.emplace(s), lvl[s] = 0;
	for (int u; !q.empty(); ) {
		u = q.front(), q.pop(), lst[u] = head[u];
		for (int _ = head[u]; _; _ = e[_].nxt) {
			int v = e[_].v, c = e[_].c;
			if (c && !~lvl[v]) lvl[v] = lvl[u] + 1, q.emplace(v);
		}
	}
	return ~lvl[t];
}

int dfs(int u, int t, int f = inf) {
	if (u == t) return f; int res = 0;
	for (int &_ = lst[u]; _; _ = e[_].nxt) {
		int v = e[_].v, c = e[_].c;
		if (!c || lvl[v] != lvl[u] + 1) continue;
		int x = dfs(v, t, min(f, c));
		e[_].c -= x, e[_ ^ 1].c += x, f -= x, res += x;
	}
	return res;
}

inline 
int dinic(int s, int t) {
	int res = 0;
	for (; bfs(s, t); res += dfs(s, t));
	return res;
}

int n, m, B, S, T, a[7][MAXN], b[7][MAXN];

vector<int> fs[729], ft[729];

int main() {
	scanf("%d%d", &n, &m), B = 1;
	for (int i = 1; i < m; i++) B *= 3;
	S = B << 1, T = S | 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) scanf("%d", &a[j][i]);
	}
	memcpy(b, a, sizeof a);
	for (int j = 0; j < m; j++) sort(b[j] + 1, b[j] + n + 1);
	for (int i = 1; i <= n; i++) {
		int k = n >> 1, x = 0;
		for (int j = 0; j < m; j++) {
			x *= 3;
			if (a[j][i] >= b[j][k + 1]) ++x, (a[j][i] <= b[j][k]) && ++x;
		}
		if (x < B) fs[x].emplace_back(i); else ft[x - B].emplace_back(i);
	}
	for (int i = 0; i < B; i++) {
		if (!fs[i].empty()) add(S, i, fs[i].size());
		if (!ft[i].empty()) add(B + i, T, ft[i].size());
		int p = 0;
		for (int j = 1, x = i; x; x /= 3, j *= 3) {
			if (x % 3 == 2) { p = j; break; }
		}
		if (p) {
			add(i, i - p, inf), add(B + i - p, B + i, inf);
			add(i, i - p - p, inf), add(B + i - p - p, B + i, inf);
		}
	}
	for (int i = 0; i < 1 << m - 1; i++) {
		int x = 0, y = 0;
		for (int j = m - 1; ~j; j--) x *= 3, y *= 3, (i >> j & 1) ? ++x : ++y;
		add(x, y, inf);
	}
	if (dinic(S, T) != n >> 1) return puts("NO"), 0; puts("YES");
	for (int i = B - 1; ~i; i--) {
		int p = 0;
		for (int j = 1, x = i; x; x /= 3, j *= 3) {
			if (x % 3 == 2) { p = j; break; }
		}
		if (!p) continue;
		for (int _ = head[i]; _; _ = e[_].nxt) {
			int v = e[_].v, c = e[_ ^ 1].c;
			if (v != i - p && v != i - p - p) continue;
			for (; c--; fs[v].emplace_back(fs[i].back()), fs[i].pop_back());
		}
		for (int _ = head[B + i]; _; _ = e[_].nxt) {
			int v = e[_].v - B, c = e[_].c;
			if (v != i - p && v != i - p - p) continue;
			for (; c--; ft[v].emplace_back(ft[i].back()), ft[i].pop_back());
		}
	}
	for (int i = 0; i < 1 << m - 1; i++) {
		int x = 0, y = 0;
		for (int j = m - 2; ~j; j--) x *= 3, y *= 3, (i >> j & 1) ? ++x : ++y;
		for (; !fs[x].empty() || !ft[y].empty(); ) {
			printf("%d %d\n", fs[x].back(), ft[y].back());
			fs[x].pop_back(), ft[y].pop_back();
		}
	}
}