/*#define abs(x) (x>-(x)?x:-(x))
#include<stdio.h>
int a[1002][1002]={},n,m;
int r(int x,int y){
if(x==n&&y==m)return 1;
int memo=a[x][y], min=2147483647, t;
a[x][y]=0;
if(a[x+1][y]&&abs(a[x+1][y]-memo)<2){
t=r(x+1,y);
if(t&&t<min)min=t;
}
if(min==n+m-x-y)return min+1;
if(a[x][y+1]&&abs(a[x][y+1]-memo)<2){
t=r(x,y+1);
if(t&&t<min)min=t;
}
if(min==n+m-x-y)return min+1;
if(a[x-1][y]&&abs(a[x-1][y]-memo)<2){
t=r(x-1,y);
if(t&&t<min)min=t;
}
if(min==n+m-x-y)return min+1;
if(a[x][y-1]&&y>1&&abs(a[x][y-1]-memo)<2){
t=r(x,y-1);
if(t&&t<min)min=t;
}
if(min==n+m-x-y)return min+1;
if(min==2147483647){
return 0;
}
if(min==n+m-x-y)return min+1;
a[x][y]=memo;
return min+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
a[i][j]++;
a[i][j]=1;
if(i+j==n)a[i][j]=3;
}
}
printf("%d",r(1,1));
return 0;
}*/
//놀이공원(실패)
/*#include<stdio.h>
int a[501][501]={},n;
int sh[501]={},ta[501]={};
void sho(int x){
if(sh[x])return;
sh[x]=1;
for(int i=1;i<=n;i++){
if(a[x][i]){
sho(i);
for(int j=1;j<=n;j++){
if(a[i][j])a[x][i]=1;
}
}
}
}
void tal(int x){
if(ta[x])return;
ta[x]=1;
for(int i=1;i<=n;i++){
if(a[i][x]){
tal(i);
for(int j=1;j<=n;j++){
if(a[j][i])a[j][x]=1;
}
}
}
}
int main(){
int m,x,y,t=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
a[x][y]=1;
}
for(int i=1;i<=n;i++){
sho(i);
tal(i);
}
for(int i=1;i<=n;i++){
int r=1;
for(int j=1;j<=n;j++){
if(a[i][j]||a[j][i])r++;
}
if(r==n)t++;
}
printf("%d",t);
return 0;
}*/
//키 순서
/*#include<stdio.h>
int a[26][26]={},n,guchim[26]={},s,e;
int minroad(int start,int nl){
printf("function started:%d %d\n",start,nl);
if(start==e){printf("function ended:%d=>%d\n",e,0);return 0;}
guchim[start]=1;
int min=2147483647;
for(int i=0;i<n;i++){
if(a[start][i]&&guchim[i]==0&&(nl+a[start][i]<=a[s][i]||a[s][i]==0)){
a[s][i]=nl+a[start][i];
a[i][s]=a[s][i];
int t=minroad(i,a[s][i]);
if(a[i][e]<t||a[i][e]==0)a[i][e]=t;
a[e][i]=a[i][e];
if(t==-1)continue;
t+=a[i][start];
if(t<min)min=t;
}
}
guchim[start]=0;
printf("function ended:%d=>%d\n",start,min);
if(min==2147483647)return -1;
return min;
}
int main(){
int m,l;
char x,y;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("\n%c %c %d",&x,&y,&l);
a[x-'A'][y-'A']=l;
a[y-'A'][x-'A']=l;
}
scanf("\n%c %c",&x,&y);
s=x-'A';
e=y-'A';
printf("%d",minroad(s,0));
return 0;
}*/
//최단 경로 1(실패)