RT，求证明或给出 hack 数据

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=3e5+9;
ll n,m,a[MAXN],b[MAXN],ans,now,rec[MAXN],ans2;
vector<ll> to[MAXN],to2[MAXN];
bool flag=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i],to[a[i]].push_back(i),to2[b[i]].push_back(i);
	for(int i=1;i<=m;i++)
		if(to[i].size()!=0) ans=to[i][0],now=i;
	for(int i=1;i<=m;i++){
		for(int j=0;j<to[i].size();j++){
			ll id1=to[i][j],id2=ans;
			if(a[id1]==a[id2]||a[id2]==b[id1]||a[id1]==b[id2]||b[id1]==b[id2]);
			else rec[id1]=id2,rec[id2]=id1;
			if(ans2==0) continue;
			id1=to[i][j],id2=ans2;
			if(a[id1]==a[id2]||a[id2]==b[id1]||a[id1]==b[id2]||b[id1]==b[id2]);
			else rec[id1]=id2,rec[id2]=id1;
		}
		for(int j=0;j<to[i].size();j++){
			ll id=to[i][j];
			if(b[id]==i){
				ans2=id;	
				continue;
			}
			to[b[id]].push_back(id);
			if(b[id]>now) now=b[id],ans=id;
		}
	}
	ans2=0;
	for(int i=m;i>=1;i--)
		if(to2[i].size()!=0) ans=to2[i][0],now=i;
	for(int i=m;i>=1;i--){
		for(int j=0;j<to2[i].size();j++){
			ll id1=to2[i][j],id2=ans;
			if(a[id1]==a[id2]||a[id2]==b[id1]||a[id1]==b[id2]||b[id1]==b[id2]);
			else rec[id1]=id2,rec[id2]=id1;
			if(ans2==0) continue;
			id1=to2[i][j],id2=ans2;
			if(a[id1]==a[id2]||a[id2]==b[id1]||a[id1]==b[id2]||b[id1]==b[id2]);
			else rec[id1]=id2,rec[id2]=id1;
		}
		for(int j=0;j<to2[i].size();j++){
			ll id=to2[i][j];
			if(a[id]==i){
				ans2=id;
				continue;
			}
			to2[a[id]].push_back(id);
			if(a[id]<now) now=a[id],ans=id;
		}
	}
	for(int i=1;i<=n;i++) cout<<rec[i]<<" ";
	return 0;
}