Перемішані дерева#11329

Перемішані дерева

1 секунда

128 мегабайтів

Легка

Задано неорієнтований зв'язний граф з $n$ вершинами та $m$ ребрами. У кожного ребра є лічильник, початково рівний $0$ . За одну операцію можна вибрати довільне остовне дерево і додати одне й те ж значення $v$ до всіх ребер цього дерева.

Визначте, чи можливо домогтися того, щоб лічильник кожного ребра став рівним своєму цільовому значенню $x_{i}$ x_i за модулем простого числа $p$ . Якщо це можливо, виведіть послідовність операцій, яка призводить до заданої конфігурації.

Вхідні дані

Перший рядок містить три цілі числа $n, m$ та $p (1 \leq n \leq 500, 1 \leq m \leq 1000, 2 \leq p \leq 1 0^{9})$ p~(1 \le n \le 500, 1 \le m \le 1000, 2 \le p \le 10^9) — кількість вершин, кількість ребер та модуль. Відомо, що $p$ — просте число.

Наступні $m$ рядків містять по три цілі числа $u_{i}, v_{i}, x_{i} (1 \leq u_{i}, v_{i} \leq n, 0 \leq x_{i} < p, u_{i} \neq = v_{i})$ u_i, v_i, x_i~(1 \le u_i, v_i \le n, 0 \le x_i < p, u_i \ne v_i) — кінці $i$ -го ребра та його цільове значення.

Граф зв'язний. Циклів в ньому немає, але між одними й тими ж вершинами може існувати декілька ребер.

Вихідні дані

Якщо досягти цільових значень неможливо, виведіть $- 1$ .

У протилежному випадку, виведіть число операцій $t$ , а потім $t$ рядків з їхнім описом. Кожен рядок починається з цілого числа $v (0 \leq v < p)$ v~(0 \le v < p) — приросту для даної операції. Потім йдуть $n - 1$ n - 1 цілих чисел $e_{1}, e_{2}, \dots, e_{n - 1} (1 \leq e_{i} \leq m)$ e_1, e_2, \dots, e_{n-1}~(1 \le e_i \le m) — ребра, що утворюють обране остовне дерево.

Кількість операцій $t$ не повинна перевищувати $2 m$ . Мінімізувати $t$ не потрібно: допускається будь-яка коректна відповідь у межах цього обмеження. Дозволяється використовувати одне й те ж остовне дерево кілька разів.

Приклади

Приклад 1

Приклад 2

Приклад 3