研究两个图(G1)和(G2)的乘积的连通块的性质（agc011c）
根据定义，两个点((a,b),(c,d))连通的条件：存在(a,b)和(c,d)之间长度为(x)的路径
考虑(G1)的每个连通块和(G2)每个连通块合并后结果：
有任一是孤立点：显然不会连出任何边。
两个非二分图：会发现在(x)足够大（大于两个图大小的最大值）时，奇，偶路径都存在，所以会合并成一个非二分图。
一个非二分图，一个二分图：在(x)足够大时只存在长为偶数的路径，所以会合并成一个二分图。
两个二分图：会合并成两个二分图。
所以我们只需要关心每个连通块是孤立点/非二分图/二分图。
考虑孤立点对答案的贡献。
假设(G_i)的孤立点的个数是(a_i)，则新图中有(prod m_i-prod a_i)个孤立点。
这是因为正难则反原理，只有两个非孤立点图合并起来才是孤立点图。
图(i)中一个点为孤立点的概率是其不向外面连任何边，是((1-(frac{1}{2})^{m_i-1})m_i)
这也是由于正难则反原理。
考虑两个非孤立点图，设二分图/所有连通块数量为((a_1,b_1),(a_2,b_2))，根据前面的分析，合并后二分图/所有连通块的数目是((a_1b_1+a_2b_2,a_1b_2+a_2b_1))
这长得很像fwt。
设((a_i,b_i))为一个图的二分图/所有连通块数量。
所以我们只需要知道(a_i+b_i,a_i-b_i)的期望即可。
连通图的生成函数可以通过解方程得到，是经典问题。
设(F(x))表示所有图的生成函数，(G(x))表示连通图的生成函数。
则(F)是(G)的拼接，所以可以使用exp描述。
从(G)解出(F)可以多项式ln。
令(H(x)= sum_{i = 0}^{S} sum_{j = 0}^{i} frac{2^{j(i - j)}}{j!(i - j)!})
它的意义是：二分图的判定可以染色，可以枚举染色方法和连的边以生成二分图的拼接。
则借鉴之前从(G)解出(F)，可以用ln解(I)，(I(x)=ln(H(x)))
求(H(x))可以用卷积，用CZT拆解(j(i - j))即可。
时间复杂度(O(nlog_2n))