Police Cars

The downtown area of a city has N east-west streets and N north-south streets arranged as a grid.

Every street is numbered. The north-south streets are numbered from 1 to N from left to right, and the east-west streets are numbered from 1 to N from top to bottom. The distance between two adjacent east-west streets is 1, and the distance between two adjacent north-south streets is also 1. An intersection is represented as (east-west street number, north-south street number).

There are two police cars in the city. Initially, police car 1 is at (1, 1), and police car 2 is at (N, N). Whenever an incident occurs, police headquarters assigns that incident to one of the two cars. The assigned car moves to the incident location along a shortest path and handles it. Each incident is handled by exactly one car. After handling an incident, the car waits at that incident location until it receives another assignment.

Police headquarters must assign the incidents in the order they occur. All incidents occur at intersections. The goal is to assign each incident so that the sum of the distances traveled by the two cars is as small as possible.

For the situation shown above, let N=6 and let the incident locations be (3, 5), (5, 5), and (2, 3) in that order. If the first and second incidents are assigned to police car 2 and the third incident is assigned to police car 1, the total distance traveled is 4 + 2 + 3 = 9, and it cannot be made smaller.

Given the incidents in order, write a program that finds an assignment minimizing the total distance traveled by the two police cars.

The first line contains an integer N, the number of east-west streets. (5 ≤ N ≤ 1,000)

The second line contains an integer W, the number of incidents to handle. (1 ≤ W ≤ 1,000)

Each of the next W lines contains the location of one incident in order. Each location is given as two integers: the east-west street number and the north-south street number, separated by one space. Two incidents may occur at the same location.

The police cars must handle the incidents in the order given in the input.

On the first line, print the minimum possible sum of the distances traveled by the two police cars.

Then print W more lines. On the i-th of these lines, print 1 or 2, the number of the police car assigned to the i-th incident.