Організація компанії

Ви започаткували компанію кілька років тому, і, на щастя, вона стала дуже успішною. Зі зростанням компанії ви помітили необхідність більш організовано керувати працівниками й вирішили створити кілька груп та призначати до них працівників.

Тепер ви плануєте створити $n$ груп, кожна з яких відповідає певному проєкту. Іноді існують обмеження щодо складу цих груп. Наприклад: - Одна група є підмножиною іншої, оскільки складається зі старших учасників - Дві групи мають мати однаковий склад, оскільки їхні проєкти тісно пов’язані - Склади двох груп не повинні повністю збігатися, щоб уникнути корупції - Дві групи не можуть мати спільних співробітників із міркувань безпеки - Між двома групами повинен бути хоча б один спільний учасник для полегшення співпраці

Позначимо X_i (i = 1, \ldots, n) — множину працівників, призначених у $i$-у групу. Можливі пʼять типів обмежень:

1. X_i \subseteq X_j 2. X_i = X_j 3. X_i \neq X_j 4. X_i \cap X_j = \varnothing 5. X_i \cap X_j \neq \varnothing

Оскільки обмеження у списку можуть бути взаємно суперечливими, задовольнити всі одночасно не завжди можливо. Обмеження впорядковані за пріоритетами. Ваше завдання — знайти найбільший префікс, який можна виконати одночасно, починаючи з найпріоритетнішого.

Вам не потрібно враховувати здібності співробітників — ви можете призначати будь-кого до будь-якої групи або створювати групи без учасників. Можна брати на роботу або звільняти необмежену кількість людей для виконання більшої кількості обмежень.

Наприклад, для трьох груп задано пʼять обмежень у порядку пріоритету (як у першому прикладі у вхідних даних):

- X_2 \subseteq X_1 - X_3 \subseteq X_2 - X_1 \subseteq X_3 - X_1 \neq X_3 - X_3 \subseteq X_1

Наділивши X_1, X_2 та X_3 однаковим набором людей, можна виконати перші три обмеження. Проте перші чотири одночасно виконати неможливо. Хоча можна виконати перші три та пʼяте одночасно, відповіддю буде число три.