Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ROUBMG14 - Rouba Bandeira

Um grupo de N crianças decidiu brincar de rouba bandeira. Para isso, elas precisam se separar em dois times com a mesma quantidade de crianças. Porém, algumas delas são muito amigas e querem estar no mesmo time. Por outro lado, outras são inimigas e não querem estar no mesmo time. Determine o número de formas de dividir os times satisfazendo todas essas restrições. Duas formas de dividir as crianças em times são consideradas diferentes se e somente se existe um par de crianças que são companheiras em uma das formas e adversárias na outra. Como a resposta pode ser muito grande, calcule-a mod 1.000.000.007.

Entrada

Há múltiplos casos de teste.

A primeira linha de cada caso de teste contém três inteiros N, A e I (1 ≤ N ≤ 1000, 0 ≤ A, I ≤ (n·(n-1))/2), onde N é o número de crianças, A é o número de relações de amizade e I é o número de relações de inimizade. A seguir, A linhas descrevem as relações de amizade e I linhas descrevem as relações de inimizade. Uma relação de amizade/inimizade é representada por um par de inteiros (p, q), tal que 1 ≤ p, q ≤ N, indicando que a relação existe entre as crianças p e q.

A entrada termina quando N=A=I=0.

Saída

Para cada caso de teste, imprima uma linha contendo um único inteiro que representa o número de formas de dividir os times mod (109 + 7).

Exemplos

Entrada:
2 0 0
4 0 0
4 1 2
1 2
1 3
2 4
3 0 0
0 0 0

Saída:
1
3
1
0

Adicionado por:Wanderley Guimarăes
Data:2014-07-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.