/*

NAME: Andrei Daian

GRADE: 12

SCHOOL: Tiberiu Popoviciu Computer Science High School, Cluj-Napoca

DIVISION: Senior 5

*/

#include<iostream.h>

#include<stdio.h>

#include<limits.h>

#include<conio.h>

int a[100][100], nl, nc;

int x1, y1, x2, y2;

int t[100][100];

int min;

const int dx[]={101, -1, -1, -1, 0, 1, 1, 1, 0};

const int dy[]={101, -1, 0, 1, 1, 1, 0, -1, -1};

void back(int i, int j, int lung);

int valid(int i, int j);

void main(){

int tz;

clrscr();

cout << "0. ";

scanf("%d, %d", &x1, &y1);

while(!(x1==0 && y1==0)){

if (x1>nl)

nl=x1;

if (y1>nc)

nc=y1;

a[x1][y1]=1;

scanf(", %d, %d", &x1, &y1);

}

for (tz=1; tz<=5; tz++){

min=INT_MAX;

cout << tz << ". ";

scanf("%d, %d, %d, %d", &x1, &y1, &x2, &y2);

t[x1][y1]=1;

back(x1, y1, 0);

cout << tz << ". ";

if (min!=INT_MAX)

cout << min << endl;

else

cout << "NONE\n";

t[x1][y1]=0;

}

getch();

}

void back(int i, int j, int lung){

for (int k=1; k<=8; k++){

int ii=i+dx[k];

int jj=j+dy[k];

if (valid(ii, jj)){

t[ii][jj]=1;

if (ii==x2 && jj==y2){

if (lung+1<=min)

min=lung+1;

}else

back(ii, jj, lung+1);

t[ii][jj]=0;

}

}

}

int valid(int i, int j){

if (i<0 || i>nl || j<0 || j>nc)

return 0;

if (a[i][j]==0)

return 0;

if (t[i][j]==1)

return 0;

return 1;

}