Drawer Item Placement

You are given (N) items and (L) drawers. Each drawer can hold at most one item. For the (i)-th item, it can be placed either in drawer (A_i) or drawer (B_i). Items come in sequentially. For each item, follow these rules in order until one applies, then stop:

1. If drawer (A_i) is empty, place the item in drawer (A_i).
2. Otherwise, if drawer (B_i) is empty, place the item in drawer (B_i).
3. Otherwise, try to shift the item currently in drawer (A_i) to its other drawer. That is, if the item in drawer (A_i) was originally placed in (A_j), then its alternative is (B_j); if it was placed in (B_j), its alternative is (A_j). If the alternative drawer is full, try shifting recursively. If the shifting process succeeds (i.e. you eventually free a drawer), place the new item in drawer (A_i).
4. If step 3 fails, similarly try shifting the item in drawer (B_i) to its alternative drawer recursively. If successful, place the new item in drawer (B_i).
5. If both shifting attempts fail, discard the item.

After processing all items in order, determine for each item whether it has been saved (placed in a drawer) or discarded.

Note: An item that has been moved during a shifting process is still considered saved.

inputFormat

The first line contains two integers \(N\) and \(L\): the number of items and the number of drawers.

The next \(N\) lines each contain two integers \(A_i\) and \(B_i\) (1-based indices) indicating the two drawers between which the \(i\)-th item can be placed.

outputFormat

Output a single line containing \(N\) space-separated integers. The \(i\)-th integer should be 1 if the \(i\)-th item is saved (i.e. placed in some drawer), or 0 if it has been discarded.

sample

3 2
1 2
1 2
1 2

1 1 0