2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
J. Jumbled Trees

time limit per test

3 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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.

Output

If the target values on counters cannot be achieved, print -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$$$, ... $$$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.

Examples

Input

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

Output

3 10 1 2 20 1 3 30 2 3

Input

2 2 37 1 2 8 1 2 15

Output

2 8 1 15 2

Input

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

Output

-1

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/08/2023 21:06:55 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|