| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 92 | 31 | 30 | 41.096% |
Farmer John is hiring a new herd leader for his cows. To that end, he has interviewed $N$ (2ドル \leq N \leq 10^5$) cows for the position. After interviewing the $i$th candidate, he assigned the candidate an integer "cowmpetency" score $c_i$ ranging from 1ドル$ to $C$ inclusive (1ドル \leq C \leq 10^9$) 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 $Q$ (1ドル \leq Q < N$) pairs of numbers $(a_j, h_j)$ where cow $h_j$ was the first cow with a strictly greater cowmpetency score than cows 1ドル$ through $a_j$ (so 1ドル \leq a_j < h_j \leq N$).
Farmer John now tells you the sequence $c_1, \dots, c_N$ (where $c_i = 0$ means that he has forgotten cow $i$'s cowmpetency score) and the $Q$ pairs of $(a_j, h_j)$. 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 $T$ $(1 \leq T \leq 20)$ independent test cases. The sum of $N$ across all test cases is guaranteed to not exceed 3ドル \cdot 10^5$.
The first line contains $T,ドル the number of independent test cases. Each test case is described as follows:
For each test case, output a single line containing the lexicographically smallest sequence of cowmpetency scores consistent with what Farmer John remembers, or $-1$ if such a sequence does not exist.
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.
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.
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.