设 $i$ 的答案为 $j$，则 $x_j<x_i$ 或 $x_j>x_i$，分两种情况，分别从小到大、从大到小排个序。

对于第一种，不符合条件的情况是 $y_j$ 等于 $x_i$ 或 $y_i$，所以只需记录 $3$ 个不同的 $y_j$ 判断就可以了；

对于第二种，不符合条件的情况有可能是 $y_i$ 等于 $x_j$ 或 $y_j$，对于不同的 $j$，$x_j$ 和 $y_j$ 不应重复出现 $2$ 次以上，按这种策略最坏只用记录 $5$ 个。

复杂度 $O(n\log n)$（排序复杂度），感觉很假的样子，但是它过了。其实和这篇题解有一点类似。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
struct node {
	int x, y, id;
}a[N]; 
int ans[N], b[N], s1[N], s2[N];
bool vis[N], viss[N];
bool cmp1(node x, node y) {
	return x.x < y.x;
}
bool cmp2(node x, node y) {
	return x.x > y.x; 
}
int main() {
	int n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i].x >> a[i].y, a[i].id = i;
	sort(a + 1, a + 1 + n, cmp1);
	int ts = 0;
	for (int i = 1, j = 1; i <= n; i++) {
		while (j < i && a[i].x != a[i - 1].x) {
			if (!vis[a[j].y] && ts < 3) 	
				b[++ts] = j, vis[a[j].y] = true;
			j++;
		}
		for (int j = 1; j <= ts; j++)
			if (a[b[j]].y != a[i].y && a[b[j]].y != a[i].x) {
				ans[a[i].id] = a[b[j]].id;
				break;
			} 	
	}
	sort(a + 1, a + 1 + n, cmp2);
	ts = 0; 
	for (int i = 1, j = 1; i <= n; i++) {
		while (j < i && a[i].x != a[i - 1].x) {
			if (s1[a[j].x] <= 1 && s2[a[j].y] <= 1 && ts < 5) 	
				b[++ts] = j, s1[a[j].x]++, s2[a[j].y]++;
			j++;
		}
		for (int j = 1; j <= ts; j++)
			if (a[b[j]].x != a[i].y && a[b[j]].y != a[i].y) {
				ans[a[i].id] = a[b[j]].id;
				break;
			} 	
	} 
	for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
	return 0;
}