#PU1374. USACO 2024 January Contest, Silver — Problem 1. Cowmpetency
USACO 2024 January Contest, Silver — Problem 1. Cowmpetency
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 .
输入格式
The first line contains , the number of independent test cases. Each test case is described as follows: 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.
输出格式
For each test case, output a single line containing the lexicographically smallest sequence of cowmpetency scores consistent with what Farmer John remembers, or if such a sequence does not exist.
数据范围
(见题面原文)
样例
样例 1
1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 5
1 2 2 3 4 4 1
We can see that the given output satisfies all of Farmer John's remembered
pairs.
$\max(c_1) = 1$, $c_2 = 2$ and $1<2$ so the first pair is satisfied
$\max(c_1,c_2,c_3) = 2$, $c_4 = 3$ and $2<3$ so the second pair is
satisfied
$\max(c_1,c_2,c_3,c_4) = 3$, $c_5 = 4$ and $3<4$ 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.
样例 2
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
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 $C=1$, 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, $a_1$ and $h_1$ 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.