Có ~n~ đồ vật đánh số từ ~1~ đến ~n~ nằm rải rác trên sàn và có ~k~ thùng đánh số từ ~1~ đến ~k~. Bon quyết định dọn dẹp, bỏ đồ vào trong thùng, mỗi đồ vật sẽ được bỏ vào một thùng. Để tiện cho việc tìm kiếm sau này, Bon quyết định bỏ đồ vật thứ ~i~ vào một trong ~2~ thùng ~a_i~ hoặc ~b_i~.

Bon nhặt lần lượt các đồ vật từ ~1~ đến ~n~ và cất đồ vật thứ ~i~ theo quy tắc đầu tiên có thể chọn trong số các quy tắc sau:

• Nếu thùng ~a_i~ rỗng thì cất vào thùng này,

• Nếu thùng ~b_i~ rỗng thì cất vào thùng này,

• Cố gắng chuyển đồ từ thùng ~a_i~ sang thùng khác phù hợp theo quy định và cứ di chuyển tiếp cho đến khi giải phóng được thùng ~a_i~ để lưu trữ, nếu không giải phóng được thì áp dụng quy tắc tiếp theo,

• Cố gắng chuyển đồ từ thùng ~b_i~ sang thùng khác phù hợp theo quy định và cứ di chuyển tiếp cho đến khi giải phóng được thùng ~b_i~ để lưu trữ, nếu không giải phóng được thì áp dụng quy tắc tiếp theo,

• Vứt đồ vật này.

Hãy xác định những đồ vật nào lưu trữ được và đồ vật nào phải vứt bỏ. Với đồ vật lưu trữ được ghi ra số ~1~, với đồ vật phải vứt bỏ ghi ra số ~0~.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \le n, k \le 3 \times 10^5)~,

• Dòng thứ ~i~ trong ~n~ dòng sau chứa ~2~ số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i, b_i \le k; a_i \ne b_i)~.

Output

Xâu lần lượt ghi trạng thái đồ vật được lưu trữ hay vứt bỏ xác định được.

Sample Input 1

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

Sample Output 1

111111111