The Kingdom of Belzerg consists of cities lined up on both sides of a long and vast forest running from west to east. The
cities above the forest are numbered
to
from left to right, and the
cities below the forest are numbered in the same manner.
To increase the connectedness of the citizens and strengthen their defense against the Demon King's advancements, the King of Belzerg has ordered for roads to be paved through the forest. Specifically, he gave you a list of
commands, the
-th saying:
Pave a road of the shortest possible length between city
and city
on opposite sides of the forest.
However, he did not mention which of the cities should be on which side of the forest! You took this to mean that both interpretations would be acceptable, and so you will pave the -th road between city
above the forest and city
below the forest or between city
above the forest and city
below the forest.
Of course, you know the ultimate goal is to increase the connectedness of the citizens. We say that two cities are connected if it is possible for a citizen from the first city to reach the second city by walking along the paved roads, possibly passing through some other cities in the process. Here, note that if any two roads intersect at any point, it is possible for the citizen to switch from one road to the other.
As such, you wonder: out of all possible interpretations of the king's commands, what is the smallest possible size of the largest set of cities in which no two cities are connected? Naturally, you should also produce a list of roads to pave where this size is achieved.
Constraints
Each city number appears at most twice in the list.
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [30%]
Each city number appears at most once in the list.
Subtask 4 [30%]
No additional constraints.
Input Specification
The first line contains integers
and
.
The next lines each contain
integers
and
.
Output Specification
Output a single integer on the first line, the smallest possible size of the largest set of cities in which no two cities are connected.
Then, output a space-separated sequence of integers
or
, where the
-th integer is
if the
-th road should be paved between city
above the forest and city
below the forest, or
if the road should be paved between city
above the forest and city
below the forest. These roads must minimize the size of the largest set of cities in which no two cities are connected. If there are multiple solutions, output any of them.
Sample Input
7 6
4 2
3 2
1 1
4 5
6 7
6 7
Sample Output
6
0 1 0 0 1 0
Explanation
A diagram of the paved roads is given below:
For example, city above the forest is connected to city
below the forest by the path highlighted in red. In general, we see that the largest set of cities in which no two cities are connected has a size of
, and that no smaller size can be achieved. So, this is a valid output.
Comments