题目描述

Fredrik 在家里玩自己定制的铁路模型，并对此非常自豪。铁路由 $N$ 个首尾相连成环的轨道段组成，按顺时针方向编号为 $1,2,\ldots,N$。

火车的电力由 $M$ 根沿圆环铺设的弯曲导线提供。每根导线覆盖圆环上的一段连续轨道。保证每个轨道段至少被一根导线覆盖。

后来 Fredrik 觉得火车只是绕圈太无聊了，于是想在每个轨道段上加一个道岔，用来制造脱轨事故等更刺激的场景。不过，道岔也需要电力，而且需要的是“交流电”。

Fredrik 认为，要得到交流电，就要有两个方向的电流。每根导线只能提供一个方向的电流：顺时针或逆时针。但每根导线具体选哪个方向，可以由 Fredrik 决定。

因此，你需要为每根导线选择电流方向，使得每个轨道段同时满足：

• 至少被一根顺时针电流的导线覆盖；
• 至少被一根逆时针电流的导线覆盖。

请帮助 Fredrik 完成这个任务。

输入格式

第一行包含两个整数 $N,M$，分别表示轨道段数和导线数。

接下来 $M$ 行，每行包含两个整数 $a,b$，表示一根导线覆盖轨道段：

若 $b<a$，表示该区间会绕过编号边界，即覆盖：

特别地，若 $a=b$，则该导线只覆盖一个轨道段。

输出格式

若存在合法方案，输出一行长度为 $M$ 的 01 字符串。

第 $i$ 个字符表示第 $i$ 根导线的方向：

• 0：电流方向为顺时针；
• 1：电流方向为逆时针。

如果有多个合法方案，可以输出任意一个。

若不存在合法方案，输出：

impossible

数据范围

• $2\le N,M\le 100000$。

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务分数。

样例

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