
ZOJ Problem Set  4097
Princess Cjb is caught by Heltion again! Her knights Little Sub and Little Potato are going to Heltion Kingdom to rescue her. Heltion Kingdom is composed of $n$ islands, numbered from $1$ to $n$. There are $m$ bridges in the kingdom, among which the $i$th bridge connects the $l_i$th island and the $r_i$th island. The knights can go through each bridge in both directions. Landing separately on the $v$th and the $w$th island, the two knights start their journey heading to the $u$th island where the princess is imprisoned. However, as the knights are fat and the bridges are unstable, there will be a risk of breaking down the bridge and falling into the water if they go through one or more common bridges during their journey. Thus, to successfully bring back the princess, two paths \textbf{with no common bridges} are needed: one starts from the $v$th island and leads to the $u$th island, while the other starts from the $w$th island and also leads to the $u$th island. As the princess is caught very often, the knights will ask you for help $q$ times. Each time, given their starting islands and their goal, you need to tell them whether it's possible to find two paths satisfying the constraints above. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $q$ ($1 \le n \le 10^5$, $0 \le m \le 2 \times 10^5$, $1 \le q \le 10^5$), indicating the number of islands, the number of bridges and the number of queries. The following $m$ lines describe the bridges. The $i$th line contains two integers $l_i$ and $r_i$ ($1 \le l_i,r_i \le n$), indicating the two islands the $i$th bridge connects. Notice that different bridges may connect the same pair of islands and a bridge may connect an island to itself. The following $q$ lines describe the queries. The $i$th line contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i,v_i,w_i \le n$), indicating the island where the princess is imprisoned and the starting islands of the two knights. It's guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$, the sum of $m$ of all test cases will not exceed $10^6$, and the sum of $q$ of all test cases will not exceed $5 \times 10^5$. OutputFor each test case output $q$ lines indicating the answers of the queries. For each query, if two paths meeting the constraints can be found, output "Yes" (without quotes), otherwise output "No" (without quotes). Sample Input2 6 7 4 1 2 2 3 3 1 4 5 5 6 6 4 1 4 4 1 3 1 4 2 1 2 3 1 3 3 2 1 2 1 2 1 1 1 2 1 2 Sample OutputNo Yes Yes Yes Yes Yes HintFor the first sample test case:
For the second sample test case:
Author: CHEN, Shihan Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple 