Grupos de Trabalho

A professora Paula divide a classe em grupos de três estudantes para os trabalhos da sua disciplina. Para minimizar descontentamentos, ela fez uma enquete no início do ano, de forma que ela tem uma lista de pares de estudantes que gostariam de estar no mesmo grupo, e uma lista de pares de estudantes que não gostariam de estar no mesmo grupo.

Para cada trabalho ela faz uma nova divisão de grupos, e claro que nem sempre vai ser possível satisfazer todas as restrições da classe!

Dados os pares de estudantes que gostariam estar no mesmo grupo, os pares de estudantes que não gostariam estar no mesmo grupo, e uma possível distribuição dos estudantes em grupos de três, sua tarefa é determinar o número total de restrições que são violadas com essa distribuição.

Entrada

A primeira linha contém três inteiros $E$ , $M$ e $D$ , indicando, respectivamente, o número total de estudantes, o número de pares de estudantes que gostariam de estar no mesmo grupo e o número de pares de estudantes que não gostariam de estar no mesmo grupo. Os estudantes são identificados por números inteiros de $1$ a $E$ .

Cada uma das $M$ linhas seguintes descreve um par de estudantes que gostariam de estar no mesmo grupo e contém dois inteiros $X$ e $Y$ indicando os estudantes do par. Cada uma das $D$ linhas seguintes descreve um par de estudantes que não gostariam de estar no mesmo grupo e contém dois inteiros $U$ e $V$ indicando os estudantes do par.

Finalmente, cada uma das $E/3$ linhas seguintes descreve um grupo de estudantes e contém três inteiros $I$ , $J$ e $K$ indicando os estudantes do grupo.

Saída

Seu programa deve produzir uma única linha, contendo um único inteiro, o número total de restrições que são violadas nos grupos da entrada.

Restrições

$3 \leq E \leq 999\ 999$ e $E$ é divisível por $3$ .
$0 \leq M \leq 100\ 000$
$0 \leq D \leq 100\ 000$
$M + D > 0$ e, entre todos os $M + D$ pares, cada par de estudantes aparece no máximo uma vez.
$1 \leq X \leq E, 1 \leq Y \leq E$ e $X\neq Y$
$1 \leq U \leq E, 1 \leq V \leq E$ e $U\neq V$
$1 \leq I \leq E, 1 \leq J \leq E$ e $1 \leq K \leq E$
Cada estudante aparece em exatamente um dos $E/3$ grupos.

Informações sobre a pontuação

A tarefa vale $100$ pontos. Estes pontos estão distribuídos em subtarefas, cada uma com suas restrições adicionais às definidas acima:

Subtarefa 1 (39 pontos): $E \leq 999, M \leq 1\ 000$ e $D \leq 1\ 000$ .
Subtarefa 2 (61 pontos): Nenhuma restrição adicional.

Seu programa pode resolver corretamente todas ou algumas das subtarefas (elas não precisam ser resolvidas em ordem). Sua pontuação final na tarefa é a soma dos pontos de todas as subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Exemplo de entrada 1

3 1 0
1 2
2 1 3

Exemplo de saída 1

Explicação do exemplo 1: Há $3$ estudantes e apenas uma restrição (estudantes $1$ e $2$ gostariam de estar no mesmo grupo), que é obedecida no único grupo da distribuição, $(2,1,3)$ , portanto a resposta é $0$ .

Exemplo de entrada 2

Exemplo de saída 2

Explicação do exemplo 2: Há $9$ estudantes e portanto serão formados três grupos. Há $1$ par de estudantes que gostariam de estar no mesmo grupo: $(1,9)$ e três pares de estudantes que não gostariam estar no mesmo grupo: $(1,3)$ , $(5,6)$ e $(2,8)$ . Nos grupos formados – $(1,2,3)$ , $(4,5,6)$ e $(7,8,9)$ –, das quatro restrições apenas o par $(2,8)$ tem a restrição obedecida (pois não estão no mesmo grupo). Para os outros três pares, $(1,9)$ , $(1,3)$ e $(5,6)$ , as restrições são violadas, portanto a resposta é $3$ .

Exemplo de entrada 3

Exemplo de saída 3

Explicação do exemplo 3: Há $6$ estudantes e portanto serão formados dois grupos. Não há nenhum par de estudantes que gostariam de estar no mesmo grupo e há três pares de estudantes que não gostariam estar no mesmo grupo: $(1,5)$ , $(5,2)$ e $(2,3)$ . Nos grupos formados – $(5,2,1)$ e $(3,4,6)$ –, das três restrições, duas são violadas: $(1,5)$ e $(5,2)$ não gostariam de estar no mesmo grupo, e portanto a resposta é $2$ .