VIP Şəbəkə

Giriş

Birinci sətirdə $t$ tam ədədi verilir ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — test hallarının sayı.

Hər test halının birinci sətrində üç tam ədəd $n$ , $m$ və $k$ verilir ( $1 \leq k \leq n \leq 2 \cdot 1 0^{5}$ 1 \le k \le n \le 2 \cdot 10^5, $0 \leq m \leq min (5 \cdot 1 0^{5}, \frac{n ( n - 1 )}{2})$ 0 \le m \le \min\left(5 \cdot 10^5, \frac{n(n-1)}{2}\right)) — şəhərlərin sayı, yolların sayı və "VIP" statusuna yüksəldiləcək şəhərlərin sayı.

Sonrakı $m$ sətir yolları təsvir edir. Hər sətirdə iki tam ədəd $u$ və $v$ verilir ( $1 \leq u, v \leq n$ 1 \le u, v \le n, $u \neq = v$ u \ne v) — $u$ və $v$ şəhərləri arasındakı ikitərəfli yol.

Qrafda ilgəklər və təkrar tillər yoxdur.

Bütün test hallarında $n$ -lərin cəminin $2 \cdot 1 0^{5}$ 2 \cdot 10^5-i, $m$ -lərin cəminin isə $5 \cdot 1 0^{5}$ 5 \cdot 10^5-i aşmadığına zəmanət verilir.

Çıxış

Hər test halı üçün bir tam ədəd çıxarın — Fady dəqiq $k$ şəhəri optimal şəkildə "VIP" statusuna yüksəltdikdən sonra yol şəbəkəsinin mümkün olan minimal ümumi sıxlıq balı.

Nümunələr

Nümunə 1

Loading

Qeyd

Birinci nümunədə optimal seçim $1$ nömrəli şəhəri "VIP" statusuna yüksəltməkdir. $(1, 2)$ , $(2, 3)$ , $(3, 4)$ və $(4, 1)$ yolları üçün sıxlıq balları müvafiq olaraq $2$ , $3$ , $3$ və $2$ olur. Minimal ümumi sıxlıq balı $2 + 3 + 3 + 2 = 10$ 2 + 3 + 3 + 2 = 10-a bərabərdir.

Bal hesablama

Altməsələ $1$ ( $50$ bal): $\sum n \leq 20$ \sum n \le 20.
Altməsələ $2$ ( $250$ bal): Əlavə məhdudiyyət yoxdur.