← 返回题目列表

Codeforces · 1773/J

J. 杂乱的树木

中文机器翻译题面 查看原题

给你一个无向连通图,其中有 $$$n$$$ 个顶点和 $$$m$$$ 个边。每条边都有一个关联的计数器,最初等于 $$$0$$$。在一次操作中,您可以选择任意一棵生成树,并将任意值 $$$v$$$ 添加到该生成树的所有边。

确定是否可以使每个计数器等于其目标值 $$$x_i$$$ 模素数 $$$p$$$,并提供实现该目标的一系列操作。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$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$$$ — 第 $$$i$$$ 边的两个端点以及该边计数器的目标值 ($$$1 \le u_i, v_i \le n$$$; $$$0 \le x_i \lt p$$$; $$$u_i \neq v_i$$$)。

该图已连接。不存在循环,但相同的两个顶点之间可能存在多条边。

输出

如果无法达到计数器的目标值,则打印 -1.

否则,打印 $$$t$$$ — 操作数,后跟 $$$t$$$ 行,描述操作顺序。每行以整数 $$$v$$$ ($$$0 \le v \lt p$$$) 开头——此操作的计数器增量。然后,在同一行中,后面跟着 $$$n - 1$$$ 整数 $$$e_1$$$, $$$e_2$$$, ... $$$e_{n - 1}$$$ ($$$1 \le e_i \le m$$$) — 生成树的边。

操作次数 $$$t$$$ 不应超过 $$$2m$$$。您不需要最小化$$$t$$$。任何在 $$$2m$$$ 范围内的正确答案都会被接受。您可以重复生成树。

示例

输入
复制

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