The Matrix can be regarded as an enormous connected weighted graph. To describe the Matrix, you are given. ). The graphs will not contain self loops or duplicate edges. The Matrix is the graph. ) in the Matrix, there is an edge between the vertices if and only if there exists an. i will be unique. The weight of the edge will be the weight of the edge. You are required to output weight of the minimum spanning tree of. (V,E). As the weight could be very large, you are only required to output modulo
The Matrix can be regarded as an enormous connected weighted graph. To describe the Matrix, you are given k k connected weighted graphs (V_1,E_1),(V_2,E_2), ldots, (V_k,E_k) (V 1 ,E 1 ),(V 2 ,E 2 ),…,(V k ,E k ). The graphs will not contain self loops or duplicate edges. The Matrix is the graph (V,E) (V,E) where V = V_1 times V_2 times ldots times V_k V=V 1 ×V 2 ×…×V k . That is, any vertex in V V can be described as a tuple (v_1,v_2,ldots,v_k) (v 1 ,v 2 ,…,v k ) where v_i in V_i v i ∈V i for i in {1,2,ldots,k} i∈{1,2,…,k}. For two vertices (v_1,v_2,ldots,v_k) (v 1 ,v 2 ,…,v k ) and (v'_1,v'_2,ldots,v'_k) (v 1 ′ ,v 2 ′ ,…,v k ′ ) in the Matrix, there is an edge between the vertices if and only if there exists an i i such that (v_i,v'_i) (v i ,v i ′ ) is in E_i E i and for all j in {1,2,ldots,n}backslash{i} j∈{1,2,…,n}{i} we have that v_j = v'_j v j =v j ′ . As there is no self loops in the k k graphs it is obvious that such i i will be unique. The weight of the edge will be the weight of the edge (v_i,v'_i) (v i ,v i ′ ) is in E_i E i . You are required to output weight of the minimum spanning tree of (V,E) (V,E). As the weight could be very large, you are only required to output modulo 998,244,353 998,244,353.
