She - Co ta


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1000M

Author:
Problem type
Allowed languages
Assembly, C, C++, Java, Pascal, Perl, Python, Text

As the story unfolds...

In the middle of a vast desert of nothing but sand and sun, she rose like a single blooming flower.

Every step, every movement she made was chased down by the media. What did she do to earn all this? She's talented, she's kind - but like anyone else, she stumbles and corrects her mistakes too. And the world waits on every word she says, every story about her, just to satisfy its own curiosity.

When she takes part in an event - a special event lasting exactly \(M\) minutes - they say that even if there are \(N\) people like her, each one must be captured, moment by moment, by a dedicated media crew. At the moment corresponding to minute \(i\), if there are \(m_i\) people appearing at the same time (the list published by the platform being: \(x_{i,1}, x_{i,2}, ..., x_{i,m_i}\)), then that many crews must be tracking them. And once someone appears - no matter at which moment, which minute - a crew will follow that person closely from the very first minute to the very last minute that person appears. Only after that will the crew move on to chase after someone else.

However, this overload has forced the platforms to impose limits. They have capped the number of crews allowed to attend. And so, the world has taken to guessing - trying to figure out just how few crews would be enough to cover all \(N\) of these people.

Input

  • The first line contains two positive integers \(N, M \ (1 \le N, M \le 10^5)\);
  • The next \(M\) pairs of lines, the \(i\)-th pair structured as follows:
    • The first line contains an integer \(m_i \ (1 \le m_i \le N)\);
    • The next line contains \(m_i\) distinct integers \(x_{i,j} \ (1 \le x_{i,j} \le N)\).

It is guaranteed that \(m_1 + m_2 + ... + m_M \le 10^5\).

Output

  • A single integer as the answer to the problem.

Scoring

  • Subtask 1 (60%): \(N, M \le 10^3\).
  • Subtask 2 (40%): No additional constraints.

Example

Example 1

input

2 3
1
1
2
1 2
1
2

output

2
Example 2

input

3 3
1
1
1
2
1
3

output

1
Example 3

input

6 7
2
1 2
2
2 3
3
1 3 4
2
4 5
2
2 5
1
6
2
3 6

output

4

Explanation

In example 1, the event lasts 3 minutes and there are 2 people. At the moment corresponding to minute 2, both people appear at the same time. So we need at least 2 crews to track the 2 people.

In example 2, all three people appear at different moments, so just one crew is enough to track all 3 of them.


Comments

There are no comments at the moment.