Maximum Initial Plush Distribution in Kindergarten

At the beginning of the kindergarten school year, some children have a plush toy which they may share with others. The sharing process occurs over \(t\) days. On each day, the seating arrangement can be represented as an undirected graph. Any child that has a plush toy on a given day must choose exactly one child sitting next to him (i.e. connected by an edge in that day's graph) to send the toy to. Note that each child can have at most one plush toy. Furthermore, we assume that in each day, all children first send out their toy and then receive from others.

An initial configuration (i.e. the set of children that begin with a plush toy) is considered legal if there exists a sequence of transfers – one for each of the \(t\) days – such that every child who has a plush toy on that day is able to send one to a neighbor, and at the end of the day each child ends up with at most one toy. In other words, on each day the transfer corresponds to selecting a matching in the seating graph (where every toy-holding child is matched with a neighbor) so that the set of recipients is exactly as many as the set of senders.

Your task is to find the maximum number of children who can have a plush toy initially such that there exists a legal sequence of transfers over \(t\) days. Observe that if we denote \(S_0\) as the initial set of children with a toy and for every day \(i\) there is a matching \(M_i\) from \(S_{i-1}\) (the set of toy-holders at the start of day \(i\)) to some set \(S_i\) (the recipients), then the size of the matching must be \(|S_{i-1}|\). Therefore, for the process to be possible, every seating arrangement must admit a matching of size at least \(k\) if we start with \(k\) toys. Equivalently, the answer is the largest integer \(k\) such that every day's graph has a matching of size at least \(k\).

Mathematically, if \(M_i\) is the size of a maximum matching in the graph for day \(i\), then the answer is:

[ \text{answer} = \min_{1 \le i \le t} M_i. ]

inputFormat

The first line contains two integers (n) and (t) (the number of children and the number of days). For each day, the input begins with an integer (m), the number of edges in that day's seating graph. Then (m) lines follow, each containing two integers (u) and (v) (1-indexed) representing an undirected edge between children (u) and (v).

outputFormat

Output a single integer, representing the maximum number of children that can initially have a plush toy such that there exists a legal transfer process over (t) days.

sample

4 1
3
1 2
2 3
3 4

2