All Tracks Algorithms Graphs Articulation Points and Bridges Problem

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications