#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename Vert=int, typename Flow=int, int NV = 50>
class MaxFlow
{
vector<int> G[NV];
Flow F[NV][NV];
public:
void addEdge(Vert s, Vert t)
{
G[s].push_back(t);
G[t].push_back(s);
F[s][t] = 1;
F[t][s] = 1;
}
Flow calc(Vert S, Vert D)
{
for (Flow total = 0;; ) {
// Do BFS and compute the level for each node.
int LV[NV] = { 0 };
vector<int> Q(1, S);
for (int lv = 1; !Q.empty(); ++lv) {
vector<int> Q2;
for (size_t i = 0; i != Q.size(); ++i) {
const vector<int>& ne = G[Q[i]];
for (size_t j = 0; j != ne.size(); ++j)
if (F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j] != S)
LV[ne[j]] = lv, Q2.push_back(ne[j]);
}
Q.swap(Q2);
}
// Destination is now unreachable. Done.
if (!LV[D])
return total;
// Iterating DFS.
bool blocked[NV] = {};
total += dinic_dfs(S, D, LV, 0x7fffffff, blocked);
}
}
private:
Flow dinic_dfs(int v, int D, int LV[], Flow flow_in, bool blocked[])
{
Flow flow_out = 0;
for (size_t i = 0; i != G[v].size(); ++i) {
int u = G[v][i];
if (LV[v] + 1 == LV[u] && F[v][u]) {
Flow f = min(flow_in - flow_out, F[v][u]);
if (u == D || !blocked[u] && (f = dinic_dfs(u, D, LV, f, blocked))>0) {
F[v][u] -= f;
F[u][v] += f;
flow_out += f;
if (flow_in == flow_out) return flow_out;
}
}
}
blocked[v] = (flow_out == 0);
return flow_out;
}
};
class AngelDemonGame { public:
string winner(vector <string> G, int A, int D)
{
const int N = G.size();
if (D >= N - 1)
return "Demon"; // by cutting all the edges around 0.
// Since A>=2, there are at least (n-1) way
// 0--(n-1) or 0--k--(n-1) for all k
// possible and disjoint paths. Devil cannot prevent all of them.
// If and only if Angle can make mincut > D, Angle certainly wins.
// Otherwise Demon may luckily choose the mincut.
return canMakeMinCutLargerThanD(N, G, A, D) ? "Angel" : "Unknown";
}
bool canMakeMinCutLargerThanD(int N, vector<string> G, int A, int D)
{
if (G[0][N - 1] == 'N') {
G[0][N - 1] = G[N - 1][0] = 'Y';
--A;
}
set<int> Lchance, Rchance;
for (int u = 1; u < N - 1; ++u) {
if (G[0][u] == 'N') Lchance.insert(u);
if (G[u][N-1] == 'N') Rchance.insert(u);
}
int cur = minCut(N, G);
while(cur <= D && A > 0) {
for (int u : Lchance) {
G[0][u] = G[u][0] = 'Y';
if (minCut(N, G) > cur) {
--A;
++cur;
Lchance.erase(u);
goto next;
}
G[0][u] = G[u][0] = 'N';
}
for (int u : Rchance) {
G[u][N-1] = G[N-1][u] = 'Y';
if (minCut(N, G) > cur) {
--A;
++cur;
Rchance.erase(u);
goto next;
}
G[u][N - 1] = G[N - 1][u] = 'N';
}
if (!Lchance.empty()) {
int u = *Lchance.begin();
G[0][u] = G[u][0] = 'Y';
Lchance.erase(u);
--A;
goto next;
}
if (!Rchance.empty()) {
int u = *Rchance.begin();
G[0][u] = G[u][0] = 'Y';
Rchance.erase(u);
--A;
goto next;
}
next:;
}
return cur > D;
}
int minCut(int N, const vector<string>& G)
{
MaxFlow<> mf;
for (int u = 0; u < N; ++u)
for (int v = u + 1; v < N; ++v)
if (G[u][v] == 'Y')
mf.addEdge(u, v);
return mf.calc(0, N - 1);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, AngelDemonGame().winner(G, A, D));}
int main(){
CASE(0)
string G_[] = {"NYNY",
"YNYY",
"NYNN",
"YYNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 2;
int D = 2;
string _ = "Angel";
END
CASE(1)
string G_[] = {"NYNY",
"YNYY",
"NYNN",
"YYNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 6;
int D = 6;
string _ = "Demon";
END
CASE(2)
string G_[] = {"NNNN",
"NNNN",
"NNNN",
"NNNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 2;
int D = 2;
string _ = "Unknown";
END
CASE(3)
string G_[] = {"NYNNNY",
"YNNYNN",
"NNNNYN",
"NYNNNN",
"NNYNNN",
"YNNNNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 4;
int D = 4;
string _ = "Unknown";
END
CASE(4)
string G_[] = {"NYNNNY",
"YNNYNN",
"NNNNYN",
"NYNNNN",
"NNYNNN",
"YNNNNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 8;
int D = 4;
string _ = "Angel";
END
CASE(5)
string G_[] = {"NYNNNY",
"YNNYNN",
"NNNNYN",
"NYNNNN",
"NNYNNN",
"YNNNNN"};
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 4;
int D = 8;
string _ = "Demon";
END
CASE(6)
string G_[] = { "NNNN","NNNN","NNNN","NNNN" };
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = 4;
int D = 2;
string _ = "Unknown";
END
/*
CASE(7)
string G_[] = ;
vector <string> G(G_, G_+sizeof(G_)/sizeof(*G_));
int A = ;
int D = ;
string _ = ;
END
*/
}
// END CUT HERE