#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
typedef long long ll;
const int MAXN = 1e5 + 5;
struct d{
int a;
int b;
int nr;
int org;
};
int ans[MAXN];
vector<d> dzieci[MAXN];
int P[MAXN];
vector<d> przedzialy;
bool comp(const d &d1, const d &d2){
if(d1.a != d2.a) return d1.a < d2.a;
return false;
}
vector<d> wejscie;
int n, m;
int pref[MAXN][2];
int G[MAXN];
int G2[MAXN];
bool comp2(const d &d1, const d &d2){
int s1;
if(d1.a <= d1.b) s1 = d1.b - d1.a + 1;
else s1 = n - d1.a + 1 + d1.b;
int s2;
if(d2.a <= d2.b) s2 = d2.b - d2.a + 1;
else s2 = n - d2.a + 1 + d2.b;
if(s1 != s2){
return s1 > s2;
}
return false;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cout << n << " " << m << "\n";
int a, b;
for(int i = 1; i <= m; ++i){
ans[i] = -1;
cin >> a >> b;
cout << a << " " << b << "\n";
if(a > b){
G[a]++;
G[1]++;
G[b+1]--;
}
else{
G[a]++;
G[b+1]--;
}
przedzialy.push_back({a, b, i, i});
}
for(int i = 1; i <= n; ++i){
G[i] += G[i-1];
if(G[i] <= 1){
cout << "impossible\n";
return 0;
}
}
sort(przedzialy.begin(), przedzialy.end(), comp2);
int cnt = 1;
for(auto &u : przedzialy){
//cout << u.a << " " << u.b << " LK\n";
u.nr = cnt;
cnt++;
}
set<pii> duze;
for(auto u : przedzialy){
// cout << u.a << " " << u.b << " " << u.nr << " po kolei\n";
int p = -1;
auto it = duze.lower_bound({u.a, 1e9});
if(it != duze.begin()){
//cout << it->first << " " << it->second << " curr\n";
p = (*(--it)).second;
}
else{
if(duze.size() != 0) p = (*(--duze.end())).second;
}
//cout << p << " P\n";\
P[u.nr] = p;
if(p == -1){
duze.insert({u.a, u.nr});
}
else{
if(u.a <= u.b){
if(przedzialy[p-1].a <= przedzialy[p-1].b){
if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr});
else dzieci[p].push_back(u);
}
else{
if(!(przedzialy[p-1].a <= u.a or przedzialy[p-1].b >= u.b)) duze.insert({u.a, u.nr});
else dzieci[p].push_back(u);
}
}
else{
if(przedzialy[p-1].a <= przedzialy[p-1].b){
duze.insert({u.a, u.nr});
}
else{
if(!(przedzialy[p-1].a <= u.a and przedzialy[p-1].b >= u.b) and przedzialy[p-1 ].a != (przedzialy[p-1].b+1)%n){
duze.insert({u.a, u.nr});
}
else{
dzieci[p].push_back(u);
}
}
}
}
}
vector<d> tmp;
for(auto u : duze){
//cout << u.first << " " << u.second << " duze\n";
tmp.push_back(przedzialy[u.second-1]);
}
przedzialy = tmp;
sort(przedzialy.begin(), przedzialy.end(), comp);
// for(auto u : przedzialy){
// cout << u.a << " " << u.b << " U\n";
// }
// return 0;
if(przedzialy.size() % 2 == 0){
for(int i = 0; i < przedzialy.size(); ++i){
int ktory = (i % 2);
if(przedzialy[i].a > przedzialy[i].b){
pref[przedzialy[i].a][ktory]++;
pref[1][ktory]++;
pref[przedzialy[i].b+1][ktory]--;
}
else{
pref[przedzialy[i].a][ktory]++;
pref[przedzialy[i].b+1][ktory]--;
}
ans[przedzialy[i].org] = ktory;
ktory ^= 1;
for(auto u : dzieci[przedzialy[i].nr]){
if(u.a > u.b){
pref[u.a][ktory]++;
pref[1][ktory]++;
pref[u.b+1][ktory]--;
}
else{
pref[u.a][ktory]++;
pref[u.b+1][ktory]--;
}
ans[u.org] = ktory;
}
}
bool c = true;
for(int i = 1; i <= n; ++i){
for(int j = 0; j < 2; ++j){
pref[i][j] += pref[i-1][j];
if(pref[i][j] <= 0) c = false;
}
}
if(c){
for(int i = 1; i <= m; ++i){
cout << ans[i];
}
cout << "\n";
}
else{
cout << "impossible\n";
}
}
else{
if(przedzialy.size() == 1){
auto u = przedzialy[0];
int ktory = 0;
if(u.a > u.b){
pref[u.a][ktory]++;
pref[1][ktory]++;
pref[u.b+1][ktory]--;
}
else{
pref[u.a][ktory]++;
pref[u.b+1][ktory]--;
}
ans[u.org] = ktory;
ktory ^= 1;
for(auto y : dzieci[u.nr]){
if(y.a > y.b){
pref[y.a][ktory]++;
pref[1][ktory]++;
pref[y.b+1][ktory]--;
}
else{
pref[y.a][ktory]++;
pref[y.b+1][ktory]--;
}
ans[y.org] = ktory;
}
bool c = true;
for(int i = 1; i <= n; ++i){
for(int j = 0; j < 2; ++j){
pref[i][j] += pref[i-1][j];
if(pref[i][j] <= 0) c = false;
}
}
if(c){
for(int i = 1; i <= m; ++i){
cout << ans[i];
}
cout << "\n";
}
else{
cout << "impossible\n";
}
return 0;
}
for(int i = 1; i <= n; ++i){
if(G[i] > 2) G2[i]++;
G2[i] += G2[i-1];
}
int sajz = przedzialy.size();
for(int i = 0; i < sajz; ++i){
int nxt = (i == sajz - 1 ? 0 : i+1);
auto u = przedzialy[i];
auto v = przedzialy[nxt];
//cout << u.a << " " << u.b << " U\n";
auto intersect = [=](d A, d B) -> vector<pii>{
if(A.a <= A.b and B.a <= B.b){
//cout << "#\n";
if(A.b >= B.a) return {{B.a, A.b}};
else return {};
}
else if(A.a > A.b and B.a > B.b){
//cout << "$\n";
vector<pii> D;
D = {{max(A.a, B.a), n}, {1, min(A.b, B.b)}};
if(A.b >= B.a){
D.push_back({B.a, A.b});
}
return D;
}
else if(A.a <= A.b and B.a > B.b){
//cout << "^\n";
if(A.b >= B.a and B.b >= A.a){
return {{B.a, A.b}, {A.a, B.b}};
}
else if(A.b >= B.a){
return {{B.a, A.b}};
}
else if(B.b >= A.a){
return {{A.a, B.b}};
}
else{
return {};
}
}
else{
//cout << "&\n";
swap(A, B);
if(A.b >= B.a and B.b >= A.a){
return {{B.a, A.b}, {A.a, B.b}};
}
else if(A.b >= B.a){
return {{B.a, A.b}};
}
else if(B.b >= A.a){
return {{A.a, B.b}};
}
else{
return {};
}
}
};
vector<pii> C = intersect(u, v);
//cout << i << " i\n";
// for(auto u : C){
// cout << u.first << " " << u.second << " pr\n";
// }
bool c = true;
for(auto x : C){
//cout << x.first << " " << x.second << "X\n";
//cout << G2[x.second] - G2[x.first - 1] << " " << x.second - x.first + 1 << " por\n";
if(G2[x.second] - G2[x.first - 1] != x.second - x.first + 1){
c = false;
}
}
if(c){
//cout << i << " i\n";
//cout << "#\n";
ans[przedzialy[i].org] = 0;
ans[przedzialy[nxt].org] = 0;
for(auto u : dzieci[przedzialy[i].nr]){
ans[u.org] = ans[przedzialy[i].org] ^ 1;
}
for(auto u : dzieci[przedzialy[nxt].nr]){
ans[u.org] = ans[przedzialy[nxt].org] ^ 1;
}
if(nxt == 0){
//cout << "$\n";
for(int j = nxt + 1; j < i; ++j){
ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1;
for(auto u : dzieci[przedzialy[j].nr]){
ans[u.org] = ans[przedzialy[j].org] ^ 1;
}
}
for(int j = 1; j <= m; ++j){
cout << ans[j];
}
cout << "\n";
return 0;
}
else{
for(int j = i - 1; j >= 0; --j){
ans[przedzialy[j].org] = ans[przedzialy[j + 1].org] ^ 1;
//cout << przedzialy[j].a << " " << przedzialy[j].b << " ab1\n";
for(auto u : dzieci[przedzialy[j].nr]){
//cout << u.a << " " << u.b << " syn1\n";
ans[u.org] = ans[przedzialy[j].org] ^ 1;
}
}
for(int j = nxt + 1; j < sajz; ++j){
ans[przedzialy[j].org] = ans[przedzialy[j - 1].org] ^ 1;
//cout << przedzialy[j].a << " " << przedzialy[j].b << " ab2\n";
for(auto u : dzieci[przedzialy[j].nr]){
//cout << u.a << " " << u.b << " syn2\n";
ans[u.org] = ans[przedzialy[j].org] ^ 1;
}
}
for(int j = 1; j <= m; ++j){
cout << ans[j];
}
cout << "\n";
return 0;
}
}
}
cout << "impossible\n";
}
return 0;
}
