VIP Ağı

Giriş

İlk satırda bir tam sayı $t$ (1 \le t \le 10^4) verilir — test durumlarının sayısı.

Her test durumunun ilk satırında üç tam sayı $n$, $m$ ve $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)) verilir — şehirlerin sayısı, yolların sayısı ve "VIP" durumuna yükseltilecek şehirlerin sayısı.

Sonraki $m$ satır yolları tanımlar. Her satırda iki tam sayı $u$ ve $v$ (1 \le u, v \le n, u \ne v) verilir; bu, $u$ şehri ile $v$ şehri arasındaki iki yönlü bir yolu belirtir.

Graf, döngü (self-loop) veya çoklu kenar içermez.

Tüm test durumları boyunca $n$ değerlerinin toplamının 2 \cdot 10^5'i ve $m$ değerlerinin toplamının 5 \cdot 10^5'i aşmadığı garanti edilir.

Çıktı

Her test durumu için tek bir tam sayı yazdırın — Fady tam olarak $k$ şehri en iyi biçimde "VIP" durumuna yükselttikten sonra yol ağının elde edilebilecek en küçük toplam yoğunluk puanı.

Örnekler

Not

İlk örnekte en iyi seçim, $1$ numaralı şehri "VIP" durumuna yükseltmektir. $(1,2)$, $(2,3)$, $(3,4)$ ve $(4,1)$ yollarının yoğunluk puanları sırasıyla $2$, $3$, $3$ ve $2$ olur. En küçük toplam yoğunluk puanı 2 + 3 + 3 + 2 = 10'dur.

Puanlama

• Alt görev $1$ ($50$ puan): \sum n \le 20.

• Alt görev $2$ ($250$ puan): Ek kısıt yoktur.