A16608 | $Gellyfish and Camellia Japonica$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Gellyfish 有一个长度为 $n$ 的整数数组 $c$，初始状态为 $c = [a_1, a_2, \ldots, a_n]$。接下来，Gellyfish 对数组进行 $q$ 次修改。每次修改由三个整数 $x_i, y_i, z_i$ 描述，表示将 $c_{z_i}$ 的值设置为 $\min(c_{x_i}, c_{y_i})$。经过 $q$ 次修改后，数组变为 $c = [b_1, b_2, \ldots, b_n]$。 Flower 知道最终数组 $b$ 和所有修改操作 $(x_i, y_i, z_i)$，但不知道初始数组 $a$。她希望找到任意一个满足条件的初始数组 $a$，或者判断不存在这样的 $a$。如果存在多个解，输出任意一个即可。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 对于每个测试用例: 第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 3 \cdot 10^5$），分别表示数组大小和修改次数。 第二行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 10^9$），表示修改后的数组。 接下来的 $q$ 行，每行包含三个整数 $x_i, y_i, z_i$（$1 \leq x_i, y_i, z_i \leq n$），描述一次修改操作。 所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $3 \cdot 10^5$。

对于每个测试用例： 如果存在初始数组 $a$，输出一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。 否则，输出一行 -1 。

输入 #1

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

输出 #1

-1
1 2 3 
1 2 3 4 5 5

C++ 编辑器

输入

输出