Fredrik đang ở nhà chơi với mô hình đường sắt tự chế mà cậu rất tự hào. Đường sắt gồm \(N\) đoạn nối thành một vòng tròn, được đánh số \(1,2,\ldots,N\) theo chiều kim đồng hồ. Tàu được cấp điện qua \(M\) dây dẫn uốn cong chạy dọc theo vòng tròn. Mỗi đoạn đường sắt đều có ít nhất một dây dẫn chạy dọc theo nó.

Tuy nhiên, Fredrik bắt đầu thấy chán khi đoàn tàu cứ chạy vòng quanh, nên cậu quyết định lắp một bộ chuyển đường ray vào mỗi đoạn. Cậu có thể dùng chúng để gây ra những vụ trật bánh và các tình huống thú vị khác. Nhưng các bộ chuyển đường ray cũng cần điện, và phải là dòng điện xoay chiều. Điều này có lý vì đây là đường sắt Thụy Điển: ở Thụy Điển, tất cả các bộ chuyển đường ray (“växlar”) đều sử dụng dòng điện xoay chiều (“växelström”).

Fredrik nghĩ rằng muốn có dòng điện xoay chiều thì chỉ cần có dòng điện chạy theo cả hai chiều. Mỗi dây dẫn chỉ cho dòng điện chạy theo một chiều, hoặc cùng chiều kim đồng hồ, hoặc ngược chiều kim đồng hồ; Fredrik được tự chọn chiều đó. Cậu muốn chọn chiều dòng điện trên từng dây sao cho mỗi đoạn đường sắt đều được phủ bởi ít nhất một dây có dòng điện cùng chiều kim đồng hồ và ít nhất một dây có dòng điện ngược chiều kim đồng hồ.

Bạn có thể giúp Fredrik thực hiện việc này không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đoạn đường sắt và số dây dẫn.

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số \(a\) và \(b\), cho biết một dây dẫn phủ các đoạn \(a,a+1,\ldots,b\). Nếu \(b<a\), dãy này đi qua chỗ nối của vòng tròn, tức là dây phủ các đoạn \(a,\ldots,N,1,\ldots,b\). Nếu \(a=b\), dây chỉ phủ đúng một đoạn.

Dữ liệu ra

In ra một dòng gồm \(M\) ký tự, mỗi ký tự là 0 hoặc 1. Ký tự thứ \(i\) bằng 0 nếu dòng điện trên dây thứ \(i\) trong dữ liệu vào chạy cùng chiều kim đồng hồ, hoặc bằng 1 nếu chạy ngược chiều kim đồng hồ. Nếu có nhiều phương án, bạn có thể in ra bất kỳ phương án nào.

Nếu không có phương án hợp lệ, in ra impossible.

Ràng buộc

• \(2 \le N,M \le 100\,000\).
• \(1 \le a,b \le N\) với mỗi dây dẫn.
• Mỗi đoạn đường sắt có ít nhất một dây dẫn phủ lên nó.
• Một dây với \(a=b\) chỉ phủ một đoạn; một dây với \(b<a\) phủ các đoạn \(a,\ldots,N,1,\ldots,b\).

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (13 điểm): \(2 \le N,M \le 15\).

• Nhóm 2 (20 điểm): \(2 \le N,M \le 100\).
• Nhóm 3 (22 điểm): \(2 \le N,M \le 1\,000\).
• Nhóm 4 (19 điểm): \(2 \le N,M \le 100\,000\); không có dây nào có \(b<a\).
• Nhóm 5 (26 điểm): \(2 \le N,M \le 100\,000\); không có ràng buộc bổ sung.

Ví dụ

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

00101

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

impossible

5 2
1 5
3 3

impossible

5 3
3 3
2 1
4 2

101

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.