경찰차

어떤 도시의 중심가는 N개의 동서 방향 도로와 N개의 남북 방향 도로가 격자 모양으로 놓여 있다.

모든 도로에는 번호가 있다. 남북 방향 도로는 왼쪽에서 오른쪽으로 1번부터 N번까지, 동서 방향 도로는 위에서 아래로 1번부터 N번까지 번호가 붙어 있다. 인접한 동서 방향 도로 사이의 거리와 인접한 남북 방향 도로 사이의 거리는 모두 1이다. 동서 방향 도로와 남북 방향 도로가 만나는 교차로의 위치는 (동서 방향 도로 번호, 남북 방향 도로 번호)로 나타낸다.

도시에는 경찰차 두 대가 있다. 처음에 경찰차 1은 (1, 1)에 있고, 경찰차 2는 (N, N)에 있다. 사건이 발생하면 경찰 본부는 두 경찰차 중 한 대에게 사건 위치를 알려 준다. 연락을 받은 경찰차는 최단 경로로 그 위치까지 이동해 사건을 처리한다. 하나의 사건은 한 대의 경찰차만 처리한다. 사건을 처리한 경찰차는 다음 연락을 받을 때까지 그 사건이 발생한 위치에서 기다린다.

경찰 본부는 사건이 발생한 순서대로 두 경찰차 중 하나에 사건을 맡겨야 한다. 처리해야 하는 모든 사건은 교차로에서 발생한다. 경찰 본부는 두 경찰차가 이동한 거리의 합이 최소가 되도록 각 사건을 배정하려고 한다.

위 그림처럼 N=6이고 사건 위치가 순서대로 (3, 5), (5, 5), (2, 3)이라면, 첫 번째와 두 번째 사건을 경찰차 2에 맡기고 세 번째 사건을 경찰차 1에 맡길 수 있다. 이때 두 경찰차가 이동한 거리의 합은 4 + 2 + 3 = 9이며, 이보다 더 작게 만들 수 없다.

처리해야 할 사건들이 순서대로 주어질 때, 두 경찰차가 이동하는 거리의 합을 최소로 만드는 배정 방법을 구하는 프로그램을 작성하시오.

첫째 줄에 동서 방향 도로의 개수 N이 주어진다. (5 ≤ N ≤ 1,000)

둘째 줄에 처리해야 하는 사건의 개수 W가 주어진다. (1 ≤ W ≤ 1,000)

셋째 줄부터 W개의 줄에 사건이 발생한 위치가 순서대로 한 줄에 하나씩 주어진다. 각 위치는 동서 방향 도로 번호와 남북 방향 도로 번호를 나타내는 두 정수로 주어지며, 두 정수 사이에는 공백이 하나 있다. 두 사건이 같은 위치에서 발생할 수도 있다.

경찰차들은 사건을 입력으로 주어진 순서대로 처리해야 한다.

첫째 줄에 두 경찰차가 이동한 거리의 합의 최솟값을 출력한다.

이어서 W개의 줄을 출력한다. 그중 i번째 줄에는 i번째 사건을 맡은 경찰차 번호 1 또는 2를 출력한다.