2017: [USACO 2024 January Contest Silver] Problem 1. Cowmpetency
题目描述
Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed () cows for the position. After interviewing the th candidate, he assigned the candidate an integer "cowmpetency" score ranging from to inclusive () that is correlated with their leadership abilities.
Because he has interviewed so many cows, Farmer John does not remember all of their cowmpetency scores. However, he does remembers () pairs of numbers where cow was the first cow with a strictly greater cowmpetency score than cows through (so ).
Farmer John now tells you the sequence (where means that he has forgotten cow 's cowmpetency score) and the pairs of . Help him determine the lexicographically smallest sequence of cowmpetency scores consistent with this information, or that no such sequence exists! A sequence of scores is lexicographically smaller than another sequence of scores if it assigns a smaller score to the first cow at which the two sequences differ.
Each input contains independent test cases. The sum of across all test cases is guaranteed to not exceed .
输入
- First, a line containing , , and .
- Next, a line containing the sequence .
- Finally, lines each containing a pair . It is guaranteed that all within a test case are distinct.
输出
样例输入
1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5样例输出
1 2 2 3 4 4 1
提示
- , and so the first pair is satisfied
- , and so the second pair is satisfied
- , and so the third pair is satisfied
There are several other sequences consistent with Farmer John's memory, such as
1 2 2 3 5 4 1
1 2 2 3 4 4 5
However, none of these are lexicographically smaller than the given output.SAMPLE INPUT:
5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 9
SAMPLE OUTPUT:
1 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1
In test case 3, since , the only potential sequence is
1 1
However, in this case, cow 2 does not have a greater score than cow 1, so we cannot satisfy the condition.In test case 5, and tell us that cow 6 is the first cow to have a strictly greater score than cows 1 through 4. Therefore, the largest score for cows 1 through 6 is that of cow 6: 5. Since cow 7 has a score of 7, cow 7 is the first cow to have a greater score than cows 1 through 6. So, the second statement that cow 9 is the first cow to have a greater score than cows 1 through 6 cannot be true.
SCORING:
- Input 3 satisfies and .
- Inputs 4-8 satisfy .
- Inputs 9-12 satisfy no additional constraints.