二部グラフマッチング問題 - Problem

二部グラフが与えられます。左側の部集合は 1 から $n_1$ までの番号がついた $n_1$ 個の頂点を含み、右側の部集合は 1 から $n_2$ までの番号がついた $n_2$ 個の頂点を含みます。$m$ 本の辺があり、各辺は左側の 1 つの頂点と右側の 1 つの頂点を結んでいます。

右側のすべての区間 $[l, r]$（ただし $1 \le l \le r \le n_2$）について、次のようにして得られる 부분グラフを考えます：

この部分グラフにおいて、最大マッチングのサイズ（互いに端点を共有しない辺の最大本数）を求め、この値を $f(l, r)$ と表します。

次の値を計算してください：

$$\sum_{1 \le l \le r \le n_2} f(l, r) \cdot l \cdot r \cdot ((l \oplus r) + 1),$$

ここで $\oplus$ はビットごとの排他的論理和（XOR）演算を表します。

この和を $998\,244\,353$ で割った余りを出力してください。

入力は複数のテストケースを含みます。

1 行目には、テストケースの個数を表す 1 つの整数 $T$ ($1 \le T \le 2000$) が与えられます。

各テストケースについて、1 行目には左側の頂点数、右側の頂点数、および辺の本数を表す 3 つの整数 $n_1, n_2, m$ ($1 \le n_1, n_2 \le 5000, 0 \le m \le 10^4$) が与えられます。

続く $m$ 行のそれぞれには、左側の頂点 $u$ と右側の頂点 $v$ の間に辺があることを表す 2 つの整数 $u, v$ ($1 \le u \le n_1, 1 \le v \le n_2$) が与えられます。

多重辺は存在せず、$n_1$ の総和および $n_2$ の総和はいずれも $5000$ を超えないことが保証されます。

各テストケースについて、求める和を $998\,244\,353$ で割った余りを表す 1 つの整数を 1 行に出力してください。

QOJ.ac