In order to teach students how to make pizza, you had written down recipes of n pizza types. Then you approximately marked the relation between some pair of pizza, where a directed edge ( pizza x -> pizza y ) means that a student will feel more difficult to make pizza y than to make pizza x.
You have marked all the necessary relations, then you wanted to make it sequential. You want to give all recipes an unique difficulty
integer between 1 and n. If making a pizza y is more difficult than making a pizza x, the difficulty of recipe x should be smaller than that of recipe y.
You have assigned all recipes a difficulty integer. But, after a few days, you lost some numbers, so you could not even know whether the numbers were correct or not. Please write a program to find out the remaining numbers or point out it is impossible.
Warn: 本題有 specialjudge
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains two integers n, m (1<= n<= 100000; 0<= m<= 200000), indicating the number of pizza and relations. Each of the next m lines contains two integers xi, yi denoting a directed edge from pizza xi to pizza yi.
Then there are n integers or question marks. If the i-th term is an integer, then it is the difficulty of that recipe. Otherwise it will be a question mark, indicating that you have lost i-th pizza's difficulty.
For each test case, output n integers of any valid solution or output Impossible if there is no solution.
3 3 3 1 2 1 3 2 3 ? ? ? 3 3 1 2 1 3 2 3 1 2 3 3 3 1 2 2 3 1 3 ? ? 1
1 2 3 1 2 3 Impossible
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|