【题目大意】
小奇特别喜欢猪，于是他养了$n$只可爱的猪，但这些猪被魔法猪教会了魔法，一不看着某些猪就会自己打起来。
小奇要带着他的猪讨伐战狂，路途中遇到了一条河。小奇找到了一条船，可惜这条船一次只能载小奇外加一只猪（可以不载猪），于是小奇只能在两条河岸之间来回运送猪或者空船跑路。
这些猪之间的关系可以用一些三元组$(a,b,c)$表示，当$a,b,c$号猪与小奇不在一起时，他们会进行斗殴。（不在一起就是指小奇此时处于河岸*或者河对岸）。
当然，小奇在运送猪的时候希望猪之间不发生任何斗殴现象，他希望询问你是否有运送方案。
有多组数据。
$T \leq 10, n \leq 1000, m \leq 3000$
【题解】
明显需要有一头猪在所有三元组里都出现，不然一定不可行，设这头猪为$tar$。
那么考虑$tar$要怎么运送，先把他运到对岸，然后运送若干的猪到对岸，再把它运回来，把其他猪运到对岸，在把它运到对岸。
那么每个三元组变成了二元组，对应连边。
很明显按照刚刚的过程，设$tar$回来的时候，小奇带的上一个是$i$；带回来后，小奇带的下一个是$j$。
求得就是删掉$i,j$后，剩下的点是否能够构成二分图。
枚举删掉的点$i$，找出dfs树，那么每个奇环就是若干个由一条返祖边代表的奇环的异或和。
一个点$x$被删掉后，为二分图，当且仅当：
1. 所有返祖边代表的奇环，在树上都经过$x$；
2. $x$的所有子树中没有一个子树内有一条奇返祖边和偶返祖边（分别形成奇环、偶环，因为这样那个删掉$x$，由这两条返祖边构成的奇环仍在）
第一个条件做一遍树上前缀和即可，第二个做树形dp即可。
复杂度$O(Tn^2)$。
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h> using namespace std; typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 3e3 + , N = 1e3 + ;
const int mod = 1e9+, inf = 1e9; inline int getint() {
int x = ; char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x<<) + (x<<) + ch - '', ch = getchar();
return x;
} int n, m, cnt[N];
struct pa {
int a, b, c;
}p[M]; int head[N], nxt[M+M], to[M+M], tot=;
inline void add(int u, int v) {
++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v;
}
inline void adde(int u, int v) {
add(u, v), add(v, u);
} bool ok;
int vis[N], dep[N], f[N][], g[N], par[N], ocnt;
inline void dfs(int x, int fa = ) {
dep[x] = dep[fa] + ;
vis[x] = ; par[x] = fa;
for (int i=head[x], y; i; i=nxt[i]) {
y = to[i];
if(vis[y]) {
if(vis[y] == && dep[y] < dep[x]) {
// cout << x << "-->" << y << endl;
int p = (dep[x]-dep[y]+)&;
f[x][p] = min(f[x][p], dep[y]);
if(p) {
// cerr << x << ' ' << y << endl;
g[x] ++, g[par[y]] --;
++ ocnt;
}
}
continue;
}
dfs(y, x);
f[x][] = min(f[x][], f[y][]);
f[x][] = min(f[x][], f[y][]);
}
} inline void gans(int x, int fa) {
vis[x] = ; bool fl = ;
for (int i=head[x]; i; i=nxt[i]) {
if(vis[to[i]]) continue;
gans(to[i], x);
if(f[to[i]][] < dep[x] && f[to[i]][] < dep[x]) fl = ;
g[x] += g[to[i]];
}
if(g[x] == ocnt && fl) ok = ;
} inline void sol() {
n = getint(), m = getint(); tot = ;
for (int i=; i<=n; ++i) head[i] = cnt[i] = ;
for (int i=; i<=m; ++i) {
++ cnt[p[i].a = getint()];
++ cnt[p[i].b = getint()];
++ cnt[p[i].c = getint()];
}
int tar = -;
for (int i=; i<=n; ++i) if(cnt[i] == m) { tar = i; break; }
if(tar == -) {
puts("no");
return ;
}
for (int i=; i<=m; ++i) {
if(p[i].a == tar) adde(p[i].b, p[i].c);
if(p[i].b == tar) adde(p[i].a, p[i].c);
if(p[i].c == tar) adde(p[i].a, p[i].b);
}
for (int x=; x<=n; ++x) {
if(tar == x) continue;
ocnt = ; ok = ;
for (int i=; i<=n; ++i) g[i] = , par[i] = , f[i][] = f[i][] = inf, dep[i] = vis[i] = ;
vis[x] = vis[tar] = ;
for (int i=; i<=n; ++i) if(!vis[i]) dfs(i, );
for (int i=; i<=n; ++i) vis[i] = ;
vis[x] = vis[tar] = ;
for (int i=; i<=n; ++i) if(!vis[i]) gans(i, );
if(ok) {
puts("yes");
return ;
}
}
puts("no");
} int main() {
freopen("river.in", "r", stdin);
freopen("river.out", "w", stdout);
int T; T = getint();
while(T--) sol();
return ;
}