/*
#include <stdio.h>
int n, ki,kj,ti,tj,arr[1002][1002]={},q[1000002]={},f=0,r=0;
int d[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};
void push(int n)
{
r++;
q[r]=n;
return ;
}
int pop()
{
f++;
return q[f];
}
void bfs(int a,int b)
{
int k=arr[a][b];
for(int i=0;i<8;i++){
if(a+d[i][0]>0&&a+d[i][0]<=n&&b+d[i][1]>0&&b+d[i][1]<=n){
if(a+d[i][0]==ti&&b+d[i][1]==tj){
if(arr[ti][tj]==0) arr[ti][tj]=k+1;
else if(arr[ti][tj]>k+1) arr[ti][tj]=k+1;
}
else if(arr[a+d[i][0]][b+d[i][1]]==0){
arr[a+d[i][0]][b+d[i][1]]=k+1;
push(10000*(a+d[i][0])+b+d[i][1]);
}
}
}
return ;
}
int main()
{
scanf("%d",&n);
scanf("%d %d",&ki,&kj);
scanf("%d %d",&ti,&tj);
push(10000*ki+kj);
while(f!=r){
int z=pop();
bfs(z/10000,z%10000);
}
printf("%d",arr[ti][tj]);
return 0;
}
연결리스트 (이론적)
알고리즘 : 그리디, 동적계획법, 탐색기반설계, 관계기반설꼐
*/
/*
#include <stdio.h>
int main()
{
int x1,y1,x2,y2,a1,a2,b1,b2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
scanf("%d %d %d %d",&a1,&b1,&a2,&b2);
if((x1==a2&&y1==b2)||(x2==a1&&y2==b1)||(x1==a2&&y2==b1)||(x2==a1&&y1==b2)) printf("POINT");
else if(y1>b2||b1>y2||x1>a2||a1>x2) printf("NULL");
else if(x1==a2||x2==a1||y1==b2||y2==b1) printf("LINE");
else printf("FACE");
return 0;
}
*/
/*
#include <stdio.h>
int a,b,k=-1;
int f(int x,int y)
{
k++;
if(x==y) return k;
else if(x>y) return f(x/2,y);
else return f(x,y/2);
}
int main()
{
scanf("%d %d",&a,&b);
printf("%d",f(a,b));
return 0;
}
*/
/*
#include <stdio.h>
int p,m,c[11]={},k=0,z=0,l=0,o=0,y=0;
void f(int p,int m)
{
if(m<1||p<0) return ;
if(p==0) return ;
if(p>=c[m]){
if(g(p,m)+k<o||o==0) o=g(p,m)+k;
if(u(p,m-1)!=0&&(u(p,m-1)+k<y||y==0)) y=u(p,m-1)+k;
p-=c[m];
k++;
f(p,m);
}
else return f(p,m-1);
return ;
}
int g(int p,int m)
{
for(int i=m;i>0;i--){
if(p%c[i]==0) return p/c[i];
}
return 0;
}
int u(int p,int m)
{
if(m<1||p<0) return 0;
if(p==0) return 0;
if(p>=c[m]){
p-=c[m];
return u(p,m)+1;
}
else return u(p,m-1);
return ;
}
int main()
{
scanf("%d %d",&p,&m);
for(int i=1;i<=m;i++){
scanf("%d",&c[i]);
if(p%c[i]==0) z=i;
}
if(z!=0) l=p/c[z];
f(p,m);
if(l!=0&&l<k) k=l;
if(o!=0&&o<k) k=o;
if(y!=0&&y<k) k=y;
printf("%d",k);
return 0;
}
*/
/*
#include <stdio.h>
int arr[1001][1001]={},n,m,q[1000001]={},f=0,r=0,arr1[1001][1001]={};
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void push(int n)
{
r++;
q[r]=n;
return ;
}
int pop()
{
f++;
return q[f];
}
void bfs(int a,int b)
{
int z;
z=arr1[a][b];
for(int i=0;i<4;i++){
if(arr1[a+d[i][0]][b+d[i][1]]==0&&a+d[i][0]>0&&a+d[i][0]<=n&&b+d[i][1]>0&&b+d[i][1]<=m){
if(arr[a+d[i][0]][b+d[i][1]]-arr[a][b]<2&&arr[a+d[i][0]][b+d[i][1]]-arr[a][b]>-2){
arr1[a+d[i][0]][b+d[i][1]]=z+1;
push(10000*(a+d[i][0])+b+d[i][1]);
}
}
}
return ;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&arr[i][j]);
push(10001);
arr1[1][1]=1;
while(f!=r){
int k=pop();
bfs(k/10000,k%10000);
}
printf("%d",arr1[n][m]);
return 0;
}
*/