Minimum Captains Required

In a sports event, there are N students and S sports. Each student participates in one or more sports. The event organizers need to choose a subset of students as captains so that every sport is covered by at least one captain. A student covers a sport if they participate in that sport.

Task: Determine the minimum number of captains required so that all sports are covered. The selection follows a greedy strategy: iterate over the students in order, and if a student participates in any sport that has not yet been covered, choose that student as a captain and mark all sports they participate in as covered. It is guaranteed that eventually, all sports will be covered.

Note: All formulae in this statement are provided in \(\LaTeX\) format when applicable.

inputFormat

The input begins with an integer T, representing the number of test cases. For each test case, the first line contains two integers N and S ((1 \leq N, S \leq 10^5)), where N is the number of students and S is the number of sports. This is followed by N lines. Each of these lines starts with an integer k indicating the number of sports the student participates in, followed by k space-separated integers representing the 1-indexed sport identifiers.

outputFormat

For each test case, output a single line containing the minimum number of captains required to cover all sports.## sample

1
3 3
1 1
2 2 3
2 1 3

2