Description

In Pumpkin Country, there exists a mysterious two-player game between Alice and Bob. Initially, they are given a simple undirected connected graph with $n$ vertices and $m$ edges, referred to as the initial graph, where all edges are uncolored. Subsequently, each edge $(u_i, v_i)$ is assigned a color $a_i$, where $a_i \in [1, k]$ and is a positive integer. The graph after coloring is called the target graph. Then, the game begins with the following process:

• The initial graph is first given to Alice. Then, Alice and Bob engage in several game rounds.

• In each round:

  • Alice first selects an uncolored edge and chooses one of its vertices $u$, then colors all edges connected to $u$ with a color from $1$ to $k$. Edges that have been colored but not locked can also be overwritten.

  • Next, Bob locks any edge that has been colored but not locked, making its color unchangeable thereafter. The round then ends and the next round begins.

• If after some round Alice can color the initial graph to match the target graph, then Alice wins. Note that this only requires all edge colors to match the target graph, not that all edges are locked.

• If it can be proven that Alice can never win, then Bob wins.

Recently, Little P wants to play this game with his best friend. Little P will be player Alice, while his friend will be player Bob. By some means, Little P has obtained all possible target graphs, and now he wants to know when he has a winning strategy. Assume both he and his friend are extremely intelligent.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains three positive integers $n, m, k$, representing the number of vertices, edges, and color types in the target graph.

• The next $m$ lines each contain three positive integers $u, v, c$, indicating an undirected edge $(u, v)$ with color $c$. It is guaranteed that every edge $(u,v)$ appears at most once.

This problem involves large input data, so it is recommended to use faster input methods.

Output Format

For each test case, output Yes if Little P has a winning strategy, otherwise output No.

2
8 8 3
1 2 1
2 3 3
3 4 2
4 5 3
5 1 2
6 1 2
7 6 2
8 1 3
8 8 2
1 2 1
2 3 1
3 4 1
4 5 1
5 1 1
6 1 1
7 6 1
8 1 2

No
Yes

Hint

Sample Explanation

• For the first test case, it can be proven that Alice will always lose.

• For the second test case, the game may proceed as follows (the game process is for reference only, and both players may not necessarily adopt optimal strategies):

  Alice chooses to color vertex $6$, then Bob locks edge $(1,6)$.

  Alice chooses to color vertex $2$, then Bob locks edge $(1,2)$.

  Alice chooses to color vertex $3$, then Bob locks edge $(2,3)$.

  Alice chooses to color vertex $5$, then Bob locks edge $(1,5)$.

  Alice chooses to color vertex $8$, then Bob locks edge $(1,8)$.

  At this point, Alice has won.

  It can be proven that Alice has a winning strategy.

Data Constraints

This problem uses subtask bundling/dependencies.

• Subtask 0 (0 pts): Sample cases.
• Subtask 1 (6 pts): $T=3, n=5, m \le n$.
• Subtask 2 (18 pts): $\sum n \le 10^5, k=2$.
• Subtask 3 (16 pts): $\sum n \le 10^5$. The graph is a pseudotree.
• Subtask 4 (28 pts): $\sum n \le 1.5 \times 10^3, \sum m \le 3 \times 10^3$. Depends on subtask $0$.
• Subtask 5 (32 pts): No additional constraints. Depends on subtasks $0\sim4$.

For all test cases, it is guaranteed that $2 \le n, \sum n \le 10^6$, $1 \le m, \sum m \le 2 \times 10^6$, $1 \le k \le 10^9$. The graph is a simple undirected connected graph.