[AdditionalFile2777.zip](file://AdditionalFile2777.zip?type=additional_file)

#2777. 「BalticOI 2018」交流电

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 BalticOI 2018 Day2「Alternating Current」

给一个环，这个环可以被分为等长的 $N$ 段，分别标号为 $1\ldots N$。同时你可以通过 $M$ 个控制点将环的某一段染成红色或蓝色，这 $M$ 个控制点分别编号为 $1\ldots M$。

如何安排这 $M$ 个点控制的线段的颜色，使得轨道上每个点都被至少一条红色线段和至少一条蓝色线段覆盖。

保证这个环中不存在不能被染色的部分。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示轨道段数和控制点个数。

接下来 $M$ 行，每行两个整数 $a$ 和 $b$，分别表示每一个控制点可以控制颜色的左右端点。特别地，若 $a=b$ 则这个控制点只控制 $a$ 这一条长度为 $1$ 的线段；若 $b < a$ 则说明这个控制点能控制编号在区间 $[a,\, N]\cup[1,\,b]$ 内的所有线段。

输出格式

输出一行 $M$ 个字符，每个字符是 0 或 1，分别表示设置在第 $i$ 个控制点控制的线段上，染成红色还是蓝色。

如果有多组解请输出任意一组，如果无解请输出 impossible。

样例 1

输入

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

输出

00101

上图为样例 1 的一组解。注意可以将所有的箭头反向得到另一组合法解 11010。

样例 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

数据范围与提示

请注意在 LibreOJ 上共有 $6$ 个子任务，其中第一个子任务为样例。