Chip Routing

A square chip is placed on a coordinate plane. Its lower-left corner is at the origin, and its upper-right corner is at a point with integer coordinates.

Several points on the chip are marked. For each marked point, draw exactly one horizontal or vertical line segment from that point to one side of the chip. A segment must not contain any other marked point, and no two drawn segments may intersect.

Find such segments so that the sum of their lengths is as small as possible.

The first line contains an integer A (2 <= A <= 30), the side length of the square chip.

The second line contains an integer N (1 <= N <= 100), the number of marked points.

Each of the next N lines contains two integers X and Y (1 <= X, Y <= A - 1), the coordinates of one marked point. No two marked points have the same pair of coordinates.

If a solution exists, print the minimum possible sum of segment lengths on the first line.

Then print N lines. The i-th of these lines must contain one of GORE (up), DOLJE (down), LIJEVO (left), or DESNO (right), indicating which side the i-th input point is connected to.

If there is more than one optimal solution, print any one of them.

If no solution exists, print only -1.