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$.