All Tracks Algorithms Graphs Articulation Points and Bridges Problem

Two paths

Algorithms, Graphs


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.

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
  • 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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications