Задача №115268. Годовой отчет
Некоторые IT-компании проводят ежегодное глобальное мероприятие для сотрудников, на котором подводятся итоги года и обсуждаются ключевые точки в развитии всех проектов. В одной из компаний, на которой мы сфокусируемся, планируется обсуждение \(k\) различных ее проектов.
Для того, чтобы мероприятие прошло интересно, необходимо выбрать хороших спикеров. Есть \(n\) кандидатов, \(i\)-й из которых характеризуется своей осведомленностью о проектах — целым числом \(a_i\) от \(0\) до \(2^k - 1\). При этом некоторые из кандидатов дружат между собой, а именно, есть \(m\) пар друзей \((f_i, s_i)\).
Разумеется, всем хочется, чтобы мероприятие прошло гладко, а для этого необходимо, чтобы все спикеры попарно дружили между собой. При этом, чтобы рассказы спикеров не казались однообразными, важно, чтобы количество выбранных спикеров было как можно больше. Осведомленностью группы размера \(s\), состоящей из кандидатов \(i_1, i_2, \ldots, i_s\), называется \(a_{i_1} \oplus a_{i_2} \oplus \ldots a_{i_s}\), где \(\oplus\) — операция побитового исключающего «ИЛИ». Соответственно, помимо уже описанных критериев, среди всех подходящих групп кандидатов максимального размера необходимо выбрать группу спикеров с максимальной осведомленностью.
Мероприятие уже скоро, поэтому процесс набора кандидатов сейчас в самом разгаре. Ваша задача — выбрать оптимальную по описанным критериям группу спикеров.
Так как список кандидатов еще не утвержден окончательно и может меняться, вам надо решить эту задачу для \(t\) возможных наборов кандидатов.
В первой строке ввода находится одно целое число \(t\) — количество случаев, для которых надо решить задачу (\(1 \le t \le 120\)). Далее следует описание \(t\) наборов входных данных.
Первая строка каждого набора содержит три целых числа \(n\), \(m\) и \(k\) — количество кандидатов, количество пар друзей среди кандидатов и количество различных тем, которые будут обсуждаться на конференции, соответственно (\(1 \le n \le 40\); \(0 \le m \le \frac{n \cdot (n - 1)}{2}\); \(0 \le k \le 30\)).
Во второй строке каждого набора через пробел перечислены \(n\) целых чисел \(a_i\) — уровни осведомленности о проектах каждого из кандидатов (\(0 \le a_i \le 2^k - 1\)).
Далее следуют \(m\) строк, \(i\)-я из которых содержит два целых числа \(f_i\) и \(s_i\) — номера кандидатов, образующих \(i\)-ю пару друзей (\(1 \le f_i, s_i \le n\); \(f_i \neq s_i\)). Гарантируется, что все перечисленные пары друзей различны.
Гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(120\).
Для каждого набора входных данных выведите через пробел два числа в отдельной строке — сначала выведите размер максимальной группы спикеров, а затем выведите максимальную возможную осведомленность группы.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
Все указанные ограничения распространяются на все наборы входных данных в каждом тесте соответствующей группы.
Последняя подзадача имеет потестовую оценку и содержит \(7\) тестов, каждый из которых независимо оценивается в \(4\) балла.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | \(n \le 20\) | 0 | полная |
| 2 | 9 | \(k = 0\) | первая ошибка | |
| 3 | 15 | \(k \le 3\) | 2 | первая ошибка |
| 4 | 18 | \(n \le 30\) | 0, 1 | первая ошибка |
| 5 | 14 | \(a_i = 0\) при \(2 \le i \le n\) | 2 | первая ошибка |
| 6 | 9 | \(k = 2\), \(n\) четное, \(a_1 = \ldots = a_{\frac{n}{2}} = 1\), \(a_{\frac{n}{2}+1} = \ldots = a_n = 2\) | первая ошибка | |
| 7 | \(7 \times 4\) | без дополнительных ограничений | 0 – 6 | первая ошибка |
В примере из условия:
- в первом наборе входных данных выгодно выбрать спикеров под номерами \(3\) и \(4\) с осведомленностью \(a_3 \oplus a_4 = 3 \oplus 4 = 7\);
- во втором наборе входных данных выгодно выбрать спикеров под номерами \(1\), \(3\) и \(4\) с осведомленностью \(1 \oplus 4 \oplus 8 = 14\);
- в третьем наборе входных данных есть единственный способ выбрать четырех попарно дружащих спикеров: выбрать всех, кроме пятого.
3 6 2 4 1 2 3 4 5 6 1 2 3 4 6 8 8 1 2 4 8 16 32 1 2 2 3 3 4 4 5 5 6 6 1 1 3 1 4 5 8 6 1 2 4 8 16 1 2 1 3 1 4 2 3 2 4 2 5 3 5 3 4
2 7 3 13 4 15