链接: https://cses.fi/problemset/task/3357

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个含有 $n$ 个节点和 $m$ 条边的无向图。该图是简单且连通的。

你从一个特定的节点出发，每走一步都必须经过一条边到达另一个节点。

你的任务是回答 $q$ 个形如“是否可能从节点 $a$ 出发，恰好经过 $x$ 步后到达节点 $b$”的查询。

输入

第一行包含三个整数 $n$、$m$ 和 $q$：节点数量、边的数量和查询数量。节点编号为 $1,2,\dots,n$。

接下来有 $m$ 行描述边。每行包含两个整数 $a$ 和 $b$：表示节点 $a$ 与 $b$ 之间有一条边。

最后有 $q$ 行，每行描述一个查询。每行包含三个整数 $a$、$b$ 和 $x$。

输出

对于每个查询，在其所在行输出答案（YES 或 NO）。

数据范围

$2 \le n \le 2500$ $1 \le m \le 5000$ $1 \le q \le 10^5$ $0 \le x \le 10^9$

样例输入

4 5 6
1 2
2 3
1 3
2 4
3 4
1 2 2
1 4 1
1 4 5
2 2 1
2 2 2
3 4 8

样例输出

YES
NO
YES
NO
YES
YES