시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
6 초 | 1024 MB | 18 | 6 | 4 | 33.333% |
You are given integers $A,B$, and a simple undirected graph of $N$ vertices and $M$ edges. The vertices are numbered from $1$ through $N$, and the edges from $1$ through $M$. The edge $i$ connects the vertices $U_i$ and $V_i$. Here, it is guaranteed that $V_i-U_i=A$ or $V_i-U_i=B$.
Find the number of matchings of the graph, modulo $998244353$. Note that a matching of the graph is a subset of edges whose end-points are all distinct.
The first line contains integers $N$ ($3 \leq N \leq 200$), $M$ ($1 \leq M \leq 400$), $A$, and $B$ ($1 \leq A < B \leq N-1$).
The following $M$ lines describe the edges. The $i$-th of those lines contains integers $U_i$ and $V_i$ ($1 \leq U_i < V_i \leq N$, $V_i-U_i=A$ or $V_i-U_i=B$). There are no self-loops or multi-edges.
Print the answer.
4 3 1 2 1 2 1 3 3 4
5
10 14 2 4 5 7 7 9 2 6 6 8 1 5 3 7 4 8 1 3 4 6 8 10 3 5 5 9 2 4 6 10
225