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ỏ.

Dữ liệu:

+ Dòng đầu tiên chứa 2 số nguyên n và k (1 ≤ n, k ≤ 3×10⁵),

+ Dòng thứ i trong n dòng sau chứa 2 số nguyên a_i và b_i (1 ≤ a_i, b_i ≤ k, a_i ≠ b_i).

Kết quả:

+ Một 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. 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.

Ví dụ: