← 返回题目列表

Codeforces · 2115/B

B. 水母和山茶花

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

Gellyfish 有一个 $$$n$$$ 整数数组 $$$c_1, c_2, \ldots, c_n$$$。一开始,$$$c = [a_1, a_2, \ldots, a_n]$$$。

Gellyfish 将对 $$$c$$$ 进行 $$$q$$$ 修改。

对于 $$$i = 1,2,\ldots,q$$$,Gellyfish 被赋予 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$ 之间的三个整数 $$$1$$$ 和 $$$n$$$ 之间。然后 Gellyfish 将设置 $$$c_{z_i} := \min(c_{x_i}, c_{y_i})$$$。

$$$q$$$ 修改后,$$$c = [b_1, b_2, \ldots, b_n]$$$。

现在 Flower 知道 $$$b$$$ 的值以及所有 $$$1 \leq i \leq q$$$ 的整数 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$ 的值,但她不知道 $$$a$$$ 的值。

Flower 想要找到数组 $$$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$$$ 后数组 $$$c$$$ 的值。

以下 $$$q$$$ 行每行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$z_i$$$ ($$$1 \leq x_i, y_i, z_i \leq n$$$) — 描述第 $$$i$$$ 次修改。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果 $$$a$$$ 存在,则在一行中输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。否则,在一行中输出“-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 2 3 
1 2 3 4 5 5 

注意

在第一个测试用例中,根据给定的修改顺序,我们知道 $$$b_1 = a_1$$$ 和 $$$b_2 = \min(a_1, a_2)$$$。因此,$$$b_2 \leq b_1$$$ 是必要的。然而,对于给定的 $$$b$$$,我们有 $$$b_1 \lt b_2$$$。因此,没有解决办法。

在第二个测试用例中,我们可以看到给定的$$$c$$$在给定的修改后从$$$a$$$变为$$$b$$$,并且$$$c$$$在每次修改时都没有改变。