题目描述

In $2020$, there are $C$ programming contests held in Indonesia, numbered from $1$ to $C$. Each contest has zero or more tasks written for the contest. There are $A$ task authors who can write tasks for these contests, numbered from $1$ to $A$. The $i^\text{th}$ task author only likes the set of contests $L_i \subseteq \{1, 2, \dots, C\}$, and only wants to write tasks for contests in $L_i$. Each task author cannot write more than one task for the same contest.

There are also $T$ topics in programming contest tasks, numbered from $1$ to $T$. For example, topic $1$ might be about graph tasks, topic $2$ might be about string tasks, and so on. Each task has exactly one topic. The $i^\text{th}$ task author is familiar with the set of topics $F_i \subseteq \{1, 2, \dots, T\}$, and only wants to write tasks about topics in $F_i$. Each task cannot write more than one task about the same topic.

Additionally, each contest also has a syllabus. The $j^\text{th}$ contest syllabus contains the set of topics $S_j \subseteq \{1, 2, \dots, T\}$, and the topic for the tasks written for the contest must be in $S_j$. Each contest cannot have more than one task for the same topic.

You are a programming contest enthusiast in Indonesia. Surprisingly, you observed the following:

• Each task author likes at most two contests. Similarly, each contest is liked by at most two task authors.
• Each task author is familiar with at most two topics. Similarly, each topic is familiarized by at most two task authors.
• Each contest has at most two topics in its syllabus. Similarly, each topic is present in at most two contest syllabuses.

You want to find the maximum total number of tasks that can be written across all contests.

输入格式

Input begins with a line containing three integers: $A\ C\ T$ ($1 \leq A, C, T \leq 50\,000$) representing the number of task authors, contests, and topics, respectively.

The next $A$ lines each begins with an integer: $|L_i|$ ($0 \leq |L_i| \leq 2$) representing the number of contests that the $i^\text{th}$ task author likes, followed by $|L_i|$ integers: $L_i[x]$ ($1 \leq L_i[x] \leq C$) representing the liked contests. It is guaranteed that the values in $L_i$ are distinct. It is also guaranteed that for all $1 \leq j \leq C$, the value $j$ only appears at most twice in $\bigcup_{i=1}^A L_i$.

The next $A$ lines each begins with an integer: $|F_i|$ ($0 \leq |F_i| \leq 2$) representing the number of topics that the $i^\text{th}$ task author is familiar with, followed by $|F_i|$ integers: $F_i[y]$ ($1 \leq F_i[y] \leq T$) representing the familiarized topics. It is guaranteed that the values in $F_i$ are distinct. It is also guaranteed that for all $1 \leq k \leq T$, the value $k$ only appears at most twice in $\bigcup_{i=1}^A F_i$.

The next $C$ lines each begins with an integer: $|S_j|$ ($0 \leq |S_j| \leq 2$) representing the number of topics in the $j^\text{th}$ contest syllabus, followed by $|S_j|$ integers: $S_j[z]$ ($1 \leq S_j[z] \leq T$) representing the topics in the syllabus. It is guaranteed that the values in $S_j$ are distinct. It is also guaranteed that for all $1 \leq k \leq T$, the value $k$ only appears at most twice in $\bigcup_{j=1}^C S_j$.

输出格式

Output in a line an integer representing the maximum total number of tasks that can be written across all contests.

2 3 2
2 1 2
2 2 3
1 1
1 1
1 1
1 1
1 2

2

提示

Explanation for the sample input/output #1

There are at most two tasks that can be written:

1. The $1^\text{st}$ task author writes a task about the $1^\text{st}$ topic for the $1^\text{st}$ contest.
2. The $2^\text{nd}$ task author writes a task about the $1^\text{st}$ topic for the $2^\text{nd}$ contest.

Note that the $1^\text{st}$ task author has written a task about the $1^\text{st}$ topic, thus they cannot write a task for the $2^\text{nd}$ contest about the same topic.

This example can be illustrated by the following figure, with $A_i$ represents the $i^\text{th}$ task author, $C_j$ represents the $j^\text{th}$ contest, $T_k$ represents the $k^\text{th}$ topic, thick lines represent the first task, and the dashed lines represent the second task.

:::align{center} :::