你正在和朋友们玩狼人杀游戏。在这个游戏中，共有 $n$ 个参与者，编号为 $1$ 到 $n$，你的编号是 $1$。所有参与者被分为两个阵营——一个阵营的玩家是狼人，另一个阵营的玩家是村民。村民们不知道谁是狼人，他们的目标是找出狼人。

你是一名村民，并且你有一个特殊身份：记者。你可以询问任意两名玩家（除了你自己），你将会知道他们是否属于同一阵营（都是狼人或都是村民），但你不会知道他们具体属于哪个阵营。

你知道一共有 $m$ 个狼人，并且你想找出他们。在游戏过程中，你已经提了 $k$ 个问题。在第 $i$ 个问题中，你询问了玩家 $a_i$ 和 $b_i$，并且知道了他们是否在同一阵营。在游戏对你结束之前，你最多还可以再提 $2$ 个问题；你能确定谁在狼人阵营中吗？

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 1000$) —— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le m < n \le 5 \cdot 10^5$, $0 \le k \le 5 \cdot 10^5$) —— 玩家数量、狼人阵营的玩家数量以及你已经提问的数量。

每个测试用例接下来的 $k$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$ ($2 \le a_i, b_i \le n$, $0 \le c_i \le 1$)。如果玩家 $a_i$ 和 $b_i$ 属于同一阵营，则 $c_i = 1$；否则 $c_i = 0$。

你可以假设：

• 所有回答都是正确的，且存在一个由 $m$ 名成员组成的狼人阵营；
• 所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$；
• 所有测试用例中 $k$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，如果可以在最多再进行两次询问后确定狼人阵营中的所有玩家，则输出 "Yes"；否则输出 "No"。

样例

输入样例 1

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

输出样例 1

Yes
No
Yes
Yes
No