아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

합집합

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

요약
정수 집합 n개가 주어질 때, 전체 합집합과 다른 부분집합의 합집합 중 원소 수가 최대인 것을 구한다.
난이도

보통10점 중 7점

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

문제

양의 정수로 구성된 집합 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를 생성 가능하다고 한다. 00개를 선택할 수도 있기 때문에, 공집합은 항상 생성 가능하다.

집합 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∪2,3∪3,6,7=2,3,4,6,7\\{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_2,…,S_nS\_{1}, S\_{2}, \ldots, S\_{n}의 정보가 주어진다. 이 중 ii번째 줄에는 S_iS\_{i}의 원소의 개수 k_ik\_{i}와 S_iS\_{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,4S = S\_{1} \cup S\_{3} = \\{1, 2, 3, 4\\}일 때 원소 개수가 최대이다.

두 번째 테스트 케이스에서, S=S_2∪S_3∪S_4=2,3,4,5,6S = 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,10S = 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