Buổi tổng duyệt lễ hội ánh sáng sắp bắt đầu thì Lunar phát hiện lịch trực ở hai phòng điều khiển vẫn còn trống. Tinar đã tập hợp đủ ~n~ tình nguyện viên, đánh số từ ~1~ đến ~n~, và ghi lại những cặp đã từng trực chung trong các buổi tập trước.

Phòng đỏ và phòng xanh cần số người bằng nhau. Mỗi tình nguyện viên phải trực ở đúng một phòng. Vì buổi tổng duyệt có nhiều tín hiệu phải xử lý cùng lúc, Lunar yêu cầu mỗi cặp tình nguyện viên được xếp cùng phòng phải từng trực chung. Một cặp được xem là đã trực chung khi xuất hiện trong danh sách của Tinar, theo thứ tự bất kỳ. Hai người đã từng trực chung vẫn có thể được xếp vào hai phòng khác nhau.

Hãy giúp Lunar xếp lịch trực cho cả hai phòng hoặc xác định rằng không thể xếp lịch theo các điều kiện trên.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~, lần lượt là số tình nguyện viên và số cặp đã từng trực chung ~(2 \le n \le 10^6,\ 0 \le m \le 10^6)~.
• Mỗi dòng trong ~m~ dòng tiếp theo chứa hai số nguyên ~a~ và ~b~ ~(1 \le a,b \le n,\ a \ne b)~, cho biết tình nguyện viên ~a~ và tình nguyện viên ~b~ đã từng trực chung.

Mỗi cặp tình nguyện viên xuất hiện nhiều nhất một lần, kể cả khi đảo thứ tự hai người.

Output

Nếu có lịch trực hợp lệ, in ra ~n~ dòng. Dòng thứ ~i~ chứa ký tự r nếu tình nguyện viên ~i~ trực ở phòng đỏ, hoặc ký tự b nếu người đó trực ở phòng xanh.

Nếu không thể xếp lịch, in ra một dòng chứa impossible.

Nếu có nhiều lịch trực hợp lệ, bạn có thể in ra bất kỳ lịch nào.

Subtask

Bạn nhận toàn bộ số điểm của một subtask nếu chương trình vượt qua tất cả các test thuộc subtask đó.

Sample Input 1

2 1
1 2

Sample Output 1

r
b

Sample Input 2

4 3
1 2
3 1
3 2

Sample Output 2

impossible

Sample Input 3

3 3
1 2
1 3
2 3

Sample Output 3

impossible

Sample Input 4

4 4
1 2
2 3
3 4
4 1

Sample Output 4

r
b
b
r

Giải thích

• Ví dụ 1. Mỗi phòng có một người, nên trong mỗi phòng không có cặp nào cần kiểm tra.
• Ví dụ 2. Mỗi phòng cần hai người, nhưng tình nguyện viên ~4~ chưa từng trực chung với ai trong danh sách.
• Ví dụ 3. Có ba tình nguyện viên nên không thể xếp cho hai phòng có số người bằng nhau.
• Ví dụ 4. Lunar xếp người ~1~ và ~4~ vào phòng đỏ, còn người ~2~ và ~3~ vào phòng xanh. Cả hai cặp đều đã từng trực chung.