Good Groups

Interview

Time limit1sMemory limit1024 MB

Summary

Given same-group and separate-group constraints plus the actual groups of three, count how many constraints the grouping violates.

Level: Medium4 of 10
Topics: Hash map, Implementation, String, Array
Solved: No attempts yet

Problem

A class has been divided into groups of three. This division into groups might violate two types of constraints: some students must work together in the same group, and some students must work in separate groups.

Determine how many of the constraints are violated.

Input

The first line contains an integer $X$ ( $X \ge 0$ ). The next $X$ lines each consist of two different names, separated by a single space. These two students must be in the same group.

The next line contains an integer $Y$ ( $Y \ge 0$ ). The next $Y$ lines each consist of two different names, separated by a single space. These two students must not be in the same group.

Among these $X + Y$ lines representing constraints, each possible pair of students appears at most once.

The next line contains an integer $G$ ( $G \ge 1$ ). The last $G$ lines each consist of three different names, separated by single spaces. These three students have been placed in the same group.

Each name consists of between 1 and 10 uppercase letters. No two students have the same name, and each name appearing in a constraint appears in exactly one of the $G$ groups.

Output

Output an integer between $0$ and $X + Y$ , the number of constraints that are violated.

Examples2

Example 1

Input

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

Expected output

Example 2

Input

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

Expected output