3しりとりのルールから,最初の3文字と最後の3文字が重要になる.
それらを頂点として,高橋辞書に登録された文字列を辺とみたグラフを考える.
ゲーム理論の問題では,
・ルールに従った移動を辺で表して,現在の局面を頂点で表す
・勝敗が決まった局面から逆算して,新たに勝敗が決まる(後退解析)
が基本であり,この問題も基本通り.
各頂点に関する勝敗は,手番を持っている側の視点とする.
・行先がない頂点は lose
・行先がすべて win の頂点は lose
・行先に lose が存在する頂点は win
・それ以外は draw
頂点を訪れたとき,どの様なパスで訪れたかは無関係.
実装するときは初期化は draw にしておく.
最初に,出次数が0の頂点の勝敗を決める.
調べた頂点は次数を減らしていき,次数が0になったらqueue に追加する.
矢の向きを逆にしたグラフを用意すると楽かも.
typedef long long ll;
const ll INFL = 1LL << 60;
using pll = pair<ll,ll>;
ll c_to_i(char c){
ll i = 0;
if(c <= 'Z') i += c - ('A');
else i += 26 + (c - 'a');
return i;
}
ll s_to_i(string s){
ll x = 0;
rep(i,s.size()) {
x = x*52 + c_to_i(s[i]);
}
return x;
}
string substring(auto it, int len){
string t;
rep(i,len){
t.push_back(*it);
++it;
}
return t;
}
int main() {
ll n; cin >> n;
ll v = 52*52*52;// vertices
vvll to(v);
vll cnt(v);
rep(i,n){
cin >> s[i];
string _f,_b;
_f = substring(s[i].begin(), 3);
_b = substring(s[i].end()-3, 3);
ll b = s_to_i(_b);
ll f = s_to_i(_f);
to[b].push_back(f);
cnt[f]++;
ed[i] = {f,b};
}
DRAW = 0,
LOSE,
WIN
};
vll res(v, DRAW);
queue<ll> que;
rep(i,v){
if(cnt[i] == 0) {
que.push(i);
res[i] = LOSE;
}
}
while(que.size()){
ll cu = que.front(); que.pop();
// if(res[cu] == DRAW) continue; // 無くてもよい
fore(ne, to[cu]){
if(res[cu] == LOSE && res[ne] == DRAW){ //必要: && res[ne] == DRAW
res[ne] = WIN;
que.push(ne); // 確定したら追加
}
else if(res[cu] == WIN && res[ne] == DRAW){//必要: && res[ne] == DRAW
cnt[ne]--;
if(cnt[ne] == 0){
res[ne] = LOSE;
que.push(ne); // 確定したら追加
}
}
}
}
rep(i,n){
ll x = ed[i].second;
if(res[x] == WIN){
cout << "Aoki" << endl;
}
if(res[x] == LOSE){
cout << "Takahashi" << endl;
}
if(res[x] == DRAW){
cout << "Draw" << endl;
}
}
return 0;
}