给你一个无向连通图,其中有 $$$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