P6017 [CSGRound3] Cactus

ckw is a very weak newbie.

ckw has many edge-cactus graphs. An edge-cactus graph is a simple undirected connected graph in which each edge belongs to at most one simple cycle. ckw defines the degree sequence of an undirected graph. The length of the degree sequence is the number of vertices in the graph, and the $i$-th element of the degree sequence is the degree of the vertex numbered $i$. ckw wants to know: among all edge-cactus graphs with $n$ vertices and $m$ edges, how many different degree sequences are there. Output the answer modulo $998244353$. (If no valid cactus exists, output $0$.)

**This problem has multiple test cases.** The first line contains an integer $T$, the number of test cases. For each test case, one line contains two integers $n, m$, representing the number of vertices and the number of edges.

For each test case, output one integer per line, the answer modulo $998244353$.

**[Sample Explanation]** For the first test case, here are four valid degree sequences: $\{2,2,2,2\},\{1,2,2,3\},\{1,2,3,2\},\{2,1,3,2\}$. --- **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (8 points): $n \le 5$. - Subtask 2 (10 points): $n \le 10$. - Subtask 3 (18 points): $n \le 35$. - Subtask 4 (12 points): $n \le 90$. - Subtask 5 (8 points): $m = n - 1$. - Subtask 6 (10 points): $m = n$. - Subtask 7 (16 points): $m = n + 1$. - Subtask 8 (18 points): no special constraints. For $100\%$ of the testdata, $1 \le T \le 10$, $0 \le n \le 2 \times 10^3$, $0 \le m \le 10^9$. Translated by ChatGPT 5