Seafaring Tales Verification

Young Bytensson loves to hang out in the port tavern, where he listens to sea dogs recounting their amazing seafaring tales. Although initially he believed every word, over time he grew suspicious. Now, he has decided to verify if there is any grain of truth in these tall stories.

The problem is as follows: You are given an undirected graph with n ports and m waterways (edges). Each waterway can be sailed in both directions. A sailor’s tale is described by a starting port, an ending port and a number d which represents the exact number of waterways sailed (the walk length). Note that the same waterway may be used multiple times and the path does not need to be simple.

Your task is to answer q queries. For each query, determine whether there exists a walk (not necessarily simple) of exactly d waterways connecting two specified ports.

In other words, given a query with ports \(u\) and \(v\) and an integer \(d\), check if there is a walk of length \(d\) between \(u\) and \(v\). A walk of length \(0\) is regarded as staying at the same port (i.e. it exists if and only if \(u = v\)).

The existence of a walk can mathematically be determined by raising the adjacency matrix of the graph to the \(d^{th}\) power using Boolean matrix multiplication (with logical OR replacing addition and logical AND replacing multiplication). In the resulting matrix, the entry \((u,v)\) will be true if there exists a walk of length \(d\) from \(u\) to \(v\).

Use the provided input/output format to implement your solution.

inputFormat

The first line contains three space-separated integers \(n\), \(m\), and \(q\) representing the number of ports, waterways, and queries respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is an undirected waterway between port \(u\) and port \(v\).

The following \(q\) lines each contain three integers \(u\), \(v\), and \(d\) representing a query: Is there a walk of exactly \(d\) waterways between port \(u\) and port \(v\)?

Ports are numbered from 1 to \(n\).

outputFormat

For each query, output a single line containing YES if there exists a walk of exactly \(d\) waterways from port \(u\) to port \(v\), and NO otherwise.

sample

3 3 4
1 2
2 3
1 3
1 2 1
1 3 2
2 2 2
3 3 0

YES
YES
YES
YES