칩 배선

정사각형 칩이 좌표평면 위에 놓여 있다. 왼쪽 아래 꼭짓점은 원점과 일치하고, 오른쪽 위 꼭짓점은 정수 좌표를 가진 점과 일치한다.

칩 위에는 몇 개의 점이 표시되어 있다. 각 표시된 점마다 그 점에서 칩의 한 변까지 수평 또는 수직 선분을 정확히 하나 그어야 한다. 어떤 선분도 다른 표시된 점을 포함해서는 안 되며, 그은 선분끼리 서로 교차해서도 안 된다.

조건을 만족하는 선분들을 찾아, 선분 길이의 합이 가능한 한 작아지게 하라.

첫째 줄에 정사각형 칩의 한 변의 길이 A (2 <= A <= 30)가 주어진다.

둘째 줄에 표시된 점의 개수 N (1 <= N <= 100)이 주어진다.

다음 N개의 줄에는 표시된 점 하나의 좌표를 나타내는 두 정수 X, Y (1 <= X, Y <= A - 1)가 주어진다. 같은 좌표를 가진 두 점은 없다.

해가 존재한다면 첫째 줄에 선분 길이 합의 최솟값을 출력한다.

이후 N개의 줄을 출력한다. 이 중 i번째 줄에는 입력에서 i번째로 주어진 점을 어느 변에 연결하는지를 나타내는 GORE(위), DOLJE(아래), LIJEVO(왼쪽), DESNO(오른쪽) 중 하나를 출력한다.

최적해가 여러 개라면 그중 아무 것이나 출력해도 된다.

해가 존재하지 않으면 -1만 출력한다.