Годовой отчет
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Некоторые 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примеры из условияполная
17$$$n \le 20$$$0полная
29$$$k = 0$$$первая ошибка
315$$$k \le 3$$$2первая ошибка
418$$$n \le 30$$$0, 1первая ошибка
514$$$a_i = 0$$$ при $$$2 \le i \le n$$$2первая ошибка
69 $$$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
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

Примечание

В примере из условия:

  1. в первом наборе входных данных выгодно выбрать спикеров под номерами $$$3$$$ и $$$4$$$ с осведомленностью $$$a_3 \oplus a_4 = 3 \oplus 4 = 7$$$;
  2. во втором наборе входных данных выгодно выбрать спикеров под номерами $$$1$$$, $$$3$$$ и $$$4$$$ с осведомленностью $$$1 \oplus 4 \oplus 8 = 14$$$;
  3. в третьем наборе входных данных есть единственный способ выбрать четырех попарно дружащих спикеров: выбрать всех, кроме пятого.