Some of the roads in a state have been damaged due to recent flood. Your task is to repair just enough roads such that each city in the state is connected to every other city. You are given the list of functional roads and damaged roads. Each input line will contain the id of the road and two city which it connects. The roads are bidirectional.
Input Format
The first line contains an integer , denoting the number of cities.
The second line contains an integer , denoting the number of functional roads.
The next lines contains two integers describing the endpoints (u, v) of each road.
The m + 2 line contains an integer , denoting the number of damaged roads.
The next lines contains two integers describing the endpoints (u, v) of each road.
Constraints
-
It is guaranteed that roads are different in the input.
Output Format
If answer doesn't exist, print -1.
Otherwise, print the minimum numbers of reconstructed roads such that every two cities connect to each other.
Sample Input 0
4
2
1 2
2 3
2
3 4
1 4
Sample Output 0
1
Explanation 0
In this example, city 1, 2 and 3 are connected to each other by the functional roads and we can reach city 4 by repairing any one of the damaged roads.
Sample Input 1
5
0
5
3 5
3 4
1 2
1 3
1 1
Sample Output 1
4
Explanation 1
In this example, there are no functional roads. We repair all the damaged roads except the last one which connects city 1 to itself.