Tales of Seafaring

Young Bytensson loves to hang around the port tavern, where the old sea dogs tell tales of their voyages. At first he believed every story, however incredible it sounded. In time, though, he grew suspicious, and he resolved to write a program that checks whether a tale could hold any grain of truth. He cannot tell whether a sailor really weathered every storm, but he can at least check whether the described itinerary makes sense. Bytensson is no programmer, so help him out.

In the waters the sailors frequent there are $n$ ports and $m$ waterways connecting them. A waterway directly joins two ports and can be sailed in either direction. Bytensson has heard $k$ tales. Each tale describes a sailor who set out from one port, sailed across some number of waterways, and finished at another port (possibly the very port he set out from). The sailor may travel along the same waterway many times, each time in either direction.

The first line contains three integers $n$, $m$, and $k$ ($2 \le n \le 5000$, $1 \le m \le 5000$, $1 \le k \le 10^6$): the number of ports, the number of waterways, and the number of tales, respectively.

Each of the next $m$ lines describes one waterway with two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), separated by a single space: the two ports joined by this waterway.

Each of the following $k$ lines describes one tale with three integers $s$, $t$, and $d$ ($1 \le s, t \le n$, $1 \le d \le 10^9$), separated by single spaces: the tale's sailor set out from port $s$, finished at port $t$, and sailed across exactly $d$ waterways in total.

Print exactly $k$ lines. On the $i$-th line print TAK (Polish for “yes”) if the journey described in the $i$-th tale (in input order) could have taken place, or NIE (Polish for “no”) if it could not.