题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6073

题意：给个图，求每个完全匹配的权值的积，最后再求和

解法：首先用拓扑排序处理一下度为1的边，这些边对答案的贡献就是它的权值，不难想到答案就是ans1*sigma(每个连通块的贡献)，所谓连通块就是指删掉度为1的点，剩下的联通块的方案数，所以在拓扑的过程中直接乘以度为1的边的权值，之后对每个环DFS，得到当前这个环贡献的答案，由于是匹配只有两种答案，交替走就可以了，这个用DFS可以轻松搬办到。


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 300010;
const int mod = 998244353;
struct FastIO
{
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar()
    {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint()
    {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint()
    {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s)
    {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c > 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x)
    {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x)
    {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s)
    {
        while (*s) wchar(*s++);
    }
    ~FastIO()
    {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
struct edge{
    int to,w,next;
    bool mark;
}E[maxn*4];
int T, n, head[maxn*2], edgecnt, du[maxn*2], used[maxn*2];
LL temp[2];
void init(){
    memset(head,-1,sizeof(head));
    edgecnt=0;
}
void add(int u, int v, int w){
    E[edgecnt].to=v,E[edgecnt].w=w,E[edgecnt].next=head[u],E[edgecnt].mark=0,head[u]=edgecnt++;
}
void dfs(int x, int id){
    used[x]=1;
    for(int i=head[x];~i;i=E[i].next){
        if(E[i].mark) continue;
        E[i].mark=E[i^1].mark=1;
        temp[id]*=E[i].w;
        temp[id]%=mod;
        dfs(E[i].to, 1-id);
    }
}

int main()
{
    T = io.xint();
    while(T--){
        init();
        n = io.xint();
        memset(du, 0, sizeof(du));
        memset(used, 0, sizeof(used));
        int u,v,w;
        for(u=1; u<=n; u++){
            for(int i=1; i<=2; i++){
                //scanf("%d%d",&v,&w);
                v = io.xint();
                w = io.xint();
                add(u,v+n,w);
                add(v+n,u,w);
                du[u]++;
                du[v+n]++;
            }
        }
        LL ans=1;
        queue <int> q;
        for(u=n+1; u<=n+n; u++){
            if(du[u]==1){
                q.push(u);
            }
        }
        while(q.size())
        {
            u=q.front(); q.pop();
            used[u]=1;
            for(int i=head[u]; ~i; i=E[i].next){
                if(E[i].mark) continue;
                E[i].mark=E[i^1].mark=1;
                used[E[i].to]=1;
                ans*=E[i].w;
                ans%=mod;
                for(int j=head[E[i].to]; ~j; j=E[j].next){
                    E[j].mark=E[j^1].mark=1;
                    du[E[j].to]--;
                    if(du[E[j].to]==1) q.push(E[j].to);
                }
            }
        }
        for(int i=1; i<=n; i++){
            if(used[i]) continue;
            temp[0]=temp[1]=1;
            dfs(i,0);
            ans=(ans%mod*(temp[0]+temp[1])%mod)%mod;
        }
        ans %= mod;
        printf("%lld\n", ans);
    }
    return 0;
}