#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
short dist[5000][5000][2];
bool island[5000];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
// Bogus solution #1
ll N, M, K;
cin >> N >> M >> K;
vector<vector<short>> graph(N);
for (int i=0; i<M; i++) {
int A, B; cin >> A >> B; A--; B--; graph[A].push_back(B); graph[B].push_back(A);
}
// edge case: no edges
for (int i=0; i<N; i++)
if (graph[i].size() == 0) island[i] = 1;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++)
dist[i][j][0] = dist[i][j][1] = -32768;
}
queue<pair<short, bool>> q;
for (ll node=0; node<N; node++) {
q.push({node, 0}); dist[node][node][0] = 0;
while (!q.empty()) {
auto [a, b] = q.front(); q.pop();
for (auto neighbor : graph[a]) {
if (dist[node][neighbor][!b] == -32768) {
q.push({neighbor, !b}); dist[node][neighbor][!b] = dist[node][a][b] + 1;
}
}
}
}
while (K--) {
int S, T, D; cin >> S >> T >> D; S--; T--;
if (S == T && island[S]) {
if (D == 0) cout << "TAK\n";
else cout << "NIE\n";
continue;
}
ll val = dist[S][T][D % 2];
if (val <= D && val != -32768) cout << "TAK\n";
else cout << "NIE\n";
}
// diophantine?
//
//
/*
Case 1:
dist[s --> t] > d; NO.
Case 2:
dist[s --> t] === d (mod 2); YES, since just repeat an edge.
Case 3:
dist[s --> t] is different.
Path will look like s --> k --> k --> t, where k --> k completes odd cycle.
Another way to think about it?
If there is a path of length N and a path of length N + 1 % 2
For each node is it possible to compute shortest even and odd paths?
Keep array[5000][5000][2] with modified bfs maybe?
1 million * N is too slow (5 billion) so need to precompute more.
m <= 5000???
Find odd cycles
*/
return 0;
}
