[POI2013] MOR-航海故事

题目描述

年轻的拜滕森喜欢常去港口酒馆，在那里他经常听海员们讲述他们的航海故事。

起初，他相信了所有这些看似难以置信的故事。

然而，随着时间的推移，他开始产生怀疑。

他决定编写一个程序，来验证这些夸张的故事中是否有一丝真实。

拜滕森认为，虽然他无法判断这些水手是否确实经历了所有那些风暴，但至少他可以找出他们的旅行路线是否合理。

这是一项程序员的任务，而遗憾的是，拜滕森并不是程序员。

帮帮他吧！

给定一个包含 $n$ 个端口和 $m$ 条水道的无向图，这些水道位于拜滕森听到的水手们经常出没的水域中。

如果两个端口之间有水道，那么从一个端口航行到另一个端口是可行的。任何水道都可以双向航行。

拜滕森听说了 $k$ 个航海故事。

每个故事描述了一位水手从一个端口出发，经过若干条水道航行，最终到达另一个端口，这个终点端口可能是他最初出发的端口。

该水手可能多次经过同一条水道，每次可以任意方向航行。

简而言之，给定一个包含 $n$ 个点和 $m$ 条边的无向图，每次询问两个点之间是否存在长度为 $d$ 的路径（不一定是简单路径）。

输入格式

标准输入的第一行包含三个整数，$n$、$m$ 和 $k$ ($2 \le n \le 5\,000$，$1 \le m \le 5\,000$，$1 \le k \le 1\,000\,000$)。

它们分别表示：

• 由讲述航海故事的水手们经常出没的水域中的端口数量，
• 水道的数量，
• 拜滕森听到的故事数量。

接下来的 $m$ 行描述水道。

每条水道的描述由一行两个整数 $a$ 和 $b$ ($1 \le a, b \le n$，$a \ne b$) 组成，这两个整数用一个空格分隔，表示该水道两端的端口编号。

接下来的 $k$ 行描述拜滕森听到的故事。每个故事的描述由一行三个整数 $s$、$t$ 和 $d$ ($1 \le s, t \le n$，$1 \le d \le 1\,000\,000\,000$) 组成，这三个整数用一个空格分隔，表示故事中的水手从端口编号 $s$ 出发，最终到达端口编号 $t$，并且恰好航行了 $d$ 次水道。

输出格式

你的程序应当向标准输出打印恰好 $k$ 行；第 $i$ 行应包含单词 TAK（波兰语的“是”），如果第 $i$ 个故事中描述的航行（按照输入顺序）是可能发生的。

如果不可能，则该行应包含单词 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

提示

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

# [POI2013] MOR-航海故事

## 题目描述

年轻的拜滕森喜欢常去港口酒馆，在那里他经常听海员们讲述他们的航海故事。

起初，他相信了所有这些看似难以置信的故事。

然而，随着时间的推移，他开始产生怀疑。

他决定编写一个程序，来验证这些夸张的故事中是否有一丝真实。

拜滕森认为，虽然他无法判断这些水手是否确实经历了所有那些风暴，但至少他可以找出他们的旅行路线是否合理。

这是一项程序员的任务，而遗憾的是，拜滕森并不是程序员。

帮帮他吧！

给定一个包含 $n$ 个端口和 $m$ 条水道的无向图，这些水道位于拜滕森听到的水手们经常出没的水域中。

如果两个端口之间有水道，那么从一个端口航行到另一个端口是可行的。任何水道都可以双向航行。

拜滕森听说了 $k$ 个航海故事。

每个故事描述了一位水手从一个端口出发，经过若干条水道航行，最终到达另一个端口，这个终点端口可能是他最初出发的端口。

该水手可能多次经过同一条水道，每次可以任意方向航行。

简而言之，给定一个包含 $n$ 个点和 $m$ 条边的无向图，每次询问两个点之间是否存在长度为 $d$ 的路径（不一定是简单路径）。

## 输入格式

标准输入的第一行包含三个整数，$n$、$m$ 和 $k$ ($2 \le n \le 5\,000$，$1 \le m \le 5\,000$，$1 \le k \le 1\,000\,000$)。

它们分别表示：
- 由讲述航海故事的水手们经常出没的水域中的端口数量，
- 水道的数量，
- 拜滕森听到的故事数量。

接下来的 $m$ 行描述水道。

每条水道的描述由一行两个整数 $a$ 和 $b$ ($1 \le a, b \le n$，$a \ne b$) 组成，这两个整数用一个空格分隔，表示该水道两端的端口编号。

接下来的 $k$ 行描述拜滕森听到的故事。每个故事的描述由一行三个整数 $s$、$t$ 和 $d$ ($1 \le s, t \le n$，$1 \le d \le 1\,000\,000\,000$) 组成，这三个整数用一个空格分隔，表示故事中的水手从端口编号 $s$ 出发，最终到达端口编号 $t$，并且恰好航行了 $d$ 次水道。

## 输出格式

你的程序应当向标准输出打印恰好 $k$ 行；第 $i$ 行应包含单词 **TAK**（波兰语的“是”），如果第 $i$ 个故事中描述的航行（按照输入顺序）是可能发生的。

如果不可能，则该行应包含单词 **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

## 提示

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