题目链接：[POI2013]MOR-Tales of seafaring

因为可以来回走，所以显然只与奇偶路径有关，分别记录长度为奇数的最短路和长度为偶数的最短路即可。

注意：起点终点相同，且这个点孤立，走长度大于0的距离是不行的。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5010,M=1e6+10;
int n,m,k,d[N][2],res[M];
struct node{int ed,dis,id;};
vector<node> v[N];	vector<int> g[N];
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){
    int x=0,f=1; char ch=gc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
    return x*f;
}
inline void add(int a,int b){g[a].push_back(b),g[b].push_back(a);}
inline void bfs(int s){
	queue<int> q;	memset(d,-1,sizeof d);	q.push(s);	d[s][0]=0;
	while(q.size()){
		int u=q.front();	q.pop();
		for(auto to:g[u]){
			if(d[to][0]==-1&&d[u][1]!=-1)	d[to][0]=d[u][1]+1,q.push(to);
			if(d[to][1]==-1&&d[u][0]!=-1)	d[to][1]=d[u][0]+1,q.push(to);
		}
	}
}
signed main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;i++)	add(read(),read());
	for(int i=1,a,b,c;i<=k;i++)	
		a=read(),b=read(),c=read(),v[a].push_back({b,c,i});
	for(int i=1;i<=n;i++){
		if(!v[i].size())	continue;	bfs(i);
		for(auto j:v[i]){
			int f=j.dis%2;
			if(d[j.ed][f]!=-1&&d[j.ed][f]<=j.dis)	res[j.id]=1;
			if(i==j.ed&&!f&&j.dis%2==0&&!g[i].size()&&j.dis!=0)	res[j.id]=0;	
		}
	}
	for(int i=1;i<=k;i++)	puts(res[i]?"TAK":"NIE");
	return 0;
}