Даны \(n\) множеств \(S_{1}, S_{2}, \ldots, S_{n}\), состоящих из целых чисел. Назовём множество \(S\) доступным, если можно выбрать некоторые из множеств \(S_{1}, S_{2}, \ldots, S_{n}\) (возможно, ни одного) так, что \(S\) равно их объединению\(^{\dagger}\). Если ни одно из множеств \(S_{1}, S_{2}, \ldots, S_{n}\) не выбрано, то объединение равно пустому множеству.
Найдите наибольшее возможное число элементов в доступном \(S\), таком что \(S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}\).
\(^{\dagger}\) Объединение множеств \(A_1, A_2, \ldots, A_k\) определяется как множество элементов, присутствующих по крайней мере в одном из этих множеств. Результат обозначается через \(A_1 \cup A_2 \cup \ldots \cup A_k\). Например, \(\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}\).
Выходные данные
Для каждого набора входных данных выведите одно число — наибольшее возможное число элементов в доступном \(S\), таком что \(S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}\).
Примечание
В первом наборе входных данных \(S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}\) — самое большое доступное множество, не равное \(S_1 \cup S_2 \cup S_3 = \{1, 2, 3, 4, 5\}\).
Во втором наборе входных данных можно выбрать \(S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}\).
В третьем наборе входных данных можно выбрать \(S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}\).
В четвёртом наборе входных данных единственным доступным множеством является \(S = \varnothing\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|