题目描述

You are given an undirected connected graph with $n$ vertices and $m$ edges. Each edge has an associated counter, initially equal to $0$. In one operation, you can choose an arbitrary spanning tree and add any value $v$ to all edges of this spanning tree.

Determine if it's possible to make every counter equal to its target value $x_i$ modulo prime $p$, and provide a sequence of operations that achieves it.

输入格式

The first line contains three integers $n$, $m$, and $p$ --- the number of vertices, the number of edges, and the prime modulus ($1 \le n \le 500$; $1 \le m \le 1000$; $2 \le p \le 10^9$, $p$ is prime).

Next $m$ lines contain three integers $u_i$, $v_i$, $x_i$ each --- the two endpoints of the $i$-th edge and the target value of that edge's counter ($1 \le u_i, v_i \le n$; $0 \le x_i < p$; $u_i \neq v_i$).

The graph is connected. There are no loops, but there may be multiple edges between the same two vertices.

输出格式

If the target values on counters cannot be achieved, print $\tt{-1}$.

Otherwise, print $t$ --- the number of operations, followed by $t$ lines, describing the sequence of operations. Each line starts with integer $v$ ($0 \le v < p$) --- the counter increment for this operation. Then, in the same line, followed by $n - 1$ integers $e_1$, $e_2$, $\ldots$ $e_{n - 1}$ ($1 \le e_i \le m$) --- the edges of the spanning tree.

The number of operations $t$ should not exceed $2m$. You don't need to minimize $t$. Any correct answer within the $2m$ bound is accepted. You are allowed to repeat spanning trees.

3 3 101
1 2 30
2 3 40
3 1 50

3
10 1 2
20 1 3
30 2 3

2 2 37
1 2 8
1 2 15

2
8 1
15 2

5 4 5
1 3 1
2 3 2
2 5 3
4 1 4

-1