Two paths
Tag(s):

## Algorithms, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Math > Number Theory
• Algorithms > Graphs
• Data Structures > Advanced Data Structures