Задан неориентированный связный граф с n вершинами и m ребрами. Каждое ребро имеет счетчик, изначально равный 0. За одну операцию Вы можете выбрать произвольное остовное дерево и добавить любое значение v ко всем ребрам этого остовного дерева.
Определите, можно ли сделать каждый счетчик равным его целевому значению x[i]
по простому модулю p, и предоставьте последовательность операций, обеспечивающих это.
Первая строка содержит три целых числа n, m и p - количество вершин, количество ребер и простой модуль (1 ≤ n ≤ 500, 1 ≤ m ≤ 1000, 2 ≤ p ≤ 10^9
, p - простое число).
Следующие m строк содержат по три целых числа u[i]
, v[i]
, x[i]
- две конечные точки i-го ребра и целевое значение счетчика этого ребра (1 ≤ u[i]
, v[i]
≤ n, 0 ≤ x[i]
< p, u[i]
≠ v[i]
).
Граф связный. Циклов нет, но между одними и теми же двумя вершинами может быть несколько ребер.
Если целевые значения счетчиков не могут быть достигнуты, выведите -1.
В противном случае выведите t - количество операций, а затем t строк, описывающих последовательность операций. Каждая строка начинается с целого числа v (0 ≤ v < p) - приращения счетчика для этой операции. Затем в той же строке следуют n - 1 целых чисел e[1]
, e[2]
, ..., e[n-1]
(1 ≤ e[i]
≤ m) - ребра остовного дерева.
Количество операций t не должно превышать 2m. Вам не нужно минимизировать t. Принимается любой правильный ответ в пределах 2m. Вам разрешено повторять остовные деревья.