AGC043C Giant Graph

神仙题，虽然用垃圾做法过掉了，但是 sol 太神仙了。

Editorial 做法：显然我们会贪心选点，因此对于点 $(x_i,y_j,z_k)$ ，设它是否会被选为状态 $dp[i][j][k]$ ，很显然这只有在 Giant Graph 中与它直接相连的点有关，即若 $dp[a][b][c]$ 中有 $1$ （这里 $a,b,c$ 中有一个是在图中与 $i/j/k$ 有边的点，另外两个就是 $i/j/k$ ），则 $dp[i][j][k] = 0$ ，否则 $dp[i][j][k] = 1$ 。

这个东西可以看成博弈问题！ 即如果存在后继为必败状态，那么当前状态必胜，否则当前状态必败。

因此我们可以看成三个图的点上分别有一个 Token ，每次可以把一个图上的 Token 移动到相邻的更大的一个位置，移动不了就输了，其必胜必败态的转移和该问题的选点与否的转移等价。

根据博弈论的结论，我们可以在三个图上分别做 SG 函数的转移，最后对于状态 $(i,j,k)$ ，它是否被选只取决于三个图上三个点 SG 的异或值。

可以发现，SG 值是不超过 $O(\sqrt m)$ 的，因此只需要枚举两个图上选择点的 SG 值，第三个图上就是 $x \oplus y$ ，然后就可以统计相加的值的和了。

复杂度 $O(n + m)$ 。

垃圾做法：我们可以发现每张图上的选点是按独立集分层的，也就是说每次选出贪心的最大独立集，删掉它，做同样的事情，每次选点会把一个独立集整体拿走，而且这样的层数应该是不超过 $O(\sqrt m)$ 的。我们可以给所有的层按最大点排序，然后依次考虑每个层，它可以贪心和之前没有匹配过的成对的独立集匹配，可以拿 set 维护这样的独立集对。最后需要合并的独立集组不多，我们可以对每个组都把小的合并到大的，合并的时候较小就暴力，较大就 NTT 。复杂度我也算不明白，我猜是个 $O(m\sqrt m \log n)$ 之类的东西。难写+卡常，还是题解做法牛逼。

zjk 说这个题解做法可以通过观察完全图的选点猜到和异或有关，可惜我整不太明白。

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
// #pragma GCC optimize(2)
typedef long long ll;
const int MAXN = 2e6 + 10;
const int P = 998244353;
int n , m[3] , p18[MAXN];

int Pow( int x , int a ) {
    int ret = 1;
    while( a ) {
        if( a & 1 ) ret = ret * 1ll * x % P;
        x = x * 1ll * x % P , a >>= 1;
    }
    return ret;
}

vi G[3][MAXN];
vi lev[3][MAXN];
int cov[3][MAXN] , cr , cn , tl[3];
void gen( int idx , vi& res ) {
    // rep( i , 1 , n ) cov[i] = 0;
    ++ cr;
    per( i , n , 1 ) if( !cov[idx][i] ) {
        int flg = 0;
        for( int v : G[idx][i] ) if( cov[idx][v] == cr ) {
            flg = 1; break;
        }
        if( !flg ) cov[idx][i] = cr , res.pb( i ) , ++ cn;
    }
}

int tr[MAXN];
int ans = 0;
vector<pii> merge( const vector<pii>& a , const vector<pii>& b ) {
    vector<pii> ret;
    if( a.size() * b.size() <= 5000000 ) {
        // cout << "S" << endl;
        for( auto& x : a ) for( auto& y : b )
            tr[x.fi + y.fi] = ( tr[x.fi + y.fi] + x.se * 1ll * y.se ) % P;
        for( auto& x : a ) for( auto& y : b ) if( tr[x.fi + y.fi] )
            ret.eb( x.fi + y.fi , tr[x.fi + y.fi] ) , tr[x.fi + y.fi] = 0;
    } else {
        // cout << "H" << endl;
        // cout << a.size() << ' ' << b.size() << endl;
        vi ta( 3 * n + 1 ) , tb( 3 * n + 1 );
        for( auto x : a ) ta[x.fi] = ( ta[x.fi] + x.se ) % P;
        for( auto y : b ) tb[y.fi] = ( tb[y.fi] + y.se ) % P;
        vi tr = atcoder::convolution( ta , tb );
        rep( i , 1 , tr.size() - 1 ) {
            if( tr[i] )
                ret.eb( i , tr[i] );
        }
    }
    return ret;
}
vector<pii> merge( const vector<int>& a , const vector<int>& b ) {
    vector<pii> sa , sb;
    for( auto x : a ) sa.eb( x , 1 );
    for( auto x : b ) sb.eb( x , 1 );
    return merge( sa , sb );
}

vector<pair<int,vector<int>>> vec;

struct tcur {
    int a , b;
    bool operator < ( const tcur& t ) const {
        if( vec[a].se.back() + vec[b].se.back() == vec[t.a].se.back() + vec[t.b].se.back() )
            return a == t.a ? b < t.b : a < t.a;
        return vec[a].se.back() + vec[b].se.back() > vec[t.a].se.back() + vec[t.b].se.back();
    }
};

int vis[MAXN] , ddx[MAXN];
vector<pii> ps[MAXN];

void solve() {
    cin >> n;
    p18[0] = 1;
    p18[1] = ( (ll) 1e18 ) % P;
    rep( i , 1 , 3 * n ) p18[i] = p18[i - 1] * 1ll * p18[1] % P;
    rep( i , 0 , 2 ) {
        scanf("%d",m + i);
        rep( j , 1 , m[i] ) {
            int u , v;
            scanf("%d%d",&u,&v);
            G[i][u].pb( v ) , G[i][v].pb( u );
        }
        cn = 0 , tl[i] = 0;
        while( cn < n ) {
            ++ tl[i];
            gen( i , lev[i][tl[i]] );
            sort( all( lev[i][tl[i]] ) );
        }
    }
    int idx[3]; mem( idx );
    while( idx[0] < tl[0] || idx[1] < tl[1] || idx[2] < tl[2] ) {
        auto mx = mp( -1 , vector<int>( 1 ) );
        rep( k , 0 , 2 ) if( tl[k] > idx[k] && lev[k][idx[k] + 1].back() > mx.se.back() )
            mx = mp( k , lev[k][idx[k] + 1] );
        ++ idx[mx.fi];
        vec.pb( mx );
    }
    // for( auto& t : vec ) cout << t.se.size() << ' '; puts("");
    set<tcur> Q[4];
    int pt = 0;
    for( int i = 0 ; i < vec.size() ; ++ i ) {
        int dx = vec[i].fi;
        vector<set<tcur>::iterator> vit;
        for( auto it = Q[dx].begin() ; it != Q[dx].end() ; ++ it ) {
            if( vis[it -> a] != i + 1 && vis[it -> b] != i + 1 ) {
                if( vec[i].se.size() > vec[it -> a].se.size() && vec[i].se.size() > vec[it -> b].se.size() ) {
                    ps[i].eb( it -> a , it -> b );
                } else if( vec[i].se.size() < vec[it -> a].se.size() && vec[it -> a].se.size() > vec[it -> b].se.size() ) {
                    ps[it -> a].eb( i , it -> b );
                } else {
                    ps[it -> b].eb( i , it -> a );
                }
                vis[it -> a] = vis[it -> b] = i + 1;
                vit.pb( it );
            }
        }
        // add( s1 , s2 , vec[i].se );
        for( auto it : vit ) Q[dx].erase( it );
        rep( j , 0 , i - 1 ) if( vis[j] != i + 1 && vec[j].fi != dx ) {
            Q[3 - vec[j].fi - dx].insert( (tcur) { j , i } );
            // for( auto& t : Q[3 - vec[j].fi - dx] ) 
            //     cout << t.a << ' ' << t.b << endl;
        }
    }
    rep( i , 0 , vec.size() - 1 ) ddx[i] = i;
    sort( ddx , ddx + vec.size() , [&]( int a , int b ) { return vec[a].se.size() < vec[b].se.size(); } );
    rep( ti , 0 , vec.size() - 1 ) {
        int i = ddx[ti];
        vector<pii> d , s;
        for( int x : vec[i].se ) d.eb( x , 1 );
        for( auto t : ps[i] ) {
            // cout << vec[i].se[0] << ' ' << vec[t.fi].se[0] << ' ' << vec[t.se].se[0] << endl;
            auto v = merge( vec[t.fi].se , vec[t.se].se );
            s.insert( s.end() , v.begin() , v.end() );
        }
        vector<pii> ec = merge( d , s );
        for( auto& x : ec )
            ans = ( ans + p18[x.fi] * 1ll * x.se ) % P;
    }
    // cout << pt << endl;
    cout << ans << endl;
}

signed main() {
	//  freopen("in","r",stdin);
	// freopen("out","w",stdout);
	// int T;cin >> T;while( T-- ) solve();
	solve();
}