Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4097
Rescue the Princess

Time Limit: 1 Second      Memory Limit: 65536 KB

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.

Input

There 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$.

Output

For 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 Input

2
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 Output

No
Yes
Yes
Yes
Yes
Yes

Hint

For the first sample test case:

  • For the 2nd query, we can select the paths 4-1 and 2-1.
  • For the 3rd query, we can select the paths 2-1 and 3-1.
  • For the 4th query, we can select the paths 3-1 and 3-2-1.

For the second sample test case:

  • For the 1st query, as the knights and the princess are on the same island initially, the answer is "Yes".
  • For the 2nd query, as one of the knights are on the same island with the princess initially, he does not need to cross any bridge. The other knight can go from island 1 to island 2 directly.


Author: CHEN, Shihan
Source: The 19th Zhejiang University Programming Contest Sponsored by TuSimple
Submit    Status