Alternating Current

Fredrik has a model railway consisting of $N$ segments connected in a circle. The segments are numbered $1, 2, \dots, N$ in clockwise order. Electricity is supplied through $M$ curved wires running along the circle, and every segment is covered by at least one wire.

Fredrik wants to install a switch on every segment. The switches need alternating current. In Fredrik's view, alternating current means current flowing in both directions. Each wire carries current in one direction only, clockwise or counter-clockwise, and Fredrik can choose the direction of every wire. The directions must be chosen so that every segment is covered by at least one wire with clockwise current and at least one wire with counter-clockwise current.

Find such a choice of directions if one exists.

The figure above shows a solution for the first sample. The curved arrows outside the railway are the wires, and each arrow direction is Fredrik's choice of current direction. Reversing every arrow gives another valid solution.

This idea makes sense because the railway is Swedish, and in Sweden every switch (in Swedish växlar) uses alternating current (in Swedish växelström).

The first line contains two integers $N$ and $M$, the number of segments and the number of wires.

Each of the next $M$ lines contains two integers $a$ and $b$ with $1 \le a, b \le N$. The wire covers segments $a, a+1, \dots, b$. If $b$ is smaller than $a$, the interval wraps around the circle and covers segments $a, \dots, N, 1, \dots, b$. If $a = b$, the wire covers only that single segment.

Output a single line with $M$ characters, each $0$ or 1. The $i$th character must be 0 if the current in the $i$th input wire flows clockwise, and 1 if it flows counter-clockwise. If several solutions exist, output any of them.

If no valid solution exists, output impossible.