Codeforces Round 170 (Div. 1) |
---|
Закончено |
В компании «BerCorp» работает n сотрудников. Для официальной переписки утверждено m языков, пронумерованных целыми числами от 1 до m. Для каждого сотрудника известно, какие языки он знает. Возможно даже, что человек не знает ни одного официального языка. Но работники готовы выучить любое количество языков, если только компания оплатит им обучение. Стоимость курса изучения одного языка для одного сотрудника составляет 1 бердоллар.
Определите, какую минимальную сумму денег придется затратить компании, чтобы любой сотрудник мог обратиться к любому другому, возможно, не напрямую (то есть, привлекая других сотрудников для перевода).
В первой строке записано два целых числа n и m (2 ≤ n, m ≤ 100) — количество сотрудников и количество языков.
Далее следует n строк — списки языков для каждого работника. В начале i-ой строки записано целое число ki (0 ≤ ki ≤ m) — количество языков, которые знает i-ый сотрудник. Далее в i-ой строке записано ki целых чисел — aij (1 ≤ aij ≤ m) — номера языков, которые знает i-ый сотрудник. Гарантируется, что все номера в одном списке различны. Обратите внимание, что сотрудник может не знать ни одного языка.
Числа в строках разделяются одиночными пробелами.
Выведите единственное целое число — наименьшее количество денег, которое придется заплатить, чтобы каждый мог написать письмо каждому (возможно, привлекая других для перевода).
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0
8 7
0
3 1 2 3
1 1
2 5 4
2 6 7
1 3
2 7 4
1 1
2
2 2
1 2
0
1
Во втором примере сотрудник с номером 1 может выучить язык с номером 2, а сотрудник с номером 8 — язык с номером 4.
В третьем примере сотруднику с номером 2 нужно выучить язык с номером 2.
Название |
---|