VIP-мережа

Вхідні дані

Перший рядок містить ціле число $t$ (1 \le t \le 10^4) — кількість наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить три цілі числа $n$, $m$ і $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)) — кількість міст, доріг і міст, які потрібно підвищити до статусу "VIP".

Наступні $m$ рядків описують дороги. Кожен рядок містить два цілі числа $u$ і $v$ (1 \le u, v \le n, u \ne v), що позначають двонапрямлену дорогу між містами $u$ і $v$.

Граф не містить петель і кратних ребер.

Гарантується, що сума $n$ по всіх наборах вхідних даних не перевищує 2 \cdot 10^5, а сума $m$ по всіх наборах вхідних даних не перевищує 5 \cdot 10^5.

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число — мінімально можливу сумарну величину заторів у дорожній мережі після того, як Фаді оптимально підвищить рівно $k$ міст до статусу "VIP".

Приклади

Примітка

У першому прикладі оптимальним вибором є підвищити місто $1$ до статусу "VIP". Показники заторів для доріг $(1,2)$, $(2,3)$, $(3,4)$ і $(4,1)$ стають рівними $2$, $3$, $3$ і $2$ відповідно. Мінімальна сумарна величина заторів дорівнює 2 + 3 + 3 + 2 = 10.

Оцінювання

• Підзадача $1$ ($50$ балів): \sum n \le 20.

• Підзадача $2$ ($250$ балів): Без додаткових обмежень.