题目描述

给 $n$ 个点 $m$ 条边无向图，有 $k$ 次询问，每次询问两个点 $s,t$ 之间是否有长度为 $d$ 的路径（不一定是简单路径）。

输入格式

I第一行输入三个整数 $n,m,k$ 。

接下来 $m$ 行，每行输入两个整数 $a,b$ 。

接下来 $k$ 行，每行输入三个整数 $s,t,d$ 。

输出格式

如果有，输出 $TAK$ ，如果没有，输出 $NIE$ 。

输入输出样例 #1

输入 #1

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

输出 #1

TAK
NIE
TAK
NIE

数据范围

对于$100\%$ 的数据，有 $2\le n\le 5\ 000$, $1\le m\le 5\ 000$, $1\le k\le 1\ 000\ 000$ , $1\le a,b\le n$,$a\ne b$ , $1\le s,t\le n$,$1\le d\le 1\ 000\ 000\ 000$ 。