20693번 - Writing Tasks 다국어

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$^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$^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 author cannot write more than one task about the same topic.

Additionally, each contest also has a syllabus. The $j$^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 \le A, C, T \le 50 000$) representing the number of task authors, contests, and topics, respectively.

The next $A$ lines each begins with an integer: $|L_i|$ ($0 \le |L_i| \le 2$) representing the number of contests that the $i$^th task author likes, followed by $|L_i|$ integers: $L_i[x]$ ($1 \le L_i[x] \le C$) representing the liked contests. It is guaranteed that the values in $L_i$ are distinct. It is also guaranteed that for all $1 \le j \le 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 \le |F_i| \le 2$) representing the number of topics that the $i$^th task author is familiar with, followed by $|F_i|$ integers: $F_i[y]$ ($1 \le F_i[y] \le T$) representing the familiarized topics. It is guaranteed that the values in $F_i$ are distinct. It is also guaranteed that for all $1 \le k \le 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 \le |S_j| \le 2$) representing the number of topics in the $j$^th contest syllabus, followed by $|S_j|$ integers: $S_j[z]$ ($1 \le S_j[z] \le 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 \le k \le 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.