Стрункий Остов#5831

Стрункий Остов

5 секунд

64 мегабайти

Середня

Дано неорієнтований зважений граф $G$ . Потрібно знайти одне з остовних дерев, визначених наступним чином.

Граф $G$ є впорядкованою парою $(V, E)$ (V, E), де $V$ — це множина вершин ${v_{1}, v_{2}, \dots, v_{n}}$ \{v_1, v_2, \ldots, v_n\}, а $E$ — це множина неорієнтованих ребер ${e_{1}, e_{2}, \dots, e_{m}}$ \{e_1, e_2, \ldots, e_m\}. Кожне ребро $e$ має свою вагу $w (e)$ .

Остовне дерево $T$ — це дерево (зв'язний підграф без циклів), яке з'єднує всі $n$ вершини за допомогою $n - 1$ n-1 ребер. Стрункість остовного дерева $T$ визначається як різниця між найбільшою вагою та найменшою вагою серед $n - 1$ n-1 ребер $T$ .

Рисунок 1: Граф $G$ та ваги ребер

Наприклад, граф $G$ на Рисунку 1(a) має чотири вершини ${v_{1}, v_{2}, v_{3}, v_{4}}$ \{v_1, v_2, v_3, v_4\} та п'ять неорієнтованих ребер ${e_{1}, e_{2}, e_{3}, e_{4}, e_{5}}$ \{e_1, e_2, e_3, e_4, e_5\}. Ваги ребер: $w (e_{1}) = 3$ w(e_1) = 3, $w (e_{2}) = 5$ w(e_2) = 5, $w (e_{3}) = 6$ w(e_3) = 6, $w (e_{4}) = 6$ w(e_4) = 6, $w (e_{5}) = 7$ w(e_5) = 7, як показано на Рисунку 1(b).

Рисунок 2: Приклади остовних дерев $G$

Існує кілька остовних дерев для $G$ . Чотири з них зображені на Рисунку 2(a)'(d). Остовне дерево $T_{a}$ T_a на Рисунку 2(a) має три ребра, ваги яких $3$ , $6$ і $7$ . Найбільша вага — $7$ , а найменша вага — $3$ , тому стрункість дерева $T_{a}$ T_a дорівнює $4$ . Стрункість остовних дерев $T_{b}$ T_b, $T_{c}$ T_c і $T_{d}$ T_d, показаних на Рисунку 2(b), (c) і (d), дорівнює $3$ , $2$ і $1$ відповідно. Легко побачити, що стрункість будь-якого іншого остовного дерева більша або дорівнює $1$ , отже, остовне дерево $T_{d}$ T_d на Рисунку 2(d) є одним з найстрункіших остовних дерев, стрункість якого дорівнює $1$ .

Ваше завдання — написати програму, яка обчислює найменшу стрункість.

Вхідні дані

Вхід складається з кількох наборів даних, за якими слідує рядок, що містить два нулі, розділені пробілом. Кожен набір даних має наступний формат.

$n$ $m$

$a_{1}$ a_1 $b_{1}$ b_1 $w_{1}$ w_1

$\dots$

$a_{m}$ a_m $b_{m}$ b_m $w_{m}$ w_m

Кожен елемент введення в наборі даних є невід'ємним цілим числом. Елементи в рядку розділені пробілом.

$n$ — це кількість вершин, а $m$ — кількість ребер. Можна припустити, що $2 \leq n \leq 100$ 2 \leq n \leq 100 і $0 \leq m \leq n (n - 1) /2$ 0 \leq m \leq n(n-1)/2. $a_{k}$ a_k і $b_{k}$ b_k ( $k = 1, \dots, m$ k = 1, \ldots, m) є додатними цілими числами, меншими або рівними $n$ , які представляють дві вершини $v_{a_{k}}$ v_{a_k} і $v_{b_{k}}$ v_{b_k}, з'єднані $k$ -м ребром $e_{k}$ e_k. $w_{k}$ w_k є додатним цілим числом, меншим або рівним $10000$ , що вказує на вагу $e_{k}$ e_k. Можна припустити, що граф $G = (V, E)$ G = (V, E) є простим, тобто не має петель (які з'єднують одну й ту ж вершину) і паралельних ребер (які є двома або більше ребрами, обидва кінці яких є одними й тими ж двома вершинами).

Вихідні дані

Для кожного набору даних, якщо граф має остовні дерева, слід вивести найменшу стрункість серед них. В іншому випадку, слід вивести $- 1$ . Вивід не повинен містити зайвих символів.

Приклади

Приклад 1