간선 부분집합

시간 제한6초메모리 제한1024 MB

요약

정점이 최대 200개인 그래프에서 간선의 차이가 A 또는 B인 조건으로 매칭의 개수를 998244353으로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산
정답자: 아직 제출이 없습니다

문제

정수 $A$ , $B$ 와 정점 $N$ 개, 간선 $M$ 개로 이루어진 단순 무방향 그래프가 주어진다. 정점은 1부터 $N$ 까지, 간선은 1부터 $M$ 까지 번호가 매겨져 있다. 간선 $i$ 는 정점 $U_i$ 와 $V_i$ 를 잇는다. 여기서 $V_i-U_i=A$ 또는 $V_i-U_i=B$ 임이 보장된다.

그래프의 매칭 개수를 $998244353$ 으로 나눈 나머지를 구하라. 매칭은 끝점이 모두 서로 다른 간선들의 부분집합이다.

입력

첫 줄에 정수 $N$ ( $3 \leq N \leq 200$ ), $M$ ( $1 \leq M \leq 400$ ), $A$ , $B$ ( $1 \leq A < B \leq N-1$ )가 주어진다.

다음 $M$ 개의 줄에 간선이 주어진다. $i$ 번째 줄에는 정수 $U_i$ 와 $V_i$ ( $1 \leq U_i < V_i \leq N$ , $V_i-U_i=A$ 또는 $V_i-U_i=B$ )가 주어진다. 자기 루프와 중복 간선은 없다.

출력

답을 출력한다.

예제2

예제 1
입력
```
4 3 1 2
1 2
1 3
3 4
```
예상 출력
```
5
```

예제 2

입력

예상 출력