Maffia

En maffia har infiltrerat staden <sätt in namn här>. Det här har gjort polismakten i <sätt in namn här> väldigt förvirrad, med anklagelser om korruption slängda i alla riktningar. Stadens $N$ poliser (som är numrerade mellan $0$ och $N - 1$) har gjort ett antal anklagelser om andra poliser. Varje anklagelse är antingen:

1. Polis nummer $i$ är en ärlig polis.

2. Polis nummer $i$ är en korrupt polis.

En ärlig polis berättar alltid sanningen, medan en korrupt polis alltid ljuger. Totalt har $M$ anklagelser gjorts.

Polischefen försöker nu reda ut situationen, och tänker börja med att avgöra hur många av hennes poliser som är korrupta. Hon har $G$ olika gissningar om hur många av poliserna som är korrupta, och vill nu för varje gissning $C$ veta på hur många olika sätt exakt $C$ poliser kan vara korrupta, givet att alla anklagelser är konsistenta.

Exempel

Låt antalet poliser vara $N = 3$, med $M = 2$ anklagelser. Den första polisen anklagade den andra för att vara korrupt, och den andra polisen anklagade den tredje för att vara korrupt. Det finns nu två fall. Antingen är den andra polisen korrupt eller inte.

Om den andra polisen är korrupt så ljuger hen (så den tredje polisen är ärlig), och den första polisen ljuger inte (vilket betyder att även hen är ärlig).

Om den andra polisen är ärlig så måste den tredje polisen vara korrupt (eftersom den andra polisens anklagelse nu är sann), och den första polisens måste också vara korrupt (eftersom hans anklagelse om den andra polisen var en lögn).

Det finns således två möjliga mängder korrupta poliser: $\{ 1, 3\} $ och $\{ 2\} $, vilket betyder att det finns en delmängd av storlek 1 och en av storlek 2.

Uppgift

Din uppgift är att beräkna, för varje av polischefens gissningar $C$, på hur många sätt exakt $C$ poliser kan vara korrupta. Du ska implementera funktionerna cops(N, M, A, B, T) och guess(C).

• cops(N, M, A, B, T) - denna funktion anropas exakt en gång av domaren i början av programmet.

  • N: antalet poliser.

  • M: antalet anklagelser.

  • A: en array med $M$ element. A[i] ($0 \le i < N$) innehåller numret på den polis som gjorde den $i$:te anklagelsen.

  • B: en array med $M$ element. B[i] ($0 \le i < N$) innehåller numret på den polis som är målet för den $i$:te anklagelsen.

  • T: en array with $M$ elements. T[i] ($0 \le i < N$) innehåller 1 eller 2 om den $i$:te anklagelsen är av typ 1 eller 2, respektive.

  • Funktionen har inget returvärde.

• guess(C) - denna funktion anropas en gång för varje gissning.

  • C: ett tal mellan $0$ och $N$; polischefens gissning.

  • Returvärdet för $C$ kommer aldrig överstiga $10^{18}$.

  • Funktionen ska returnera antalet sätt som exakt $C$ poliser kan korrupta på.

Ett kodskelett som innehåller funktionerna du ska implementera, tillsammans med en exempeldomare, finns tillgängligt på http://progolymp.se/uploads/kattis-attachments/mafia.zip.

Delpoäng

Problemet består av flera grupper av testfall. Varje grupp ger ett visst antal poäng och för att klara det måste du klara alla testfall i gruppen.

Låt $G$ vara antalet anrop till guess(C).

Indataformat

Exempeldomaren läser indata i följande format:

• line $1$: N M

• line $2$: A[0] ... A[M - 1]

• line $3$: B[0] ... B[M - 1]

• line $4$: T[0] ... T[M - 1]

• line $5$: G: antalet anrop till guess(C).

• line $6$ C1 ... CG: parametrarna till de $G$ anropen till guess(C).

Utdataformat

Exempeldomaren skriver ut $G$ rader med returvärdena från guess(C).

3 2
1 2
0 1
2 2
4
0 1 2 3

0 1 1 0