Edição de Rede

A empresa Sistemas Brasileiros de Conectividade (SBC) administra uma rede formada por $N$ estações, numeradas de $1$ a $N$. Cada conexão da rede é um enlace dedicado formado por dois terminais, um em cada estação conectada. As conexões são bidirecionais, e existe no máximo uma conexão entre cada par de estações distintas.

Para modernizar sua infraestrutura, a SBC preparou uma configuração desejada para a rede. Por questões de custo, durante a reconfiguração a empresa não compra nem descarta terminais, mas reaproveita os enlaces existentes. Além disso, sua equipe de campo é pequena e consegue remanejar apenas um terminal por intervenção.

Em cada intervenção, a equipe escolhe uma conexão entre duas estações $u$ e $v$, mantém um dos terminais na estação $v$ e transporta o outro terminal da estação $u$ para uma estação $w$. Dessa forma, a conexão entre $u$ e $v$ é removida e uma conexão entre $v$ e $w$ é instalada. As estações $u$, $v$ e $w$ devem ser distintas, e a conexão entre $v$ e $w$ não pode existir antes da intervenção.

Dadas as configurações atual e desejada da rede, determine o número mínimo de intervenções necessárias para transformar a primeira na segunda, ou informe que essa transformação é impossível.

Entrada

A primeira linha contém três inteiros $N$, $M_1$ e $M_2$ ($2 \leq N \leq 500$, $0 \leq M_1, M_2 \leq 500$), representando o número de estações, o número de conexões na configuração atual e o número de conexões na configuração desejada, respectivamente.

Cada uma das próximas $M_1$ linhas contém dois inteiros $a$ e $b$ ($1 \leq a,b \leq N$, $a \neq b$), indicando que existe uma conexão entre as estações $a$ e $b$ na configuração atual.

Cada uma das próximas $M_2$ linhas contém dois inteiros $a$ e $b$ ($1 \leq a,b \leq N$, $a \neq b$), indicando que existe uma conexão entre as estações $a$ e $b$ na configuração desejada.

Em cada configuração, cada par de estações aparece em no máximo uma linha.

Saída

Imprima uma única linha contendo um inteiro correspondente ao número mínimo de intervenções necessárias para obter a configuração desejada, ou $-1$ se isso for impossível.

5 2 2
1 2
2 3
1 3
4 5

3

4 1 2
1 2
1 3
2 4

-1

4 5 5
1 2
1 3
1 4
2 3
2 4
1 3
1 4
2 3
2 4
3 4

2