Alice 和 Bob 正在参加一场比赛。比赛由若干个独立的轮次组成。

比赛规则如下：每位选手都会被给定一个包含 $n$ 个顶点和 $m$ 条边的简单（无自环和重边）连通无向图。$n$ 和 $m$ 的值对两位选手是相同的，但图可能不同。最先找到自己图的生成树的选手将被宣布为获胜者。如果两位选手都较快地找到了生成树，则该轮宣布为平局。为了简单起见，边从 $1$ 到 $m$ 进行编号，选手只需提交他们找到的生成树中边的索引（编号）。

Alice 最近学习了许多寻找生成树的算法，她确信这场比赛会很轻松。而 Bob 这一边，他不知道任何寻找生成树的算法，但他有自己的策略。他希望主办方太懒而不去准备两个不同的图，因此他打算直接复制 Alice 的答案并提交给裁判。在过去，这种方法效果相当不错。然而，Alice 最近开始怀疑 Bob 作弊，因此她现在试图揭穿 Bob 的卑劣策略。

距离比赛结束还剩 $t$ 轮，Alice 试图赢得尽可能多的轮次。为了实现这一目标，在每一轮中，她都会在自己的图中寻找一棵生成树，使得其对应的边在 Bob 的图中不构成一棵生成树。事实证明这有些困难，因此 Alice 现在想知道是否存在这样一棵合适的生成树。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2500$)，表示剩余的轮次。

每轮的描述首先包含一行，其中有两个整数 $n$ 和 $m$ ($2 \le n \le 5000$, $n - 1 \le m \le \min\left(5000, \frac{n(n-1)}{2}\right)$)，分别表示图中的顶点数和边数。

接下来有 $m$ 行表示边。其中的第 $i$ 行包含四个整数：$u_A$、$v_A$、$u_B$ 和 $v_B$ ($1 \le u_A, u_B, v_A, v_B \le n$, $u_A \neq v_A$, $u_B \neq v_B$)。它们表示 Alice 的图中的第 $i$ 条边连接顶点 $u_A$ 和 $v_A$，而 Bob 的图中的第 $i$ 条边连接顶点 $u_B$ 和 $v_B$。两个图都是简单且连通的。

所有轮次的 $n$ 之和以及 $m$ 之和均不超过 $5000$。

输出格式

对于每一轮，判断 Alice 的图中是否存在一棵生成树，使得其对应的边在 Bob 的图中不构成一棵生成树。

如果是，则输出单行 "YES"；否则，输出 "NO"。

样例

输入样例 1

3
2 1
1 2 2 1
4 4
1 2 1 2
2 3 2 3
3 4 3 4
1 4 1 3
4 4
1 2 1 2
2 3 2 3
3 4 3 4
1 3 1 4

输出样例 1

NO
YES
NO

说明

在样例中，第一轮里，两位选手都被给定了图 A。

在第二轮里，Alice 被给定图 B，Bob 被给定图 C。在这种情况下，Alice 可以提交 $[1, 2, 4]$ 作为答案：这些边在图 B 中构成一棵生成树，但在图 C 中不构成。

在第三轮里，Alice 被给定图 C，Bob 被给定图 B。