题目描述

Given two connected graphs $G_1,G_2$. You should count the number of ways to delete $4$ edges from $G_1\square G_2$ such that $G_1\square G_2$ becomes disconnected, where $G_1\square G_2$ is the Cartesian product of $G_1$ and $G_2$ (See the next section for formal definitions). In graph theory, the Cartesian product $G \square H$ of graphs $G$ and $H$ is a graph such that: the vertex set of $G \square H$ is the Cartesian product $V(G) \times V(H)$; and two vertices $(u,v)$ and $(u',v')$ are adjacent in $G \square H$ if and only if either $u = u'$ and $v$ is adjacent to $v'$ in $H$, or $v = v'$ and $u$ is adjacent to $u'$ in $G$. Since the answer might be large, you should output the answer modulo $998\,244\,353$.官方中文

输入格式

The input consists of descriptions of the two graphs $G_1$ and $G_2$ sequentially.官方中文

For each graph, the first line contains two integers $n,m$ $(5\leq n\leq 2\cdot 10^5, n-1\leq m\leq 2\cdot 10^5)$, denoting the number of vertices and edges in the graph, followed by $m$ lines, with each line containing two integers $u,v$ $(1\leq u,v\leq n)$, denoting an edge in the graph.官方中文

It is guaranteed that both graphs are connected, and have no self-loop or multiple edges.官方中文

输出格式

Output an integer in a line, denoting the number of ways to delete $4$ edges to disconnect the graph $G_1\square G_2$, taken modulo $998\,244\,353$.官方中文

说明