Системний інженер#369

Системний інженер

2 секунди

64 мегабайти

Дуже легка

Боб — досвідчений системний інженер, який регулярно стикається зі складними завданнями. Тепер йому потрібно розв'язати нову задачу: керувати набором серверів із різними можливостями для обробки постійних запитів на завдання із безперервних джерел, де кожне завдання потребує обробки протягом тривалого чи невизначеного часу.

Надходить послідовність запитів на виконання завдань, причому кожен запит містить підмножину серверів, які можуть обробити відповідне завдання. Кожне завдання виконується на одному сервері, і кожен сервер може обробляти лише одне завдання. Боб повинен запланувати максимальну кількість завдань на серверах. Наприклад, якщо є $2$ завдання $j_{1}$ j_1 і $j_{2}$ j_2 та $2$ сервери $s_{1}$ s_1 і $s_{2}$ s_2, і обидва завдання $j_{1}$ j_1 і $j_{2}$ j_2 потребують сервер $s_{1}$ s_1, Боб може запланувати лише одне завдання. Чи зможете ви йому допомогти?

У загальному випадку є $n$ завдань, пронумерованих від $0$ до $n - 1$ n-1, $n$ серверів, пронумерованих від $n$ до $2 n - 1$ 2n-1, і послідовність запитів на виконання завдань. Завдання полягає у визначенні максимальної кількості завдань, які можна обробити.

Вхідні дані

Програма зчитує вхідні дані з текстового файлу (не більше $1$ МБ). Кожен набір даних у файлі представляє певний набір завдань. Набір даних починається з числа $n$ ( $n \leq 10000$ n \leq 10000) — кількості завдань, далі йдуть списки потрібних серверів для кожного завдання у форматі: job_number: (nr_servers) $s_{1}$ s_1 ... $s_{n r_ser v er s}$ s_{nr\_servers}

Пробіли можуть довільно зустрічатися у вхідних даних. Вхідні дані правильні й закінчуються кінцем файлу.

Вихідні дані

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

Приклади

Приклад 1

Примітка

Зразок вхідних/вихідних даних наведено в таблиці нижче. Є два набори даних. У першому випадку кількість завдань $n$ дорівнює $2$ , вони мають номери $0$ і $1$ . Послідовність запиту для завдання $0$ — $0 : (1) 2$ 0: (1) 2, що означає, що завдання $0$ потребує $1$ сервер, а саме сервер $2$ . Послідовність запиту для завдання $1$ — $1 : (1) 2$ 1: (1) 2, тобто завдання $1$ також потребує $1$ сервер, сервер $2$ . Результат для цього набору даних — довжина максимальної кількості запланованих завдань, $1$ .