: dijkstra
"; print " : dijkstra, k5888200
"; print " : gs12065, gs10107, takuma, myungwoo
"; print " : zlzmsrhak56, jerry1259, byeonbi, pl0892029, shinism, nobe0716, gs11008

#include<stdio.h>
int a,b,n,i,j,k,q[1000002][2],w[10][2],sx,sy,h,t,v[1001][1001],D[1001][1001],s;
char p[1001][1001];				// by ainta
void BFS(int x,int y)
{
	if(x>0&&v[x-1][y]==0&&p[x-1][y]!='X'){
		v[x-1][y]=1,q[t][0]=x-1,q[t++][1]=y,D[x-1][y]=D[x][y]+1;}
	if(x<a-1&&v[x+1][y]==0&&p[x+1][y]!='X'){
		v[x+1][y]=1,q[t][0]=x+1,q[t++][1]=y,D[x+1][y]=D[x][y]+1;}
	if(y>0&&v[x][y-1]==0&&p[x][y-1]!='X'){
		v[x][y-1]=1,q[t][0]=x,q[t++][1]=y-1,D[x][y-1]=D[x][y]+1;}
	if(y<b-1&&v[x][y+1]==0&&p[x][y+1]!='X'){
		v[x][y+1]=1,q[t][0]=x,q[t++][1]=y+1,D[x][y+1]=D[x][y]+1;}
}
int main(){
	scanf("%d%d%d",&a,&b,&n);
	for(i=0;i<a;i++){
		scanf("%s",p[i]);
		for(j=0;j<b;j++){
			if(p[i][j]>='1'&&p[i][j]<='9'){
				w[p[i][j]-'0'][0]=i,w[p[i][j]-'0'][1]=j;
			}
			if(p[i][j]=='S'){
				sx=i,sy=j;
			}
		}
	}
	for(i=1;i<=n;i++){
		t=h=0;
		q[t][0]=sx,q[t++][1]=sy;
		D[sx][sy]=0;
		v[sx][sy]=1;
		while(v[w[i][0]][w[i][1]]==0){
			BFS(q[h][0],q[h][1]);
			h++;}
		for(j=0;j<a;j++)for(k=0;k<b;k++)v[j][k]=0;
		s+=D[w[i][0]][w[i][1]];
		sx=w[i][0],sy=w[i][1];
	}
	printf("%d\n",s);
}
	

#include <stdio.h>

int yy[]={-1,0,1,0},xx[]={0,1,0,-1};
int H,W,N,Y[10],X[10],D[1004][1004],ans;
int head,tail;
char map[1004][1004];
						//by myungwoo
struct QUE{
	int y,x;
} que[1000*1000+9];

void iq(int y,int x){ QUE q={y,x}; que[tail++] = q; }

void bfs(int t)
{
	int i,j,y=Y[t],x=X[t];
	QUE q;
	head = tail = 0;
	for (i=1;i<=H;i++) for (j=1;j<=W;j++) D[i][j] = 1e9;
	D[y][x] = 0;
	iq(y,x);
	while (head != tail){
		q = que[head++];
		for (i=0;i<4;i++){
			y = q.y+yy[i], x = q.x+xx[i];
			if (y < 1 || y > H || x < 1 || x > W || map[y][x] == 'X' || D[y][x] < 1e9) continue;
			D[y][x] = D[q.y][q.x]+1;
			iq(y,x);
		}
	}
}

int main()
{
	int i,j;
	scanf("%d%d%d",&H,&W,&N);
	for (i=1;i<=H;i++){
		scanf("%s",map[i]+1);
		for (j=1;j<=W;j++){
			if (map[i][j] == 'S') map[i][j] = '0';
			if ('0' <= map[i][j] && map[i][j] <= '9'){
				Y[map[i][j]-'0'] = i, X[map[i][j]-'0'] = j;
			}
		}
	}
	for (i=0;i<N;i++){
		bfs(i);
		ans += D[Y[i+1]][X[i+1]];
	}
	printf("%d",ans);
}
	

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int n;
int a[40][40];
int s1[40],s2[40],s;
int max;
int T;

void print(){
    int i,j;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++) printf("%d",a[i][j]==-1?0:1);
        printf("\n");
    }
    printf("\n");
}

void R(){
    int i,j;
    for(i=1;i<=n;i++){
        if(rand()&1){
            for(j=1;j<=n;j++){
                s1[i]=-s1[i];
                for(j=1;j<=n;j++) a[i][j]=-a[i][j], s2[j]+=a[i][j]*2, s+=a[i][j]*2;
            }
        }
    }
    for(j=1;j<=n;j++){
        if(rand()&1){
            for(i=1;i<=n;i++){
                s2[j]=-s2[j];
                for(i=1;i<=n;i++) a[i][j]=-a[i][j], s1[i]+=a[i][j]*2, s+=a[i][j]*2;
            }
        }
    }
}
int main(){
    T=clock();
    srand(time(NULL));

    int i,j;

    scanf("%d",&n);
    for(i=1;i<=n;i++) for(j=1;j<=n;j++){
        scanf("%1d",&a[i][j]);
        if(!a[i][j]) a[i][j]=-1;
        s1[i]+=a[i][j];
        s2[j]+=a[i][j];
        s+=a[i][j];
    }
    //for(i=1;i<=n;i++) for(j=1;j<=n;j++) printf("%d ",a[i][j]);
    max=s;

    for(;;){
        for(i=1;i<=n;i++) if(s1[i]<0) break;
        if(i!=n+1){
            s1[i]=-s1[i];
            for(j=1;j<=n;j++) a[i][j]=-a[i][j], s2[j]+=a[i][j]*2, s+=a[i][j]*2;
        }
        else {
            for(j=1;j<=n;j++) if(s2[j]<0) break;
            if(j!=n+1){
                s2[j]=-s2[j];
                for(i=1;i<=n;i++) a[i][j]=-a[i][j], s1[i]+=a[i][j]*2, s+=a[i][j]*2;
            }
            else {
                R();
            }
        }
        if(s>max) max=s;
        if(clock()-T>10000) break;
    }
    printf("%d",max+(n*n-max)/2);
}
	

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

#define MAXN 32
// SA setting
#define _K 0.000015
#define _TBOUND 0.0000001
#define _TIMELIMIT 390000
#define _TUP 0.995
					//by dijkstra
unsigned int map[MAXN+1][MAXN+1];
int getX(int n)
{
	int i, j, rev=0;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(!map[i][j]) rev++;
	return rev;
}
int Perturb(int t, int n)
{
	int i;
	if(t<n)
		for(i=0;i<n;i++)
			if(map[t][i]) map[t][i] = 0;
			else map[t][i] = 1;
	else
		for(i=0;i<n;i++)
			if(map[i][t-n]) map[i][t-n] = 0;
			else map[i][t-n] = 1;
	return getX(n);
}
main(void)
{
	double T=1.0;
	char temp[33];
	int n, i, j, X_init, X_update, t, min = 100000;
	unsigned long a = clock();
	srand(time(NULL));
	scanf("%d", &n);
	for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%1d",&map[i][j]);
	X_init = getX(n);
	while(T > _TBOUND)
	{
		for(i=0; i<500;i++)	
		{
			if(clock() - a > _TIMELIMIT) break;
			t = rand() % (n*2);
			X_update = Perturb(t, n);
			if( exp(X_init-X_update)/(_K*T) > ((double)rand() / 31975) ) X_init = X_update;
			else Perturb(t, n);
			if(min > X_init) min = X_init;
		}
		T *= _TUP;
	}
	printf("%d\n", n*n-min);
}

	

#include <stdio.h>
#include <algorithm>
#include <vector>
				// by gs12065
struct word{
	int a[5];
	bool operator <(const word x) const{
		int i;
		for(i=0; i<5; i++)
			if(a[i] != x.a[i]) return a[i] < x.a[i];
	}
};

word tmp, list[500020];
bool chk[500020], rEnd;

int n, pre[105], suf[105], first[105], cnt[105];
int start, end, out;

int res[500020], rFull=0;

std::vector < int > vec[105];

void print(int index){
	int i;
	for(i=0; i<5; i++){
		if(list[index].a[i] < 10) printf("0");
		printf("%d", list[index].a[i]);
	}
	printf("\n");
}

void findPath(int target){
	if(rEnd) return;
	int i;
	if(rFull == n){
		for(i=0; i<n; i++)
			print(res[i]);
		rEnd = 1;
		return;
	}
	for(i=0; i<vec[target].size() && !rEnd; i++){
		if(!chk[vec[target][i]]){
			chk[vec[target][i]] = 1;
			res[rFull++] = vec[target][i];
			findPath(list[vec[target][i]].a[4]);
			rFull--;
			chk[vec[target][i]] = 0;
		}
	}
}

int main(){
	scanf("%d", &n);

	int i;
	for(i=0; i<n; i++){
		scanf("%2d%2d%2d%2d%2d", &tmp.a[0], &tmp.a[1], &tmp.a[2], &tmp.a[3], &tmp.a[4]);
		list[i] = tmp;
		pre[tmp.a[0]]++;
		suf[tmp.a[4]]++;
	}

	std::sort(list, list+n);
	
	start=end=-1;
	for(i=0; i<100; i++){
		first[i] = -1;
		if(pre[i] == suf[i]+1){
			if(start == -1) start = i;
			else {
				printf("impossible\n");
				return 0;
			}
		} else if(suf[i] == pre[i]+1){
			if(end == -1) end = i;
			else {
				printf("impossible\n");
				return 0;
			}
		} else if(suf[i] != pre[i]){
			printf("impossible\n");
			return 0;
		}
	}

	int last=list[0].a[0];
	first[list[0].a[0]] = 0;
	for(i=1; i<n; i++){
		if(list[i].a[0] != last){
			last = list[i].a[0];
			first[list[i].a[0]] = i;
		}
	}

	last = start;
	while(rFull < n){
		if(list[first[last]+cnt[last]].a[0] != last)
			break;
		res[rFull++] = first[last]+cnt[last];
		cnt[last]++;
		last = list[first[last]+cnt[last]-1].a[4];
	}

	if(rFull == n)
		for(i=0; i<rFull; i++)
			print(res[i]);
	else {
		rFull = 0;
		for(i=0; i<n; i++)
			vec[list[i].a[0]].push_back(i);
		findPath(start);
	}

	return 0;
}
	

#include<stdio.h>
#include<stdlib.h>			// by dijkstra
#include<vector>
struct WORD{int a,b,c;} w[500010]={0}, sol[500010]={0};
int compare(const void*a, const void*b)
{
	WORD *pa=(WORD *)a;
	WORD *pb=(WORD *)b;
	if(pa->a==pb->a && pa->b == pb->b)
		return pa->c - pb->c;
	else if(pa->a==pb->a)
		return pa->b - pb->b;
	return pa->a-pb->a;
}
std::vector<WORD> G[110];
int pre[110]={0}, post[110]={0},st,n;
int chk[110][500010]={0}, flag;
void dfs(WORD v,int id, int ed)
{
	int i;
	if(flag) return;
	if(id==ed-1)
	{
		for(i=0;i<ed-1;i++)
			printf("%02d%06d%02d\n",sol[i].a,sol[i].b,sol[i].c);
		printf("%02d%06d%02d\n",v.a,v.b,v.c);
		flag=1;
		return;
	}
	sol[id]=v;
	for(i=0;i<G[v.c].size();i++)
		if(!chk[v.c][i]){ 
			chk[v.c][i]=1;
			dfs(G[v.c][i],id+1,n);
			chk[v.c][i]=0;
		}
}
main()
{
	int i, c, l=0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%02d%06d%02d",&w[i].a,&w[i].b,&w[i].c);
		pre[w[i].a]++,post[w[i].c]++;
	}
	qsort(w,n,sizeof(WORD),compare);
	for(i=0;i<100;i++) if(pre[i]-post[i]>0) break;st=i;
	for(i=c=0;i<100;i++) while(w[c].a==i) G[i].push_back(w[c++]);
	for(i=0;i<G[st].size();i++)
		chk[st][i]=1,dfs(G[st][i],0,n),chk[st][i]=0;
	return 0;
}