Додай ребра

Використовуйте мову Plain text для цієї задачі. Ця задача — Output only.

Дано дерево з $n$ вершин та $n-1$ ребер. Потрібно додати рівно $m$ нових ребер до цього дерева. Додавати кратні ребра або петлі заборонено. Якщо перед додаванням ребер у певної вершини була степінь $t_i$, то після додавання ребер її степінь не має перевищувати $t_i+k$. Нагадаємо, що степінь вершини — це кількість ребер, які її з'єднують з іншими вершинами.

Крім цього, також дано $m+n-1$ цілих чисел $a_1,a_2,\dots ,a_{m+n-1}$. Після додавання ребер потрібно зіставити кожному ребру один з елементів масиву $a$ так, щоб кожен елемент масиву відповідав рівно одному ребру. Значення $a_i$ зіставленому ребру позначатиме його вагу.

Потрібно додати нові ребра та зіставити числа до ребер так, щоб сума найкоротших відстаней між кожною парою вершин була максимальною. Тобто потрібно максимізувати функцію $\sum d_{ij}$, де $d_{ij}$ — мінімальна відстань між вершинами, для всіх $i$ та $j$ ($1\le i<j\le n$). Мінімальною відстанню між вершинами вважається сумарна вага усіх ребер на простому шляху між ними.

Зверніть увагу, що у цій задачі потрібно відправляти не код, а самі відповіді. Вам також доступні усі тести, які можна завантажити з Еолімпа.

Вхідні дані

Дано $5$ тестів.

Перший рядок кожного тесту містить три цілі числа $n$, $m$ та $k$ ($1\le n\le 5000$, $1\le m\le 250000$, $1\le k\le 500$) — кількість вершин у дереві, кількість ребер, які потрібно додати, та максимальна кількість ребер, які можна додати до однієї вершини.

Другий рядок містить $m+n-1$ цілих чисел $a_1,a_2,\dots ,a_{m+n-1}$ ($1\le a_i\le 10^6$).

Наступні $n-1$ рядків містять по два цілі числа $v_i$ та $u_i$ ($1\le v_i,u_i\le n$) — номери вершин, між якими є ребро. Гарантується, що початково заданий граф — дерево.

Гарантується, що завжди можна додати ребра так, щоб всі описані в умові вимоги виконувались.

Вихідні дані

Для кожного тесту виведіть наступне:

Якщо у вас є відповідь на цей тест, виведіть $1$, інакше $0$.

Якщо у вас є відповідь, то у кожному з наступних $m+n-1$ рядків виведіть по три цілі числа $v_i,u_i,a_i$ — номери вершин, між якими є ребро у кінцевому графі, та його вага.

Приклади

Оцінювання

Нехай $d_0$ певна змінна у тесті, а $d$ — сума відстаней у вашому графі. Якщо $d>d_0$, то ви отримаєте $20$ балів за тест. Інакше ви отримаєте стільки балів за тест:

Якщо $s$ — сума балів за всі тести, то за спробу ви отримаєте $s$, заокруглене до найближчого цілого числа.