1 #include<bits/stdc++.h>

  2 using namespace std;

  3 const int Maxn=0x3f3f3f3f;

  4 const int N=1e5+5;

  5 int lc[N],rc[N],fa[N],sze[N],vi[N],pos[N],a[N];

  6 int n,m,x,y,rt,T;

  7

  8 inline int get(){//快读

  9     char ch;bool f=false;int res=0;

 10     while(((ch=getchar())<'0'||ch>'9')&&ch!='-');

 11     if(ch=='-') f=true;

 12     else res=ch-'0';

 13     while((ch=getchar())>='0'&&ch<='9')

 14         res=(res<<3)+(res<<1)+ch-'0';

 15     return f?~res+1:res;

 16 }

 17

 18 inline bool Wrt(const int&x)

 19 {

 20     return rc[fa[x]]==x;

 21 }

 22

 23 inline void down(const int &x){//下传标记

 24     if(x&&pos[x]){

 25         pos[lc[x]]^=1;

 26         pos[rc[x]]^=1;

 27         swap(lc[x],rc[x]);

 28         pos[x]=0;

 29     }

 30 }

 31

 32 inline void push(int x){

 33     sze[x]=sze[lc[x]]+sze[rc[x]]+1;

 34 }

 35

 36 inline int build(int lst,int l,int r){//lst该节点的祖先编号

 37     if(l>r) return 0;

 38     int mid=(l+r)>>1,x=++T;

 39     fa[x]=lst;pos[x]=0;vi[x]=a[mid];

 40     lc[x]=build(x,l,mid-1);

 41     rc[x]=build(x,mid+1,r);

 42     push(x);

 43     return x;

 44 }

 45

 46 inline void rot(int x){//单旋

 47     int y=fa[x],z=fa[y];

 48     down(y);down(x);//下传标记

 49     int b=(lc[y]==x)?rc[x]:lc[x];

 50     fa[x]=z;fa[y]=x;

 51     if(b) fa[b]=y;

 52     if(z) (y==lc[z]?lc[z]:rc[z])=x;

 53     if(x==lc[y]) rc[x]=y,lc[y]=b;

 54     else lc[x]=y,rc[y]=b;

 55     push(y);push(x);//更新

 56 }

 57

 58 inline void splay(int x,int tar){

 59     while(fa[x]!=tar){

 60         if(fa[fa[x]]!=tar)

 61             Wrt(x)==Wrt(fa[x])?rot(fa[x]):rot(x);

 62         rot(x);

 63     }

 64     if(!tar) rt=x;

 65 }

 66

 67 inline int Find(int k){//查找第k个数

 68     int x=rt,y=k;

 69     while(x){

 70         down(x);

 71         if(y<=sze[lc[x]]) x=lc[x];

 72         else{

 73             y-=sze[lc[x]]+1;

 74             if(!y) return x;

 75             x=rc[x];

 76         }

 77     }

 78 }

 79

 80 /*inline void put(int x){//快输

 81     if(x<0){

 82         x=~x+1;

 83         putchar('-');

 84     }

 85     if(x>9) put(x/10);

 86     putchar(x%10+48);

 87 }*/

 88

 89 inline void Print(int x){

 90     down(x);

 91     if(lc[x]) Print(lc[x]);

 92     if(vi[x]!=-Maxn&&vi[x]!=Maxn)

 93     //    put(vi[x]),putchar(' ');//快输

 94     cout<<vi[x]<<" ";

 95     if(rc[x]) Print(rc[x]);

 96 }

 97

 98 int main(){

 99     n=get();m=get();

100     a[1]=-Maxn;a[n+2]=Maxn;

101     for(int i=1;i<=n;i++) a[i+1]=i;

102     rt=build(0,1,n+2);

103     while(m--){

104         int tx=Find(get());

105         int ty=Find(get()+2);

106         splay(tx,0);

107         splay(ty,tx);

108         pos[lc[rc[rt]]]^=1;

109     }

110     return Print(rt),0;

111 }