样例下载

【题目描述】

Farmer John 的 N 头奶牛排成一排，从前往后数，第 i 头奶牛的身高是 Hi。所有的身高都是不超过 M 的正整数。

在奶牛训练的时候，John 记录了一些相关的信息，这些信息共有 K 条，每条信息形如 x y，表示比前 x 头奶牛都高的最靠前的奶牛是第 y 头奶牛。

现在 John 需要每头奶牛的身高数据，从而对奶牛的训练作出安排。不幸的是，有些奶牛的身高数据丢失了。于是 John 向你求助，他希望你能根据他记录的信息帮他整理出每头奶牛的身高。你需要告诉 John 一个可能的身高序列。答案可能有很多，你只需要输出字典序最小的可能身高序列。如果无解，说明 John 的记录有误，此时输出 -1。

多组数据。

【输入格式】

第一行：包含一个整数 T, 表示数据组数。

对于每组数据：

• 第一行：包含三个整数 N, K, M;

• 第二行：包含 N 个整数 Hi; (若 Hi 为 0 则表示该身高数据丢失)

• 接下来 K 行，每行包含两个整数 x, y.(数据保证 1 ≤ x < y ≤ N，且同一组数据中的所有 x 均两两不同)

【输出格式】

共 T 行，每组数据的答案占一行，如果无解，输出 -1，否则输出 N 个正整数，表示字典序最小的可能身高序列。

【样例输入】

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

【样例输出】

1 2 1 3 4
-1

【数据范围】

100% 的数据：$1 ≤ T ≤ 20, 2 ≤ N ≤ 10^5, 1 ≤ K < N, 1 ≤ M ≤ 10^9$。其中

• 10% 的数据：$N ≤ 10; K, M ≤ 4$。
• 20% 的数据：$N, K, M ≤ 10$。
• 50% 的数据：$N ≤ 1000$。