11266: [yosupo] Graph - Counting Eulerian Circuits
[Creator : ]
Description
You are given a directed graph $G$, consisting of $N$ vertices and $M$ edges. The $i$-th edge is directed from $u_i$ to $v_i$.
An eulerian circuit of $G$ is a pair of sequence of vertices $(v_0,\ldots,v_{M-1})$ and sequence of edges $(e_0,\ldots,e_{M-1})$ satisfying following conditions.
- $(e_0,\ldots,e_{M-1})$ is a permutation of $(0, \ldots, M-1)$.
- For $0\leq i < M-1$, the edge $e_i$ is directed from $v_i$ to $v_{i+1}$. The edge $e_{M-1}$ is directed from $v_{M-1}$ to $v_0$.
Note that an Eulerian circuit remains an Eulerian circuit after any cyclic shift.
Find the number of Eulerian circuits of $G$, considered the same if they can be obtained from one another by a cyclic shift (in other words, the number of Eulerian circuits with $e_0 = 0$), and give the result modulo $998244353$.
An eulerian circuit of $G$ is a pair of sequence of vertices $(v_0,\ldots,v_{M-1})$ and sequence of edges $(e_0,\ldots,e_{M-1})$ satisfying following conditions.
- $(e_0,\ldots,e_{M-1})$ is a permutation of $(0, \ldots, M-1)$.
- For $0\leq i < M-1$, the edge $e_i$ is directed from $v_i$ to $v_{i+1}$. The edge $e_{M-1}$ is directed from $v_{M-1}$ to $v_0$.
Note that an Eulerian circuit remains an Eulerian circuit after any cyclic shift.
Find the number of Eulerian circuits of $G$, considered the same if they can be obtained from one another by a cyclic shift (in other words, the number of Eulerian circuits with $e_0 = 0$), and give the result modulo $998244353$.
Input
$N$ $M$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
$u_0$ $v_0$
$\vdots$
$u_{M-1}$ $v_{M-1}$
Constraints
- $1 \leq N \leq 500$
- $1 \leq M \leq 2\times 10^5$
- $0 \leq u_i, v_i \lt N$
- $1 \leq M \leq 2\times 10^5$
- $0 \leq u_i, v_i \lt N$
Sample 1 Input
3 6
0 1
0 1
1 2
1 2
2 0
2 0
Sample 1 Output
4
Sample 2 Input
4 10
0 1
0 2
1 0
1 3
1 3
2 1
2 3
3 0
3 1
3 2
Sample 2 Output
36
Sample 3 Input
10 4
0 0
0 0
0 0
0 0
Sample 3 Output
6
3 2
0 1
1 2
0