Note el límite de tiempo y memoria inusual para este problema

Es conocido que todos los años (o casi todos) se reúnen los mejores estudiantes de preuniversitario en la Preselección Nacional de Informática. Como parte de la preselección se necesita que los estudiantes compartan sus conocimientos con los demás estudiantes, por lo cual su entrenador ha decidido que se realizarán ~k~ charlas sobre temas diversos.

Para que las charlas sean interesantes se necesitan escoger los mejores estudiantes para dar las charlas. Hay ~n~ estudiantes, el ~i~-ésimo de ellos tiene un conocimiento ~a_i~ (~0 \le a_i \le 2^k - 1~).

Algunos de los estudiantes son amigos entre sí, es decir, hay ~m~ pares de amigos ~(f_i, s_i)~. Es importante que todos los estudiantes seleccionados para dar charlas sean amigos entre sí. Al mismo tiempo, para que las charlas sean diversas, es importante que el número de estudiantes seleccionados sea el mayor posible.

El conocimiento de un grupo de tamaño ~s~ que consta de estudiantes ~i_1, i_2, \ldots, i_s~ es ~a_{i_1} \oplus a_{i_2} \oplus \ldots a_{i_s}~, donde ~\oplus~ es el XOR bit a bit. En consecuencia, además de los criterios ya descritos, entre todos los grupos adecuados de estudiantes de tamaño máximo, es necesario seleccionar un grupo de estudiantes con el máximo conocimiento.

Su tarea es seleccionar el grupo óptimo de estudiantes según los criterios descritos. Debes resolver este problema para ~t~ posibles conjuntos de estudiantes.

El XOR bit a bit de enteros no negativos ~A~ y ~B~, ~A \oplus B~ , se define de la siguiente manera:

Cuando ~A \oplus B~ se escribe en base dos, el dígito en el lugar de ~2^k~ ~(k \geq 0)~ es ~1~ si exactamente uno de los dígitos en ese lugar de ~A~ y ~B~ es ~1~, y ~0~ en el caso contrario. Por ejemplo, tenemos ~3\oplus 5 = 6~ (en base dos: ~011 \oplus 101 = 110~). Generalmente, el XOR bit a bit de ~k~ enteros no negativos ~p_1,p_2,p_3, \dots ,p_k~ se define como ~(\dots ((p_1 \oplus p_2)\oplus p_3)\oplus \cdots \oplus p_k)~. Podemos demostrar que este valor no depende del orden de ~p_1,p_2,p_3,\dots ,p_k~. Esta operación se hace mediante el símbolo ^ en muchos lenguajes de programación.

Subtareas

• Subtarea 1 (7 puntos): ~n \le 20~.
• Subtarea 2 (9 puntos): ~k=0~.
• Subtarea 3 (15 puntos): ~k \le 3~.
• Subtarea 4 (18 puntos): ~n \le 30~.
• Subtarea 5 (14 puntos): ~a_i = 0~ para ~2 \le i \le n~.
• Subtarea 6 (9 puntos): ~k=2~, ~n~ par, ~a_1 = \dots = a_{\frac{n}{2}} = 1~, ~a_{\frac{n}{2}+1} = \dots = a_{n} = 2~.
• Subtarea 7 (28 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene un número entero ~t~: el número de casos para los cuales se debe resolver el problema (~1 \le t \le 120~). Le siguen ~t~ conjuntos casos.

La primera línea de cada conjunto contiene tres números enteros ~n~, ~m~ y ~k~: el número de estudiantes, el número de pares de amigos entre los estudiantes y el número de charlas que se realizarán en la preselección, respectivamente (~1 \le n \le 40~, ~0 \le m \le \frac{n \cdot (n - 1)}{2}~, ~0 \le k \le 30~).

La segunda línea de cada conjunto contiene ~n~ enteros separados por espacios ~a_i~: el nivel de conocimiento de cada estudiante (~0 \le a_i \le 2^k - 1~).

A continuación siguen ~m~ líneas, la ~i~-ésima de ellas contiene dos números enteros ~f_i~ y ~s_i~: el estudiante ~f_i~ y el estudiante ~s_i~ son amigos (~1 \le f_i, s_i \le n~, ~f_i \neq s_i~). Se garantiza que todos los pares de amigos son diferentes.

Se garantiza que la suma de ~n~ sobre todos los conjuntos de datos de entrada no excede los ~120~.

Salida

Para cada conjunto de entradas, imprima dos números separados por espacios en una línea separada: primero imprima el tamaño del grupo máximo de estudiantes y luego imprima el máximo conocimiento posible del grupo.

Ejemplos

Entrada 1

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

Salida 1

2 7
3 13
4 15

• En el primer caso es óptimo seleccionar los estudiantes ~3~ y ~4~ con conocimiento ~a_3 \oplus a_4 = 3 \oplus 4 = 7~.
• En el segundo caso es óptimo seleccionar los estudiantes ~1~, ~3~ y ~4~ con conocimiento ~1 \oplus 4 \oplus 8 = 14~.
• En el tercer caso sólo hay una forma de seleccionar estudiantes: seleccionar todos menos el quinto.