만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

합집합

면접 대비

시간 제한2초메모리 제한1024 MB

요약
양의 정수 집합 n개가 주어졌을 때, 전체 합집합과 다르면서 일부 집합의 합집합으로 만들 수 있는 집합의 원소 개수 최댓값을 구합니다.
난이도

보통10점 중 4점

유형
완전 탐색, 비트 연산, 구현
정답자
아직 제출이 없습니다

문제

양의 정수로 이루어진 집합 S_1,S_2,…,S_nS\_{1}, S\_{2}, \ldots, S\_{n}이 주어진다. S_1,S_2,…,S_nS\_{1}, S\_{2}, \ldots, S\_{n} 중 일부를 골라 그 합집합†^{\dagger}이 SS와 같아질 수 있으면 SS를 생성 가능하다고 한다. 0개를 고를 수도 있으므로 공집합은 항상 생성 가능하다.

SS가 생성 가능하고 S≠S_1∪S_2∪…∪S_nS \neq S\_{1} \cup S\_{2} \cup \ldots \cup S\_{n}일 때, SS의 원소 개수의 최댓값을 구하여라.

†^{\dagger} 집합 A_1,A_2,…,A_kA\_1, A\_2, \ldots, A\_k의 합집합은 A_1,A_2,…,A_kA\_1, A\_2, \ldots, A\_k 중 하나 이상에 속하는 수들의 집합이며, A_1∪A_2∪…∪A_kA\_1 \cup A\_2 \cup \ldots \cup A\_k로 표기한다. 예를 들어 {2, 4, 6} \cup {2, 3} \cup {3, 6, 7} = {2, 3, 4, 6, 7}이다.

입력

첫 줄에 테스트 케이스의 개수 tt가 주어진다(1≤t≤1001 \le t \le 100). 각 테스트 케이스의 첫 줄에는 정수 nn이 주어진다(1≤n≤501 \le n \le 50). 다음 nn개의 줄에 S_1,…,S_nS\_{1}, \ldots, S\_{n}의 정보가 주어진다. ii번째 줄에는 S_iS\_{i}의 원소 개수 k_ik\_{i}와 원소 s_i,1,s_i,2,…,s_i,k_is\_{i,1}, s\_{i,2}, \ldots, s\_{i,k\_{i}}가 공백으로 구분되어 주어진다(1≤k_i≤501 \le k\_{i} \le 50, 1≤s_i,1<s_i,2<…<s_i,k_i≤501 \le s\_{i,1} < s\_{i,2} < \ldots < s\_{i,k\_{i}} \le 50).

출력

각 테스트 케이스마다 정답을 출력한다.

힌트

첫 번째 테스트 케이스에서는 S=S_1∪S_3={1,2,3,4}S = S\_{1} \cup S\_{3} = \{1, 2, 3, 4\}일 때 원소 개수가 최대이다.

두 번째 테스트 케이스에서는 S=S_2∪S_3∪S_4={2,3,4,5,6}S = S\_{2} \cup S\_{3} \cup S\_{4} = \{2, 3, 4, 5, 6\}일 때 원소 개수가 최대이다.

세 번째 테스트 케이스에서는 S=S_2∪S_5=S_2∪S_3∪S_5={3,5,6,8,9,10}S = S\_{2} \cup S\_{5} = S\_{2} \cup S\_{3} \cup S\_{5} = \{3, 5, 6, 8, 9, 10\}일 때 원소 개수가 최대이다.

네 번째 테스트 케이스에서는 가능한 SS가 S=∅S = \varnothing뿐이다.

예제1

  1. 예제 1

    입력
    4
    3
    3 1 2 3
    2 4 5
    2 3 4
    4
    4 1 2 3 4
    3 2 5 6
    3 3 5 6
    3 4 5 6
    5
    1 1
    3 3 6 10
    1 9
    2 1 3
    3 5 8 9
    1
    2 4 28
    
    예상 출력
    4
    5
    6
    0