1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <ios>
#include <functional>
#include <cassert>
#include <vector>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define SREP(n) REP(_ ## n, n)
#define FOR(i, p, n) for(int i=(p); i<=(n); ++i)
#define RFOR(i, p, n) for(int i=(p); i>=(n); --i)
#define pb push_back
#define eb emplace_back
#define C const
#define V std::vector
#define F std::function
#define R std::ranges
#define RV std::ranges::views
#define sz(A) int(A.size())
#define all(A) A.begin(), A.end()
#define rall(A) A.rbegin(), A.rend()
typedef long long ll;
typedef long double ld;
typedef V <int> vi;
typedef V <vi> vvi;
typedef V <bool> vb;
typedef V <char> vc;
typedef V <ll> vll;
typedef const int ci;
typedef const ll cll;
int I(){
    int z;
    while ((z=getchar_unlocked())<'0'||z>'9');
    int r=z-'0';
    while ((z=getchar_unlocked())>='0'&&z<='9')
        r=r*10+z-'0';
    return r;
}
int main(){
    ci n=I(),m=I();
    struct idk{
        int a,b;
    };
    V <idk> rv(m);
    REP(i, m)
        rv[i]={I()-1, I()-1};
    vi wyn(n+1),wynagr(n+1); // wynagr to ze ile prz dow. o dl i
    vi v(n, 2);
    F <void(int)> rek=[&](int akt){
        // i to ind. następnego ruchu
        C vi bkp=v;
        while (akt<m){
            C auto [a, b]=rv[akt];
            ++akt;
            if (v[a]&v[b]&2){
                v[a]=v[b]=0;
                rek(akt);
                v[a]=v[b]=1;
                rek(akt);
                goto fin;
            }
            // v[a] nie zero i v[b] nie 1.
            if (v[a]*(v[b]^1))
                std::swap(v[a], v[b]);
        }
        {
            int p1=n,k1=-1,p0=-1,k0=n;
            REP(i, n){
                if (!v[i]){
                    if (p1<n)
                        k0=std::min(k0, i);
                    else
                        p0=i;
                }
                if (v[i]&1){
                    if (p1<n){
                        if (k0<n)
                            goto fin;
                        k1=i;
                    }
                    else
                        p1=k1=i;
                }
            }
            if (p1<n)
                FOR(i, 1, n){
                    ci minp=std::max(p0+1, k1-(i-1)),maxp=std::min(k0-i, p1);
                    wyn[i]^=std::max(0, maxp-minp+1)&1;
                }
            else{
                int pop0=-1;
                REP(i, n){
                    if (!v[i]){
                        wynagr[i-pop0-1]^=1;
                        pop0=i;
                    }
                }
                ++wynagr[n-pop0-1];
            }
        }
        fin:
        v=bkp;
    };
    rek(0);
    // wynagr handle
    FOR(d, 1, n)
        FOR(i, 1, d)
            wyn[i]^=wynagr[d]&(d-i+1)&1;
    FOR(i, 1, n){
        assert(!wyn[i]||wyn[i]==1);
        printf("%d ", wyn[i]);
    }
    printf("\n");
}