题意： 给出一个二部图，U、V分别是二部图的两个点集，其中，U中每个点会有两条边连到V中两个不同的点。
完美匹配定义为：所有点都成功匹配。
思路：已知一定是完美匹配了呀(也一定存在)，我们先把度数为一的匹配了(用拓扑把度数为一的找出来)，那么剩下的图中左右各有m个点，每个点度数都不小于2，且左边每个点度数都是2，而右侧总度数是2m，因此右侧只能是每个点度数都是2。这说明这个图每个连通块是个环，在环上间隔着取即可，一共两种方案。
然后就完了(还是看了别人的才懂得ε=ε=ε=┏(゜ロ゜;)┛)。
/* gyt Live up to every day */ #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<cstring> #include<queue> #include<set> #include<string> #include<map> #include <time.h> #define PI acos(-1) using namespace std; typedef long long ll; typedef double db; const int maxn = 6e5+10; const int maxm=5000+10; const ll mod = 998244353; const int INF = 0x3f3f3f; const db eps = 1e-9; struct node { ll w; int v, next; }edge[maxn<<1]; int no, head[maxn]; int bad[maxn], deg[maxn], vis[maxn]; int n, nn; queue<int>q; vector<int>vtt; ll ans, must; void init() { no=0; memset(vis, 0, sizeof(vis)); memset(head, -1, sizeof(head)); memset(bad, 0, sizeof(bad)); memset(deg, 0, sizeof(deg)); } void add(int u, int v, int w) { edge[no].v=v; edge[no].next=head[u]; edge[no].w=w; head[u]=no++; } ll dfs(int cur, int father) { vtt.push_back(cur); vis[cur] = 1; for(int k = head[cur], kk; k != -1; k = edge[k].next) { int v = edge[k].v; if(v == father) continue; if(bad[v] || vis[v]) continue; vis[v] = 1; vtt.push_back(v); for(kk = head[v]; kk != -1; kk = edge[kk].next) { if(!bad[edge[kk].v] && edge[kk].w != cur) break; } return dfs(edge[kk].v, v)*edge[k].w%mod; } return 1; } void solve() { init(); scanf("%d", &n); nn=n*2; for (int i=1; i<=n; i++) { int v, w; scanf("%d%d", &v, &w); add(i, n+v, w); add(n+v, i, w); deg[i]++, deg[n+v]++; scanf("%d%d", &v, &w); add(i, n+v, w); add(n+v, i, w); deg[i]++, deg[n+v]++; } must=1; while(!q.empty()) q.pop(); for (int i=1; i<=n; i++) { if (deg[n+i]==1) q.push(n+i); //把度数为一的提出来 } while(!q.empty()) { int u=q.front(); q.pop(); bad[u]=1; for (int k=head[u]; ~k; k=edge[k].next) { //找到度数为一的点连的另一个点a int v=edge[k].v; if (bad[v]) continue; must=must*edge[k].w%mod; bad[v]=1; for (int kk=head[v]; ~kk; kk=edge[kk].next) {//把a相连的点找出来，如果减掉1还是1，说明他能匹配的也只能是一个 if (bad[edge[kk].v]) continue;if (--deg[edge[kk].v]==1) { q.push(edge[kk].v); } } } } ans=must; //cout<<ans<<endl; for (int i=1; i<=n; i++) { if (vis[i]||bad[i]) continue; ll ans1=0; for(int k = head[i], kk; k != -1; k = edge[k].next) {//分别两种匹配的结果 int v=edge[k].v; vtt.clear(); vis[v]=1; for ( kk=head[v]; ~kk; kk=edge[kk].next) { if (!bad[edge[kk].v] && edge[kk].v!=i) break; } ans1=(ans1+dfs(edge[kk].v, v)*edge[k].w%mod)%mod; // cout<<ans1<<endl; vis[v]=0; for (int j=0; j<vtt.size(); j++) { vis[vtt[j]]=0; } vtt.push_back(v); } for (int j=0; j<vtt.size(); j++) { vis[vtt[j]]=1; } ans = ans*ans1%mod; } printf("%lld ", ans); } int main() { int t = 1; //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &t); while(t--) solve(); return 0; }