Fixed Length Walk Queries

You are given an undirected graph with n nodes and m edges. The graph is simple and connected. You start at a specific node, and on each turn you must move through an edge to another node. Your task is to answer q queries of the form: "is it possible to start at node a and end up on node b after exactly x turns?"

Input

The first line contains three integers n, m and q: the number of nodes, edges and queries. The nodes are numbered 1,2,\dots,n. After this, there are m lines which describe the edges. Each line contains two integers a and b: there is an edge between nodes a and b. Finally, there are q lines, each describing a query. Each line contains three integers a, b and x.

Output

For each query, print the answer (YES or NO) on its own line.

Constraints

$2 \le n \le 2500$

$1 \le m \le 5000$

$1 \le q \le 10^5$

$0 \le x \le 10^9$

Example

Input

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

Output

YES
NO
YES
NO
YES
YES

Explanation:

In query 1, a possible route is 1 \rightarrow 3 \rightarrow 2.

In query 3, a possible route is 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4.

In query 6, a possible route is 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4.