Two paths

4

2 votes
Algorithms, Approved, Graphs, Medium
Problem

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 (1n,m,q2105) - number of vertices, number of edges and number of queries, respectively.

Then m lines follow.

The i-th of them contains three integers ai, bi and ti (1ai,bin, aibi, ti0,1) describing edge connecting ai and bi, ti=0 for black edge and ti=1 for white edge.

Then q lines follow.

The i-th of them contains four integers ai, bi, ci and di (1ai,bi,ci,din — 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.

Time Limit: 2
Memory Limit: 512
Source Limit:
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.
Editor Image

?