[ABC209E] Shiritori

code:

#include<bits/stdc++.h>
using namespace std;
int n,u,cnt,len;
int a[1000006],vis[1000006];
string l,r[1000006],str,ans[3]={"Aoki","Draw","Takahashi"};
queue<int>q;
map<string,int>c;
vector<int>e[1000006];
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		cin>>str;
		l="";
		len=str.length();
		for (int j=  0  ;j< 3 ;j++)  l +=str[j];
		for (int j=len-3;j<len;j++)r[i]+=str[j];
		if(!c[  l ])c[  l ]=++cnt;
		if(!c[r[i]])c[r[i]]=++cnt;
		 e [c[r[i]]].push_back(c[  l ]);
		vis[c[  l ]]=1;
	}
	for (int i=1;i<=cnt;i++){
		if(!vis[i]){
			q.push(i);
			a[i]=1;
		}
	}
	while(!q.empty()){
		u=q.front();
		q.pop();
		for (auto v:e[u]){
			vis[v]--;
			 if(!a[v]&&a[u]==1){
				a[v]=-1,
				q.push(v);
			}if(!a[v]&&a[u]==-1&&!vis[v]){
				a[v]= 1,
				q.push(v);
			}
		}
	}
	for (int i=1;i<=n;i++){
		cout<<ans[a[c[r[i]]]+1]<<endl;
	}
}