9361: CCC '22 J4/S2 - Good Groups
[Creator : ]
Description
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.
Your job is to determine how many of the constraints are violated.
Your job is to determine how many of the constraints are violated.
Input
The first line will contain an integer $X$ with $X≥0$.
The next $X$ lines will each consist of two different names, separated by a single space. These two students must be in the same group.
The next line will contain an integer $Y$ with $Y≥0$.
The next $Y$ lines will 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 will contain an integer $G$ with $G≥1$.
The last $G$ lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.
Each name will consist of between 1 and 10 uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the $G$ groups.
The next $X$ lines will each consist of two different names, separated by a single space. These two students must be in the same group.
The next line will contain an integer $Y$ with $Y≥0$.
The next $Y$ lines will 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 will contain an integer $G$ with $G≥1$.
The last $G$ lines will each consist of three different names, separated by single spaces. These three students have been placed in the same group.
Each name will consist of between 1 and 10 uppercase letters. No two students will have the same name and each name appearing in a constraint will appear in exactly one of the $G$ groups.
Output
Output an integer between $0$ and $X+Y$ which is the number of constraints that are violated.
Constraints
$G \leq 100,000$
$X \leq 100,000$
$Y \leq 100,000$
$X \leq 100,000$
$Y \leq 100,000$
Sample 1 Input
1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE
Sample 1 Output
0
There is only one constraint and it is not violated: ELODIE and CHI are in the same group.
Sample 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
Sample 2 Output
3
The first constraint is that A and B must be in the same group. This is violated.
The second constraint is that G and L must be in the same group. This is violated.
The third constraint is that J and K must be in the same group. This is not violated.
The fourth constraint is that D and F must not be in the same group. This is violated.
The fifth constraint is that D and G must not be in the same group. This is not violated.
Of the five constraints, three are violated.
The second constraint is that G and L must be in the same group. This is violated.
The third constraint is that J and K must be in the same group. This is not violated.
The fourth constraint is that D and F must not be in the same group. This is violated.
The fifth constraint is that D and G must not be in the same group. This is not violated.
Of the five constraints, three are violated.