Background

Looking and looking for friends, finding a good friend. Salute and shake hands, you are my good friend.

Problem Description

Kindergarten is starting!

Before school starts, some kids will prepare a plush toy, which they can share with other kids.

Specifically, there are $t$ days. Each day’s seating plan can be represented as an undirected graph. Every day, each kid who has a plush toy will definitely choose one kid who sits with them on that day, and give the plush toy to that kid.

However, the teacher requires that everyone can have only one plush toy.

Here, we assume that every day everyone gives out their toy first, and then receives from others.

Ask: at the beginning, what is the maximum number of kids that can have a plush toy?

Note: This means that in a valid transfer process, it cannot happen that some kid cannot give out their plush toy, or that some kid ends up owning more than one plush toy. An initial configuration is valid if and only if there exists at least one valid transfer process.

Input Format

The first line contains two positive integers $t, n$, representing the number of days and the number of kids.

Then follow descriptions of $t$ graphs, representing the seating plan for each day:

The first line of each description is a positive integer $m$, representing the number of edges.

The next $m$ lines each contain two positive integers $u, v$, indicating that there is an undirected edge $(u, v)$ in the graph.

Output Format

Output one line containing the answer.

1 2
1
1 2

2

3 5
4
1 2
1 3
1 4
1 5
4
1 2
2 3
3 4
4 5
4
1 5
5 2
2 4
4 3

2

Hint

Sample Explanation

Sample 1 explanation: The only valid solution is that initially the plush toys are at $1$ and $2$.

Sample 2 explanation: One valid solution is that initially the plush toys are at $1$ and $3$.

---

Constraints

This problem uses bundled testdata.

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm t\le & \bm{n,m}\le & \textbf{分值} \\\hline \textsf{1} & 1 & 3\times 10^4 & 5 \\\hline \textsf{2} & 10 & 2 & 5 \\\hline \textsf{3} & 10 & 100 & 20 \\\hline \textsf{4} & 10 & 3\times10^3& 70 \\\hline\hline \end{array}$$

For $100\%$ of the testdata, $1 \le t \le 10$, $1 \le n, m \le 3 \times 10^4$. Note that the ranges of $t, n, m$ will not all reach the upper bounds at the same time.

It is guaranteed that each given graph has no multiple edges and no self-loops.

Translated by ChatGPT 5