题目描述

题目译自 XX Olimpiada Informatyczna — II etap Morskie opowieści

年轻的 Bajtinson 爱在港口酒馆流连，聆听水手们的冒险故事。起初，他对所有故事深信不疑，哪怕是最离奇的传说。后来，他逐渐起了疑心，决定编写一个程序，验证这些海上故事是否可能发生。可惜，他编程水平有限。请你帮他实现这个目标！

Bajtinson 遇到的水手们航行在一片水域，包含 $n$ 个港口和 $m$ 条航道。航道连接两个港口，表示可以从任一港口出发航行至另一港口，且航行是双向的。

Bajtinson 听到了 $k$ 个海上冒险故事。每则故事描述一名水手从某港口出发，沿航道航行若干次，最终到达某个港口（可能与起点相同）。水手可多次沿同一航道航行，且可双向航行。

输入格式

第一行包含三个整数 $n, m, k$ $(2 \leq n \leq 5000, 1 \leq m \leq 5000, 1 \leq k \leq 1000000)$，分别表示水域中的港口数量、航道数量和故事数量。

接下来的 $m$ 行描述航道，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示连接港口 $a$ 和 $b$ 的航道。

接下来的 $k$ 行描述 Bajtinson 听到的冒险故事，每行包含三个整数 $s, t, d$ $(1 \leq s, t \leq n, 1 \leq d \leq 1000000000)$，表示故事中的水手从港口 $s$ 出发，航行 $d$ 次后到达港口 $t$。

输出格式

输出 $k$ 行，第 $i$ 行若第 $i$ 个故事（按输入顺序）可能发生，输出 TAK，否则输出 NIE。

8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10

TAK
NIE
TAK
NIE

附加样例

1. $n=100, m=4950$，每个港口与所有其他港口相连，$1000000$ 个随机冒险，答案均为 TAK。
2. $n=100, m=2450$，仅同奇偶性港口间可航行，$1000000$ 个随机冒险，半数答案为 TAK，半数答案为 NIE。

数据范围与提示

对于 $50\%$ 的测试数据，$n \leq 800$。