#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <list>
#include <queue>
#include <set>

using namespace std;

class ChessMaze
{
  public:

    int traverseMaze( vector<string> maze )
    {
    int n=maze.size();
    int m=maze[0].size();
        cout << n << " " << m << endl;
    int mat[n][m];

    int si=0;
    int sj=0;

    int ei=0;
    int ej=0;

    int c=0;

    bool visited[n][m][1 << 11][15];
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(maze[i][j]=='K'){

            mat[i][j]=c;

            c++;
            }
            if(maze[i][j]=='S'){
             si=i;
             sj=j;
            }
             if(maze[i][j]=='E'){
                ei=i;
                ej=j;
             }
            
        }
    }

    int di[]={0, 0, 1, -1};
    int dj[]={1, -1, 0, 0};

        int ki[] = {-2, -2,  -1, -1, 1, 1, 2, 2};
                int kj[] = {1, -1,    2, -2, -2, 2, -1, 1};
         

    memset(visited, false, sizeof visited);


        maze[ei][ej] = '.';
   queue<int>q;
   q.push(si);
   q.push(sj);
   q.push(0);/// powerups
   q.push(0);
   q.push(0);
        visited[si][sj][0][0] = true;
   while(!q.empty()){
    int ci=q.front();
    q.pop();
    int cj=q.front();
    q.pop();
    int bitmask=q.front();
    q.pop();
    int mozni=q.front();
    q.pop();
    int cekori=q.front();
    q.pop();

    if(ci == ei and cj == ej){
        return cekori;
    }
    for(int i=0; i<4; i++){
    int ti=ci+di[i];
    int tj=cj+dj[i];
    if((ti>=0)and(ti<n)and(tj>=0)and(tj<m)and(maze[ti][tj]!='*')){
       if(((maze[ti][tj]=='.')or(maze[ti][tj]=='E'))and(visited[ti][tj][bitmask][mozni]==false)){
        q.push(ti);
        q.push(tj);
        q.push(bitmask);
        q.push(mozni);
        q.push(cekori+1);
        visited[ti][tj][bitmask][mozni]=true;
       }
       if(maze[ti][tj]=='K'){
        int def=(mat[ti][tj]);
        int novamaska=(bitmask | (1 << def));

        int x=0;

        if((bitmask & (1 << def)) == 0){
            x = 1;
        }
           
        if(visited[ti][tj][novamaska][mozni+x]==false){
        q.push(ti);
        q.push(tj);
        q.push(novamaska);
        q.push(mozni+x);
        q.push(cekori+1);
            visited[ti][tj][novamaska][mozni + x] = true;
        }
       }
    }
    }

    if(mozni>0){
            for(int i=0; i<8; i++){
            int ti=ci+ki[i];
            int tj=cj+kj[i];
            if((ti>=0)and(ti<n)and(tj>=0)and(tj<m)and(maze[ti][tj]!='*')){
       if(((maze[ti][tj]=='.')or(maze[ti][tj]=='E'))and(visited[ti][tj][bitmask][mozni-1]==false)){
        q.push(ti);
        q.push(tj);
        q.push(bitmask);
        q.push(mozni-1);
        q.push(cekori+1);
        visited[ti][tj][bitmask][mozni - 1]=true;
       }
       if(maze[ti][tj]=='K'){
        int def=(mat[ti][tj]);
        int novamaska=(bitmask | (1 << def));

        int x=0;
           
           if((bitmask & (1 << def)) == 0){
               x = 1;
           }
           
        if(visited[ti][tj][novamaska][mozni+x-1]==false){
        q.push(ti);
        q.push(tj);
        q.push(novamaska);
        q.push(mozni+x-1);
        q.push(cekori+1);
            visited[ti][tj][novamaska][mozni + x - 1] = true;
        }
       }

       }

    }
    }
    
    }
    return -1;





}
};
/*
 {"*........**K*.",".****....****.","*.***.**S.K*..","***..***.*....","E..*...***...*","**...**..*..*K",".*..*.*...*...","..*.*.*.......","......*.*.....",".*..***.***..*",".**.**.***.**.","*.*......**.*.","**.*....*...**"}
 */
const int Test_No=0;

int main()
{
  ChessMaze tmp;
  int res;
  vector<string> *maze;
/***************************Test 1 ********************************/

if(Test_No==0 || Test_No==1){
    string ABC0[]= {"*........**K*.",".****....****.","*.***.**S.K*..","***..***.*....","E..*...***...*","**...**..*..*K",".*..*.*...*...","..*.*.*.......","......*.*.....",".*..***.***..*",".**.**.***.**.","*.*......**.*.","**.*....*...**"};

maze= new vector<string> (&ABC0[0],&ABC0[13]);
res = tmp.traverseMaze(*maze);
if(res == 14) cout<<"test #"<<1<<" Correct!\n\n";
  else {cout<<"test #"<<1<<" Wrong!\n";
cout<<"Expected: "<<14<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 2 ********************************/

if(Test_No==0 || Test_No==2){
string ABC1[]={".SE","KKK"};
maze= new vector<string> (&ABC1[0],&ABC1[2]);
res = tmp.traverseMaze(*maze);
if(res == 1) cout<<"test #"<<2<<" Correct!\n\n";
  else {cout<<"test #"<<2<<" Wrong!\n";
cout<<"Expected: "<<1<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 3 ********************************/

if(Test_No==0 || Test_No==3){
string ABC2[]={"K.",".S","..",".*","*E"};
maze= new vector<string> (&ABC2[0],&ABC2[5]);
res = tmp.traverseMaze(*maze);
if(res == 5) cout<<"test #"<<3<<" Correct!\n\n";
  else {cout<<"test #"<<3<<" Wrong!\n";
cout<<"Expected: "<<5<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 4 ********************************/

if(Test_No==0 || Test_No==4){
string ABC3[]={"..*E","K*SK"};
maze= new vector<string> (&ABC3[0],&ABC3[2]);
res = tmp.traverseMaze(*maze);
if(res == 2) cout<<"test #"<<4<<" Correct!\n\n";
  else {cout<<"test #"<<4<<" Wrong!\n";
cout<<"Expected: "<<2<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 5 ********************************/

if(Test_No==0 || Test_No==5){
string ABC4[]={".E.KK","*K.S*"};
maze= new vector<string> (&ABC4[0],&ABC4[2]);
res = tmp.traverseMaze(*maze);
if(res == 3) cout<<"test #"<<5<<" Correct!\n\n";
  else {cout<<"test #"<<5<<" Wrong!\n";
cout<<"Expected: "<<3<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 6 ********************************/

if(Test_No==0 || Test_No==6){
string ABC5[]={"*E.**","*..SK","****.","..***"};
maze= new vector<string> (&ABC5[0],&ABC5[4]);
res = tmp.traverseMaze(*maze);
if(res == 3) cout<<"test #"<<6<<" Correct!\n\n";
  else {cout<<"test #"<<6<<" Wrong!\n";
cout<<"Expected: "<<3<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 7 ********************************/

if(Test_No==0 || Test_No==7){
string ABC6[]={".*","EK",".K","S."};
maze= new vector<string> (&ABC6[0],&ABC6[4]);
res = tmp.traverseMaze(*maze);
if(res == 2) cout<<"test #"<<7<<" Correct!\n\n";
  else {cout<<"test #"<<7<<" Wrong!\n";
cout<<"Expected: "<<2<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 8 ********************************/

if(Test_No==0 || Test_No==8){
string ABC7[]={".*.",".**","ES.","...",".KK"};
maze= new vector<string> (&ABC7[0],&ABC7[5]);
res = tmp.traverseMaze(*maze);
if(res == 1) cout<<"test #"<<8<<" Correct!\n\n";
  else {cout<<"test #"<<8<<" Wrong!\n";
cout<<"Expected: "<<1<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 9 ********************************/

if(Test_No==0 || Test_No==9){
string ABC8[]={"...*.","..***","...K*","S*E**"};
maze= new vector<string> (&ABC8[0],&ABC8[4]);
res = tmp.traverseMaze(*maze);
if(res == 4) cout<<"test #"<<9<<" Correct!\n\n";
  else {cout<<"test #"<<9<<" Wrong!\n";
cout<<"Expected: "<<4<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


/***************************Test 10 ********************************/

if(Test_No==0 || Test_No==10){
string ABC9[]={".*..","*.K.","KS.*","*KE*"};
maze= new vector<string> (&ABC9[0],&ABC9[4]);
res = tmp.traverseMaze(*maze);
if(res == 2) cout<<"test #"<<10<<" Correct!\n\n";
  else {cout<<"test #"<<10<<" Wrong!\n";
cout<<"Expected: "<<2<<"\n";
cout<<"Recieved: "<< res <<" \n\n";}
cout<<"---------------------------------------------"<<"\n";

}
/******************************************************************/


  return 0;

}