Problem C: Disarmament of the Units

This is a story in a country far away. In this country, two armed groups, ACM and ICPC, have fought in the civil war for many years. However, today October 21, reconciliation was approved between them; they have marked a turning point in their histories.

In this country, there are a number of roads either horizontal or vertical, and a town is built on every endpoint and every intersection of those roads (although only one town is built at each place). Some towns have units of either ACM or ICPC. These units have become unneeded by the reconciliation. So, we should make them disarm in a verifiable way simultaneously. All disarmament must be carried out at the towns designated for each group, and only one unit can be disarmed at each town. Therefore, we need to move the units.

The command of this mission is entrusted to you. You can have only one unit moved by a single order, where the unit must move to another town directly connected by a single road. You cannot make the next order to any unit until movement of the unit is completed. The unit cannot pass nor stay at any town another unit stays at. In addition, even though reconciliation was approved, members of those units are still irritable enough to start battles. For these reasons, two units belonging to different groups may not stay at towns on the same road. You further have to order to the two groups alternatively, because ordering only to one group may cause their dissatisfaction. In spite of this restriction, you can order to either group first.

Your job is to write a program to find the minimum number of orders required to complete the mission of disarmament.

Input

The input consists of multiple datasets. Each dataset has the following format:

n mA mI
rx1,1 ry1,1 rx1,2 ry1,2
...
rxn,1 ryn,1 rxn,2 ryn,2
sxA,1 syA,1
...
sxA,mA syA,mA
sxI,1 syI,1
...
sxI,mI syI,mI
txA,1 tyA,1
...
txA,mA tyA,mA
txI,1 tyI,1
...
txI,mI tyI,mI

n is the number of roads. m_A and m_I are the number of units in ACM and ICPC respectively (m_A > 0, m_I > 0, m_A + m_B < 8). (rx_i,1, ry_i,1 ) and (rx_i,2, ry_i,2 ) indicate the two endpoints of the i-th road, which is always parallel to either x-axis or y-axis. A series of (sx_A,i, sy_A,i ) indicates the coordinates of the towns where the ACM units initially stay, and a series of (sx_I,i, sy_I,i ) indicates where the ICPC units initially stay. A series of (tx_A,i, ty_A,i ) indicates the coordinates of the towns where the ACM units can be disarmed, and a series of (tx_I,i , ty_I,i ) indicates where the ICPC units can be disarmed.

You may assume the following:

• the number of towns, that is, the total number of coordinates where endpoints and/or intersections of the roads exist does not exceed 18;
• no two horizontal roads are connected nor ovarlapped; no two vertical roads, either;
• all the towns are connected by roads; and
• no pair of ACM and ICPC units initially stay in the towns on the same road.

The input is terminated by a line with triple zeros, which should not be processed.

Output

For each dataset, print the minimum required number of orders in a line. It is guaranteed that there is at least one way to complete the mission.

Sample Input

5 1 1
0 0 2 0
1 1 2 1
1 2 3 2
1 0 1 2
2 0 2 2
0 0
3 2
2 1
1 2
2 1 1
1 0 1 2
0 1 2 1
1 0
0 1
1 0
2 1
2 1 1
1 0 1 2
0 1 2 1
1 0
0 1
1 2
2 1
4 1 1
0 0 2 0
1 1 3 1
1 0 1 1
2 0 2 1
0 0
3 1
1 0
2 1
5 1 1
0 0 2 0
1 1 2 1
1 2 3 2
1 0 1 2
2 0 2 2
0 0
3 2
3 2
0 0
8 3 3
1 1 3 1
0 2 4 2
1 3 5 3
2 4 4 4
1 1 1 3
2 0 2 4
3 1 3 5
4 2 4 4
0 2
1 1
2 0
3 5
4 4
5 3
3 5
4 4
5 3
0 2
1 1
2 0
0 0 0

Output for the Sample Input

3
1
2
2
7
18

---