题目描述

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

输入格式

第一行有三个整数, $n$,$m$ and $k$ ($2\le n\le 5\ 000$, $1\le m\le 5\ 000$, $1\le k\le 1\ 000\ 000$).

下面有m行，每行两个数字a，b，代表有一条a到b的无向边

k表示有k次询问 下面k行询问，每行三个整数 a，b，d 代表是否有 a到b 长度为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

友情提示

好心人677 除了大样例，还给你提供了下面这组数据，希望能帮助你debug

3 1 1
1 2
3 3 2