题目传送门
比赛时没有做出来，怪我图论基本功太差，太菜了，解题技巧也不够熟练，此类题目练习也并不多，虽然看题目就知道和二分图匹配相关，但是还是无从下手，以后要多多练习，不能一直都是弱弱吧（苦笑脸！！）。比赛结束后看了题解才恍然大悟，不过还是花了比较多的时间才写出来。
官方题解：
首先如果一个点的度数为1，那么它的匹配方案是固定的，继而我们可以去掉这一对点。通过拓扑我们可以不断去掉所有度数为1的点。
那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。
AC代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 1000;
const ll mod = 998244353;
int G[N],du[N],vis[N];
int tot,u,v,n,st;
ll d,ans,t1,t2;
struct Edge {
int to;ll w;int next;Edge(int to_=0,ll w_=0,int next_=0):to(to_),w(w_),next(next_){
}
}E[N*2];
struct node {
int u;int flag;
};
void init() {
memset(du,0,sizeof(du));memset(G,0,sizeof(G));memset(vis,0,sizeof(vis));tot = 1; ans = 1;
}
inline void addEdge(int f,int t,ll dist) {
E[tot] = Edge(t,dist,G[f]);G[f] = tot ++;E[tot] = Edge(f,dist,G[t]);G[t] = tot ++;
}
void topSort() {
queue<node>Q;for(int i=1;i<=n;i++)if(du[i] == 1)Q.push((node){
i,0});//度为1的点进行匹配 while(!Q.empty()) {
node now = Q.front(); Q.pop();int u = now.u;if(vis[u])continue;vis[u] = 1;for(int i=G[u];i;i=E[i].next) {
int v = E[i].to;if(vis[v])continue;du[v] --;//点v的度-1,因为点u会进行匹配 if(du[v] <= 1) {
if(!now.flag)ans = ans * E[i].w % mod; Q.push((node){
v,!now.flag});}}}
}void dfs(int u,int dep) {
vis[u] = 1;bool flag = true;for(int i=G[u];i;i=E[i].next) {
int v = E[i].to;if(vis[v])continue;flag = false;if(dep%2)t1 = t1 * E[i].w % mod;else t2 = t2 * E[i].w % mod;dfs(v, dep + 1);}if(flag) {
for(int i=G[u];i;i=E[i].next) if(E[i].to == st){
if(dep%2)t1 = t1 * E[i].w % mod;else t2 = t2 * E[i].w % mod;}}
}
int main() {
int t; scanf("%d",&t);while(t--) {
init();scanf("%d",&n);for(int i=1;i<=n;i++) {
for(int j=0;j<2;j++) {
scanf("%d%lld",&v,&d);v = v + n;//v集合的点加上n防止和u集合的点有交集 du[v] ++, du[i] ++;//记录每个点的度 addEdge(i,v,d);}}n = 2 * n;//(1-n)为u,(n+1-2n)为V topSort();//拓扑一下，将度为1的先匹配好 for(int i=1;i<=n;i++) {
if(!vis[i]) {
t1 = t2 = 1; st = i;/*在环上间隔着取,即st为结束点也是开始点（一个环）t1,t2(两种方案)*/dfs(i,1);ll tmp = (t1 + t2) % mod;ans = ans * tmp % mod;}}printf("%lld\n",ans);}return 0;
}