마피아

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

요약

경찰관 사이의 정직 또는 부패 고발이 주어질 때, 각 질의 C에 대해 모든 고발과 모순되지 않는 크기 C의 부패 경찰관 집합의 수를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, 유니온 파인드, 조합론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

도시 <insert name here>에 마피아가 침투했다. 이 때문에 <insert name here> 경찰은 극도로 혼란에 빠졌고, 사방에서 부패 의혹이 제기되고 있다. 도시의 경찰관 $N$ 명(번호는 $0$ 부터 $N - 1$ 까지)이 다른 경찰관들에 대해 여러 가지 고발을 했다. 각 고발은 다음 둘 중 하나다.

경찰관 $i$ 는 정직한 경찰이다.
경찰관 $i$ 는 부패한 경찰이다.

정직한 경찰관은 항상 진실을 말하고, 부패한 경찰관은 항상 거짓을 말한다. 지금까지 고발은 모두 $M$ 건이다.

경찰청장은 상황을 바로잡기 위해, 우선 자신의 부하 중 부패한 경찰이 몇 명인지 알아내려 한다. 부패한 경찰의 수에 대해 서로 다른 추측이 $G$ 개 있고, 각 수 $C$ 에 대해 모든 고발이 일관성을 유지한다는 조건에서 크기가 $C$ 인 부패 집합(나머지 경찰은 모두 정직하다)이 몇 개나 될 수 있는지 알고 싶어 한다.

입력

채점기는 입력을 다음 형식으로 읽는다.

$1$ 번째 줄: N M
$2$ 번째 줄: A[0] ... A[M - 1]
$3$ 번째 줄: B[0] ... B[M - 1]
$4$ 번째 줄: T[0] ... T[M - 1]
$5$ 번째 줄: G: guess(C)를 호출한 횟수.
$6$ 번째 줄 C1 ... CG: $G$ 번의 guess(C) 호출의 매개변수.

출력

채점기는 guess(C)의 반환값을 $G$ 줄에 걸쳐 출력한다.

제한

$G$ 를 guess(C)를 호출한 횟수라고 하자.

$N \le 2\,000$
$M \le 70\,000$
$G \le 2\,000$

예제1

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