题目描述

一个环被分为 $N$ 段，有 $M$ 个控制点，每个控制点可以控制环上的一段连续区间（可能跨越首尾）。需要为每个控制点分配颜色（红色或蓝色），使得环上每一段都被至少一条红色线段和至少一条蓝色线段覆盖。

---

输入格式

第一行：$N, M$（段数、控制点数）

接下来 $M$ 行：每行两个整数 $a, b$，表示控制点覆盖的区间

• 若 $a = b$：只覆盖一段
• 若 $b < a$：覆盖 $[a, N] \cup [1, b]$（跨越首尾）

---

输出格式

一行 $M$ 个字符（0 或 1），表示每个控制点的颜色分配

如果无解，输出 impossible

---

样例 1

输入

10 5
1 5
6 7
5 1
7 2
2 4

输出

00101

---

样例 2

输入

10 5
1 4
2 5
4 7
6 10
8 1

输出

impossible

---

样例 3

输入

5 2
1 5
3 3

输出

impossible

---

样例 4

输入

5 3
3 3
2 1
4 2

输出

101

---

数据范围与提示

子任务	分值	数据范围	附加限制
1	13	$2 \leqslant N, M \leqslant 15$	无
2	20	$2 \leqslant N, M \leqslant 100$
3	22	$2 \leqslant N, M \leqslant 1000$
4	19	$2 \leqslant N, M \leqslant 100,000$	$b \geqslant a$
5	26