La red VIP

Entrada

La primera línea contiene un entero $t$ (1 \le t \le 10^4) — el número de casos de prueba.

La primera línea de cada caso de prueba contiene tres enteros $n$, $m$ y $k$ (1 \le k \le n \le 2 \cdot 10^5, 0 \le m \le \min\left(5 \cdot 10^5, \frac{n(n-1)}{2}\right)) — el número de ciudades, de carreteras y de ciudades que deben ascenderse al estado "VIP".

Las siguientes $m$ líneas describen las carreteras. Cada línea contiene dos enteros $u$ y $v$ (1 \le u, v \le n, u \ne v) que indican una carretera bidireccional entre la ciudad $u$ y la ciudad $v$.

El grafo no contiene bucles ni aristas múltiples.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera 2 \cdot 10^5, y que la suma de $m$ sobre todos los casos de prueba no supera 5 \cdot 10^5.

Salida

Para cada caso de prueba, muestra un único entero — la mínima puntuación total de congestión posible de la red de carreteras después de que Fady ascienda de forma óptima exactamente $k$ ciudades al estado "VIP".

Ejemplos

Nota

En el primer ejemplo, la elección óptima es ascender la ciudad $1$ al estado "VIP". Las puntuaciones de congestión de las carreteras $(1,2)$, $(2,3)$, $(3,4)$ y $(4,1)$ pasan a ser $2$, $3$, $3$ y $2$, respectivamente. La mínima puntuación total de congestión es 2 + 3 + 3 + 2 = 10.

Puntuación

• Subtarea $1$ ($50$ puntos): \sum n \le 20.

• Subtarea $2$ ($250$ puntos): Sin restricciones adicionales.