Некоторые 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 | первая ошибка |
36 2 41 2 3 4 5 61 23 46 8 81 2 4 8 16 321 22 33 44 55 66 11 31 45 8 61 2 4 8 161 21 31 42 32 42 53 53 4
2 7 3 13 4 15
В примере из условия: