Two paths
/

## Algorithms, Graph, Medium-Hard

Problem
Editorial
Analytics

Given an undirected graph with n vertices and m edges. Each edge is one of the two types: white and black.

There are q queries denoted by four vertices a, b, c and d. Each query asks: can some of the black edges be deleted, so that a is reachable from b, but c is not reachable from d? Note that graph itself doesn't change from query to query.

Input format

The first line contains three integers n, m and q ($1 \leq n, m, q \leq 2 \cdot 10^5$) - number of vertices, number of edges and number of queries, respectively.

Then m lines follow.

The i-th of them contains three integers $a_i$, $b_i$ and $t_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$, $t_i \in {0, 1}$) describing edge connecting $a_i$ and $b_i$, $t_i = 0$ for black edge and $t_i = 1$ for white edge.

Then q lines follow.

The i-th of them contains four integers $a_i$, $b_i$, $c_i$ and $d_i$ ($1 \leq a_i, b_i, c_i, d_i \leq n$ — vertices in the i-th query.

Output format

For each query print Yes if it's possible to delete some black edges and satisfy the condition. Print No otherwise.

SAMPLE INPUT
5 6 4
1 2 0
1 2 0
2 3 1
1 3 0
3 4 0
4 5 0
1 2 4 5
2 5 1 4
2 5 3 4
1 1 2 2
SAMPLE OUTPUT
Yes
Yes
No
No
Explanation
• In the first query you can delete the 6-th edge (between 4 and 5).
• In the second query you can delete first, second and 4-th edges.
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...