#include<iostream>
#include<string>
#include<queue>
#include<unordered_map>
using namespace std;
char map[3][4];
int dirext[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
typedef pair<int,int>PII;
string s;
int start;
int endx;
int bfs(string s){
    queue<string>q;
    unordered_map<string,int>d;
    d[s]=0;
    q.push(s);
    while(q.size()){
        auto t=q.front();
        q.pop();
        if(t.find('B')==start&&t.find('A')==endx){
            return d[t];
        }
        int pos=t.find(' ');
        int tx=pos/3;
        int ty=pos%3;
        int ss=d[t];
        for(int i=0;i<4;i++){
            int xx=tx+dirext[i][0];
            int yy =ty+dirext[i][1];
            if(xx>=0&&xx<2&&yy>=0&&yy<3){
                swap(t[xx*3+yy],t[pos]);
                if(d.count(t)==0){
                    d[t]=ss+1;
                    q.push(t);
                }
                swap(t[xx*3+yy],t[pos]);
            }
        }

    }
}
int main(){
    for(int i=1;i<=2;i++){
        string t;
        getline(cin,t);
        s+=t;
    }
    start=s.find('A');
    endx=s.find('B');
    int t=bfs(s);
    cout<<t<<endl;
    return 0;
}

#include<iostream>
#include<unordered_map>
using namespace std;
int map[10];
bool st[10];
int ans[10];
int cnt;
bool check(){
    if(ans[1]+ans[5]+ans[9]==ans[3]+ans[5]+ans[7]
    &&ans[1]+ans[2]+ans[3]==ans[4]+ans[5]+ans[6]
    &&ans[1]+ans[2]+ans[3]==ans[7]+ans[8]+ans[9]
    &&ans[1]+ans[4]+ans[7]==ans[2]+ans[5]+ans[8]&&
    ans[1]+ans[4]+ans[7]==ans[3]+ans[6]+ans[9]){
        return true;
    }else{
        return false;
    }
}
void dfs(int u){
    if(u>9&&check()){
        cnt++;
        for(int i=1;i<=9;i++){
            map[i]=ans[i];
        }
        return;
    }
    if(ans[u]!=0){
        dfs(u+1);
        return;
    }
    for(int j=1;j<=9;j++){
        if(ans[u]==0&&st[j]==false){
            st[j]=true;
            ans[u]=j;
            dfs(u+1);
             st[j]=false;
            ans[u]=0;
        }
    }
}
int main(){

 for(int i=1;i<=9;i++){
     cin>>ans[i];
     if(ans[i]!=0){
         st[ans[i]]=true;
     }
 } 
    dfs(1);
    if(cnt==1){
        for(int i=1;i<=9;i++){
         cout<<map[i]<<" ";
            if(i%3==0){
                cout<<endl;
            }

        }
        }else{
            puts("Too Many");
        }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int tmap[N][N];
int n,m;
bool st[N];
int match[N];
bool find(int x){
    for(int i=1;i<=n;i++){
        if(tmap[x][i]==1&&st[i]==false){
            st[i]=true;
            if(match[i]==0||find(match[i])){
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        while(x--){
            int a;
            cin>>a;
            tmap[i][a]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(st,false,sizeof st);
        if(find(i)){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=410,INF = 0x3f3f3f3f;;
int n,m;
int rw[N][N];//铁路
int gw[N][N];//公路
bool st[N];//状态数组
int d[N];//距离数组
int bfs(int map[][N]){
   memset(d,-1,sizeof d);
   memset(st,false,sizeof st);
   queue<int>v;
   d[1]=0;
   st[1]=true;
   v.push(1);
   while(v.size()){
       int t=v.front();
       v.pop();
       for(int i=1;i<=n;i++){//遍历所有的以t为起点i为终点的点
           if(map[t][i]==1&&st[i]==false){//如果t到i有路且i点没有走过
               st[i]=true;
               d[i]=d[t]+1;//走它
               v.push(i);//将这个点放入队列
           }
       }
   }
   return d[n];
}
int main(){
    cin>>n>>m;
    memset(rw,0x3f3f3f3f,sizeof rw);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                rw[i][j]=0;
                gw[i][j]=0;
            }else{
                gw[i][j]=1;
            }
        }
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        rw[a][b]=rw[b][a]=1;
        gw[a][b]=gw[b][a]=0x3f3f3f3f;
    }
//  for(int s=1;s<=n;s++){
//         for(int g=1;g<=n;g++){
//             cout<<gw[s][g]<<" ";
//         }
//         cout<<endl;
//     }
    int t1=bfs(rw);
    int t2=bfs(gw);
    int ans=0;
    if(t1==-1||t2==-1){//有一个不能到达就返回-1
        cout<<-1<<endl;
    }else{
        ans=max(t1,t2);
        cout<<ans<<endl;
    }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
char s[10010];
int main(){
    int sum=0;
    cin>>s;
    int len=strlen(s);
    for(int i=0;i<len;i++){
        sum+=s[i]-'0';//将字符串转换为int
    }
    int y=0;
    int k=0;
    while(1){
        k=0;//sum更新后 k也要重新计算
        while(sum){
        y=sum%10;
        sum/=10;
        k+=y;//计算余数和
        }
        if(k>=10){//如果余数和是两位数，余数和=sum；
          sum=k;  
        }else{//如果是一位数，退出循环
            break;
        }
    }

    cout<<k<<endl;
 return 0;   
}

#include<iostream>
#include<math.h>
using namespace std;
int n;
    int ans1=0;
    int ans2=0;
int main(){
    scanf("%d",&n);
    int score=0;

    for(int i=0;i<n;i++){
        scanf("%d",&score);
        if(score>=85){
            ans1++;
        }
        if(score>=60){
            ans2++;
        }
    }

//   printf("%d%\n",(int)(ans2*100.0/n+0.5));//进行四舍五入操作
//   printf("%d%\n",(int)(ans1*100.0/n+0.5));
     cout<<round(ans2*100.0/n)<<"%"<<endl;//利用四舍五入库函数
     cout<<round(ans1*100.0/n)<<"%"<<endl;
     return 0;
}

#include<iostream>
using namespace std;
int n;
int mm[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_huiwen(int date){

    int a=date/10000000;
    int b=date/1000000%10;
    int c=date/100000%10;
    int d=date/10000%10;
    int e=date/1000%10;
    int f=date/100%10;
    int g=date/10%10;
    int h=date/1%10;
    if(a==h&&b==g&&c==f&&d==e){
        return true;
    }else{
        return false;
    }
}
bool check_abhuiwen(int date){

    int a=date/10000000;
    int b=date/1000000%10;
    int c=date/100000%10;
    int d=date/10000%10;
    int e=date/1000%10;
    int f=date/100%10;
    int g=date/10%10;
    int h=date/1%10;
    if(a!=b&&a==c&&c==f&&f==h&&b==d&&d==e&&e==g){
        return true;
    }else{
        return false;
    }
}
bool check_value(int date){
    int year=date/10000;
    int month=date/100%100;
    int day=date%100;
    if(day<=0){
        return false;
    }
    if(month<=0||month>12){
        return false;
    }
    if(month!=2&&day>mm[month]){
        return false;
    }
    if(month==2){
        if(year%400==0||(year%4==0&&year%100!=0)){
            if(day>29){
                return false;
            }
        }else{
            if(day>28){
                return false;
            }
        }
    }
    return true;
}
int main(){
    scanf("%d",&n);
    int falg1=0;
      int falg2=0;
    for(int i=n+1;i<=99999999;i++){
        if(falg1==0&&check_value(i)&&check_huiwen(i)){
            falg1=1;
            printf("%d\n",i);
        }
        if(falg2==0&&check_value(i)&&check_abhuiwen(i)){
            falg2=1;
            printf("%d\n",i);

        }
    }
    return 0;
}

#include<iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    n=n/1000;//换算为秒
    int hh=(n/3600)%24;
    int mm=n/60%60;
    int ss=n%60;
   printf("%02d:%02d:%02d",hh,mm,ss);
    return 0;
}

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int w, h;
char map[25][25];
typedef pair<int, int> PII;
int direct[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool st[25][25];
bool in(int x, int y) {
    return x >= 0 && x < w&& y >= 0 && y < h;
}
int bfs(PII start) {
     memset(st,0,sizeof(st));//每一次都需要重置状态数组
    queue<PII>q;
    int step = 1;
    q.push(start);
    st[start.first][start.second] = true;
    while (q.size()) {
        PII t = q.front();
        q.pop();
        for (int j = 0; j < 4; j++) {//四个方向各试一遍
            int x = t.first + direct[j][0];
            int y = t.second + direct[j][1];
            if (in(x, y) && map[x][y] != '#' && st[x][y] == false) {
                st[x][y] = true;//更新状态数组，这个点已走过
                step++;
                q.push({ x,y });
            }
        }
    }
    return step;
}
int main() {
   //scanf("%d%d",&h,&w);//w
   PII start = { 0,0 };
   while(cin>>h>>w,h||w){
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            //scanf("%c", &map[i][j]);
             cin >> map[i][j];
            if (map[i][j] == '@') {
                start.first = i;
                start.second = j;
               // cout<<i<<j<<endl;
            }
        }
    } 
        cout << bfs(start)<<endl;

    }

    return 0;
}

#include<iostream>
#include<queue>
#include<cstring>
//#define x first ;
//#define y second ;
using namespace std;
int n;
int w, h;
typedef pair<int, int> PII;

char map[210][210];
int dist[210][210];
int direct[4][2] = { {1,0 },{0,1},{-1,0},{0,-1} };
bool in(int xx, int yy) {
    return xx >= 0 && xx < w&& yy >= 0 && yy < h;
}
int bfs(PII start, PII end) {
    queue<PII>q;
     memset(dist, -1, sizeof(dist));
    dist[start.first][start.second] = 0;
    q.push(start);
    while (q.size()) {
        PII t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x1 = t.first + direct[i][0];
            int y1 = t.second + direct[i][1];
            if (in(x1, y1) && map[x1][y1] != '#' && dist[x1][y1] == -1) {
                dist[x1][y1] = dist[t.first][t.second] + 1;
                if (end.first==x1&&end.second==y1) {
                    return dist[x1][y1];
                }
                q.push({ x1, y1 });
            }

        }
    }
    return -1;

}
int main() {
    scanf("%d", &n);
            PII start = { 0,0 };
        PII end = { 0,0 };
    while (n--) {
        scanf("%d%d",&w,&h);
        for (int i = 0; i < w; i++) {
            for(int j=0;j<h;j++){
           cin>>map[i][j];
                 if (map[i][j] == 'S') {
                     start = { i,j };
                }
                if (map[i][j] == 'E') {
                    end = { i,j };
                }
            }
        }
        int dis = bfs(start, end);
        if (dis == -1) {
            puts("oop!");
        }
        else {
            printf("%d\n", dist[end.first][end.second]);
        }
    }
    return 0;
}