Background

Please note: This problem is an advanced version of CCO 2022 J4 Good Groups.

Admin note: It seems there is no enhancement.

Problem Description

A class will be divided into $g$ groups, with three students in each group. This grouping may violate two kinds of rules:

1. Some students must be in the same group.
2. Some students must not be in the same group.

Now the principal asks you how many rules are violated by the students.

Input Format

The first line contains an integer $x$.

The next $x$ lines each contain two student names $name1_1, name1_2$, meaning these two students must be assigned to the same group.

Then there is an integer $y$.

The next $y$ lines each contain two student names $name2_1, name2_2$, meaning these two students must not be in the same group.

Then there is an integer $g$.

The next $g$ lines each contain three student names $name3_1, name3_2, name3_3$, meaning these three students are currently in the same group.

Output Format

Output one integer, the number of rules violated by the students.

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

0

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

3

Hint

Explanation for Sample 2:

1. $\rm A$ and $\rm B$ must be in the same group, and this rule is violated.
2. $\rm G$ and $\rm L$ must be in the same group, and this rule is violated.
3. $\rm J$ and $\rm K$ must be in the same group, and this rule is not violated.
4. $\rm D$ and $\rm F$ must not be in the same group, and this rule is violated.
5. $\rm D$ and $\rm G$ must not be in the same group, and this rule is not violated.

Among these $5$ rules, $3$ are violated, so the output is $3$.

For $20\%$ of the testdata: $1 \le g \le 50$, $1 \le x \le 50$, $y = 0$.

For another $35\%$ of the testdata: $1 \le g \le 50$, $1 \le x \le 50$, $1 \le y \le 50$.

For $100\%$ of the testdata: $1 \le g \le 10^5$, $1 \le x \le 10^5$, $1 \le y \le 10^5$.

Translated by ChatGPT 5