// IDEA: this is incredibly hard
// 1st, consider the problem as a bi-partite graph (partitions L, R)
// 2nd, note that Ethan will always have a winning strategy, UNLESS there
//  is none - this happens only if there is a perfect matching in the graph
//  i.e., every vertex in L is matched to exactly one in R

// 3rd, to find the perfect matching, you can either use an algorithm
// based on M-augmenting paths, OR
// do what I do which is construct a network flow from L to R and maximize
// the flow - this will give you the biggest matching

// VERDICT: I don't know how you could possibly do this during the contest...

#include <iostream.h>
#include <fstream.h>

int A[26+2][26+2]; // airports are 1 based; s=0, t=N*M+1
int N, M;

int p[28]; // path from s to t

int B[28][28]; // residual graph; not really needed

int f[28][28];  // flow

#define min(a,b) (a < b ? a : b)

int cf (int u, int v)  // A[i][j] == c[i][j] ?
{
 return A[u][v] - f[u][v];
}

// shortest path from vertex x to y (Dietrich == Dijkstra)
int Dietrich(int x, int y)
{
 int NN = N+M+2;

 int from[28];
 for (int i=0; i < NN; i++)
  from[i] = -1;

 int Mat[28][28];
 memset(Mat, 0, sizeof(Mat) );

 for (i=0; i < NN; i++)
  Mat[i][i] = 1;

 for (i=0; i < NN; i++)
  for (int j=0; j < NN; j++)
   if (Mat[x][j] > 0)
    for (int k=0; k < NN; k++)
     if (B[j][k] > 0)
     {
      if (Mat[x][k] == 0 || Mat[x][k] > Mat[x][j] + 1)
      {
       Mat[x][k] = Mat[x][j] + 1;  // B[j][k] = 1
       from[k] = j;
      }
     }

 if (Mat[x][y] == 0) return 0; // no path

 // construct path
 int cnt = 0;

 i=y;
 while (i != x)
 {
  p[cnt++] = i;
  i = from[i];
 }
 p[cnt++] = x;
 p[cnt++] = -1;

 return 1;

}

int Karp ()  // maximum flow using Karp- network flow method
{
 memset(f, 0, sizeof(f) );

 // construct residual graph
 memcpy(B, A, sizeof(B) );

 while (Dietrich(0, N+M+1))
 {
   // have an augmenting path, p

   // find min. capacity
   int cfp = cf(p[1], p[0]);

   int i = 2;
   while (p[i] >= 0)
   {
    cfp = min(cfp, cf(p[i], p[i-1]) );
    i++;
   }

   // reset f
   i = 1;
   while (p[i] >= 0)
   {
    f[ p[i] ][ p[i-1] ] += cfp;
    f[ p[i-1] ][ p[i] ] = - f[ p[i] ][ p[i-1] ];
    i++;
   }

   // construct residual graph
   for (i=0; i < N+M+2; i++)
    for (int j=0; j < N+M+2; j++)
     B[i][j] = cf(i, j);


 }


 // count flow
 int flow = 0;
 for (int i=1; i < N+M+1; i++)
  flow += f[0][i];

 return flow;
}

void main()
{
 ifstream in; in.open("world.in");
 ofstream out; out.open("world.chk");

 int nn;
 in >> nn;
 for (int kk=0; kk < nn; kk++)
 {
  in >> N >> M;

  memset(A, 0, sizeof(A));

  while (1)
  {
   char x, y;
   in >> x >> y;

   if (x == '-') {char buf[20]; in.getline(buf, 20); break;}

   x -= 'a'; x++; // 1 based
   y -= 'A'; y++; y+=N; // 1 based

   A[x][y] = 1;
  }

  // connect starting & ending nodes (0 and N+M+1)
  for (int i=1; i <= N; i++)
   A[0][i] = 1;

  for (i=N+1; i <= N+M; i++)
   A[i][N+M+1] = 1;

  int juice = Karp();

  if (N == M && juice == N)
   out << "Will" << endl;
  else
   out << "Ethan" << endl;

 }

 in.close();
 out.close();
}
Downloader failed!
Response object
006~ASP 0159~Buffering Off~Buffering must be on.