18753번 - Alternative Accounts 다국어

Everybody knows that jiry_2 = Syloviaely.

There are n different accounts on the website, and some of them competed in the recent k contests. However, Mike suspects that there are lots of alternative accounts: two or more accounts owned by the same person.

There are axioms believed by everyone:

• Nobody can use two different accounts in one contest simultaneously.
• Nobody shares an account, which means that each account can only be owned by one person.

So, a set of accounts may be owned by the same person if no two of them took part in the same contest.

Mike wants to know the minimum possible number of different people behind the given list of accounts.

The first line contains an integer T (1 ≤ T ≤ 10⁵) indicating the number of test cases. For each test case:

The first line contains two integers n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 4).

Each of the following k lines contains an integer m (1 ≤ m ≤ n) first, followed by m distinct integers x_i (1 ≤ x_i ≤ n) indicating the accounts participating in the contest.

Some accounts may not participate in any contests.

It is guaranteed that Σn ≤ 5 · 10⁵.

For each test case, output one line with one integer: the answer.