#agc043c. [agc043_c]Giant Graph

[agc043_c]Giant Graph

给定三个简单无向图G1,G2,G3G_1,G_2,G_3,其中每个图的点数均为nn,边数分别为m1,m2,m3m_1,m_2,m_3

现在根据G1,G2,G3G_1,G_2,G_3构造一个新的无向图GGGGn3n^3个点,每个点可以表示为(x,y,z)(x,y,z),对应G1G_1中的点xxG2G_2中的点yyG3G_3中的点zz。边集的构造方式如下:

G1G_1中存在一条边(u,v)(u,v),则对于任意1a,bn1\le a, b\le n,在GG中添加边((u,a,b),(v,a,b))((u,a,b),(v,a,b))

G2G_2中存在一条边(u,v)(u,v),则对于任意1a,bn1\le a, b\le n,在GG中添加边((a,u,b),(a,v,b))((a,u,b),(a,v,b))

G3G_3中存在一条边(u,v)(u,v),则对于任意1a,bn1\le a, b\le n,在GG中添加边((a,b,u),(a,b,v))((a,b,u),(a,b,v)).

对于GG中的任意一个点(x,y,z)(x,y,z),定义其点权为1018(x+y+z)10^{18(x+y+z)}

试求GG的最大权独立集的大小模998244353998244353的值。

2n105,1m1,m2,m31052\le n\le 10^5, 1\le m_1,m_2,m_3\le 10^5

Translated by Caro23333