Simple Graph and Strange Queries

A simple undirected weighted graph $G$ with $N$ vertices and $M$ edges is given. Vertices are numbered from $1$ to $N$, and the weight of every edge is exactly $1$. There are $Q$ queries of the following form.

• a b k: If there is a path from vertex $a$ to vertex $b$ whose length is a multiple of $k$, print Yes. Otherwise, print No.

A path may repeat vertices or edges. The length of a path is the sum of the weights of the edges on it, so an edge that appears several times adds its weight once per traversal. Handle the queries correctly.

The first line contains three integers $N$, $M$, and $Q$, separated by spaces. ($2\le N\le 100\,000$; $0\le M\le 200\,000$; $1\le Q\le 100\,000$)

Each of the next $M$ lines contains three integers $u_i$, $v_i$, and $w_i$, meaning that edge $i$ connects $u_i$ and $v_i$ and has weight $w_i$. Each pair of vertices is connected by at most one edge. ($1\le u_i,v_i\le N$; $u_i\neq v_i$; $w_i=1$)

Each of the next $Q$ lines, starting from line $M+2$, contains a query in the form a b k. ($1\le a,b\le N$; $a\neq b$; $1\le k\le 10^9$)

All input values are integers.

For each query, print Yes if there is a path from $a$ to $b$ whose length is a multiple of $k$, and No otherwise. Print one answer per line, in the order of the queries.