题目背景

今年共有 $n$ 名选手参加年度大型彩弹比赛 BAPC。比赛中，红队与蓝队将争夺全国冠军。

去年的比赛中，由于队员之间互不熟悉，沟通出现了严重问题：一半蓝队队员走到了旁边的场地，红队甚至成功夺走了自己的旗帜。为了避免类似事故，今年的组织者决定，任意一支队伍中的每两名队员都必须彼此认识。

题目描述

给定 $n$ 名选手以及其中若干对相互认识的关系。

你需要把所有选手分成红队和蓝队，并满足：

1. 每名选手必须且只能加入一支队伍；
2. 两支队伍人数相同；
3. 在每支队伍中，任意两名选手都彼此认识。

请判断是否存在满足要求的分组方案，并在存在时输出任意一种方案。

输入格式

第一行输入两个整数 $n,m$，分别表示选手数量和认识关系数量。

接下来 $m$ 行，每行输入两个整数 $a,b$，表示选手 $a$ 与选手 $b$ 彼此认识。

同一对选手的认识关系最多出现一次。

输出格式

如果不存在满足要求的分组方案，输出一行：

impossible

否则，对于每名选手 $i=1,2,\ldots,n$，依次输出一行：

• 若选手 $i$ 加入红队，输出 r；
• 若选手 $i$ 加入蓝队，输出 b。

如果有多个可行方案，输出任意一个即可。

本题采用 Special Judge。

数据范围

对于全部数据：

• $2\le n\le 10^6$；
• $0\le m\le 10^6$；
• $1\le a,b\le n$；
• $a\ne b$。

样例 1

2 1
1 2

r
b

样例 2

4 3
1 2
3 1
3 2

impossible

样例 3

3 3
1 2
1 3
2 3

impossible

样例 4

4 4
1 2
2 3
3 4
4 1

r
b
b
r