Little relyt871 正在解决一个谜题。谜题的关键是一个包含 $1 \dots n$ 的排列。排列中某些位置的值已经固定，relyt871 需要将数字填入剩余的位置。

此外，little relyt871 还收集了关于该排列的 $m$ 个额外要求。设解为 $p_1, p_2, \dots, p_n$，每个线索是一个下标对 $(u_i, v_i)$，这意味着在解中必须满足 $p_{u_i} < p_{v_i}$。

Little relyt871 想知道是否所有要求都能同时满足。请编写一个程序，在存在有效解时找出一个解。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 20\,000$)。

对于每个测试用例：

• 第一行包含两个整数 $n, m$ ($2 \le n \le 200\,000, 1 \le m \le 500\,000$)。
• 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le n$)。如果 $1 \le p_i \le n$，则位置 $i$ 的值固定为 $p_i$，否则需要你确定位置 $i$ 的值。保证对于 $1 \le i < j \le n$，若 $p_i > 0$ 且 $p_j > 0$，则 $p_i \neq p_j$。
• 接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n$)，表示线索。保证线索本身不矛盾。形式上，不存在线索序列 $(u_{i_1}, v_{i_1}), (u_{i_2}, v_{i_2}), \dots, (u_{i_k}, v_{i_k})$ 使得 $v_{i_j} = u_{i_{j+1}}$ ($1 \le j < k$) 且 $v_{i_k} = u_{i_1}$。

所有测试用例的 $n$ 之和不超过 $200\,000$，所有测试用例的 $m$ 之和不超过 $500\,000$。

输出格式

对于每个测试用例：

• 如果不存在有效解，输出一行 "-1"。
• 否则，输出一行包含 $n$ 个由空格分隔的整数，表示该解。如果存在多个解，输出任意一个即可。

样例

样例输入 1

2
4 4
1 0 0 4
1 2
1 3
2 4
3 4
3 2
0 3 1
1 2
3 1

样例输出 1

1 3 2 4
2 3 1

样例输入 2

1
4 4
1 4 0 0
1 2
1 3
2 4
3 4

样例输出 2

-1