#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define vi vector<int>
#define vb vector<bool>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
struct wire {
int a, b, idx;
};
struct item {
int d1, d2;
int f2f1, f2f2;
};
const item NEUTRAL = { 0, 0, INT_MAX, INT_MAX };
struct SegTree {
vector<item> arr;
int size;
void update(item & self, item & c1, item & c2) {
if (self.d1 > 0) self.f2f1 = INT_MAX;
else if (c1.f2f1 != INT_MAX) self.f2f1 = c1.f2f1;
else self.f2f1 = c2.f2f1;
if (self.d2 > 0) self.f2f2 = INT_MAX;
else if (c1.f2f2 != INT_MAX) self.f2f2 = c1.f2f2;
else self.f2f2 = c2.f2f2;
}
void update(item & self, int pos) {
self.f2f1 = (self.d1 > 0) ? INT_MAX : pos;
self.f2f2 = (self.d2 > 0) ? INT_MAX : pos;
}
void init(int _n) {
size = 1;
while (size < _n) size *= 2;
arr.assign(2 * size, { 0, 0, INT_MAX, INT_MAX });
for (int i = 0; i < size; ++i) {
arr[size + i] = { 0 , 0, i, i };
}
for (int x = size-1; x > 0; --x) update(arr[x], arr[2 * x], arr[2 * x + 1]);
}
item query(int a, int b) {
if (a < b) {
return query(a, b, 1, 0, size);
} else {
item ans = { 0, 0, INT_MAX, INT_MAX };
item c1 = query(a, size, 1, 0, size);
item c2 = query(0, b, 1, 0, size);
if (c2.f2f1 != INT_MAX) c2.f2f1 += size;
if (c2.f2f2 != INT_MAX) c2.f2f2 += size;
update(ans, c1, c2);
return ans;
}
}
item query(int a, int b, int x, int lx, int rx) {
if (a <= lx && rx <= b) { return arr[x] = arr[x]; }
if (b <= lx || rx <= a) { return NEUTRAL; }
int m = (lx + rx) / 2;
item ans = { arr[x].d1, arr[x].d2, INT_MAX, INT_MAX };
item c1 = query(a, b, 2 * x, lx, m);
item c2 = query(a, b, 2 * x + 1, m, rx);
update(ans, c1, c2);
return ans;
}
void set(int a, int b, int c) {
// current \in { +- 1, +- 2 }
if (a < b) {
set(a, b, c, 1, 0, size);
} else {
set(a, size, c, 1, 0, size);
set(0, b, c, 1, 0, size);
}
}
void set(int a, int b, int c, int x, int lx, int rx) {
if (a <= lx && rx <= b) {
if (abs(c) == 1) { arr[x].d1 += c; }
else { arr[x].d2 += c / 2; }
if (rx - lx > 1) update(arr[x], arr[2 * x], arr[2 * x + 1]);
else update(arr[x], lx);
return;
}
if (b <= lx || rx <= a) { return; }
int m = (lx + rx) / 2;
set(a, b, c, 2 * x, lx, m);
set(a, b, c, 2*x+1, m, rx);
update(arr[x], arr[2 * x], arr[2 * x + 1]);
}
};
bool in(wire a, wire b, int N) { // ist a in b?
int ea = a.b;
if (a.b <= a.a) ea += N;
int eb = b.b;
if (b.b <= b.a) eb += N;
return (b.a <= a.a && ea <= eb) || (b.a <= a.a + N && ea + N <= eb);
}
int alter(int state) {
if (abs(state) == 1) return state * 2;
else return state / 2;
}
void setSeg(SegTree & seg, wire & parent, vector<wire> & children, vi & states, int state) {
states[parent.idx] = state;
seg.set(parent.a, parent.b, state);
state = alter(state);
for (wire c : children) {
states[c.idx] = state;
seg.set(c.a, c.b, state);
}
}
void coutStates(vi & states) {
for (int b : states) printf("%d", b-1);
cout << endl;
}
void alter(SegTree & seg, wire & parent, vector<wire> & children, vi & states) {
int oldState = states[parent.idx];
setSeg(seg, parent, children, states, -oldState);
setSeg(seg, parent, children, states, alter(oldState));
}
void DebugOutput(SegTree & seg, vi & states, int N) {
for (int j = 0; j < N; ++j) {
item tmp = seg.query(j, j + 1);
cout << ((tmp.f2f1 == INT_MAX) ? "-" : to_string(tmp.f2f1));
cout << "/" << ((tmp.f2f2 == INT_MAX) ? "-" : to_string(tmp.f2f2));
cout << " ";
} cout << endl;
coutStates(states);
cout << endl;
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
vector<wire> wires(M);
vi states(M, 0);
for (int i = 0,a,b; i < M; ++i) {
scanf("%d %d", &a, &b);
wires[i] = { --a, b, i };
}
sort(wires.begin(), wires.end(), [&](wire & one, wire & two) {
if (one.a != two.a) return one.a < two.a;
else {
int l1 = one.b - one.a; if (l1 <= 0) l1 += N;
int l2 = two.b - two.a; if (l2 <= 0) l2 += N;
return l1 > l2;
}
});
// nasty fehler bei 1 N, 1 N ?
vector<wire> parents;
vector<vector<wire>> children;
parents.push_back(wires[0]);
children.push_back(vector<wire>());
for (int i = 1; i < M; ++i) {
if (in(wires[i], parents.back(), N)) {
children.back().push_back(wires[i]);
} else {
parents.push_back(wires[i]);
children.push_back(vector<wire>());
}
}
reverse(all(parents));
reverse(all(children));
while (parents.size() > 1) {
if (in(parents.back(), parents.front(), N)) {
children[0].push_back(parents.back());
for (wire w : children.back()) children[0].push_back(w);
parents.pop_back();
children.pop_back();
} else {
break;
}
}
reverse(all(parents));
reverse(all(children));
SegTree seg;
seg.init(N);
for (int i = 0, s; i < sz(parents); ++i) {
s = (i % 2) + 1;
setSeg(seg, parents[i], children[i], states, s);
// DebugOutput(seg, states, N);
}
for (int i = 0; i < sz(parents); ++i) {
item res = seg.query(0, N);
if (res.f2f1 == INT_MAX && res.f2f2 == INT_MAX) {
coutStates(states);
return 0;
}
alter(seg, parents[i], children[i], states);
// DebugOutput(seg, states, N);
}
printf("impossible");
}
