Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
E. Network Editing
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The company Sistemas Brasileiros de Conectividade (SBC) manages a network formed by $$$N$$$ stations, numbered from $$$1$$$ to $$$N$$$. Each connection in the network is a dedicated link formed by two terminals, one at each connected station. Connections are bidirectional, and there is at most one connection between each pair of distinct stations.

To modernize its infrastructure, SBC has prepared a desired configuration for the network. For cost reasons, during the reconfiguration the company neither buys nor discards terminals, but reuses the existing links. Furthermore, its field team is small and can only relocate one terminal per intervention.

In each intervention, the team chooses a connection between two stations $$$u$$$ and $$$v$$$, keeps one of the terminals at station $$$v$$$, and moves the other terminal from station $$$u$$$ to a station $$$w$$$. As a result, the connection between $$$u$$$ and $$$v$$$ is removed and a connection between $$$v$$$ and $$$w$$$ is installed. Stations $$$u$$$, $$$v$$$, and $$$w$$$ must be distinct, and the connection between $$$v$$$ and $$$w$$$ must not exist before the intervention.

Given the current and desired configurations of the network, determine the minimum number of interventions needed to transform the first into the second, or report that this transformation is impossible.

Input

The first line contains three integers $$$N$$$, $$$M_1$$$, and $$$M_2$$$ ($$$2 \leq N \leq 500$$$, $$$0 \leq M_1, M_2 \leq 500$$$), representing the number of stations, the number of connections in the current configuration, and the number of connections in the desired configuration, respectively.

Each of the following $$$M_1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq N$$$, $$$a \neq b$$$), indicating that there is a connection between stations $$$a$$$ and $$$b$$$ in the current configuration.

Each of the following $$$M_2$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a,b \leq N$$$, $$$a \neq b$$$), indicating that there is a connection between stations $$$a$$$ and $$$b$$$ in the desired configuration.

In each configuration, each pair of stations appears in at most one line.

Output

Print a single line containing an integer corresponding to the minimum number of interventions needed to obtain the desired configuration, or $$$-1$$$ if this is impossible.

Examples
Input
5 2 2
1 2
2 3
1 3
4 5
Output
3
Input
4 1 2
1 2
1 3
2 4
Output
-1
Input
4 5 5
1 2
1 3
1 4
2 3
2 4
1 3
1 4
2 3
2 4
3 4
Output
2
Note

Explanation for example 1

An optimal sequence consists of replacing, in this order, connection $$$1$$$–$$$2$$$ with $$$1$$$–$$$3$$$, connection $$$2$$$–$$$3$$$ with $$$2$$$–$$$4$$$, and connection $$$2$$$–$$$4$$$ with $$$4$$$–$$$5$$$.

It is not possible to use only two interventions, since the connection between $$$4$$$ and $$$5$$$ does not share a station with any of the connections in the initial configuration.

Explanation for example 3

First, the connection between $$$1$$$ and $$$3$$$ can be removed and the connection between $$$3$$$ and $$$4$$$ installed. Then, the connection between $$$1$$$ and $$$2$$$ is removed and the connection between $$$1$$$ and $$$3$$$ is reinstalled.

A single intervention is not enough, since the only connections that differ between the configurations, $$$1$$$–$$$2$$$ and $$$3$$$–$$$4$$$, do not share any station.