28a Olimpíada Brasileira de Informática
Submeta sua solução

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 ≤ E ≤ 999 999 e E é divisível por 3.
  • 0 ≤ M ≤ 100 000
  • 0 ≤ D ≤ 100 000
  • M + D > 0 e, entre todos os M + D pares, cada par de estudantes aparece no máximo uma vez.
  • 1 ≤ X ≤ E, 1 ≤ Y ≤ E e X &neq; Y.
  • 1 ≤ U ≤ E, 1 ≤ V ≤ E e U &neq; V.
  • 1 ≤ I ≤ E, 1 ≤ J ≤ E e 1 ≤ K ≤ 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 ≤ 999, M ≤ 1 000 e D ≤ 1 000.
  • Subtarefa 2 (61 pontos): Nenhuma restrição adicional.
Seu programa pode resolver corretamente ambas ou somente uma das subtarefas. Sua pontuação final na tarefa é a soma dos pontos das subtarefas resolvidas corretamente por alguma das suas submissões.

Exemplos

Entrada
3 1 0
1 2
2 1 3
Saída
0
	

 

Entrada
9 1 3
1 9
1 3
5 6
2 8
1 2 3
4 5 6
7 8 9
Saída
3
	

 

Entrada
6 0 3
1 5
5 2
2 3
5 2 1
3 4 6
Saída
2
	

 

PJ P1 P2 PS
Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação