All submissions for this problem are available.
The students of the XYZ school spend time together: they watch cricket, they go fishing, they solve contests. So, it's no big deal that sometimes someone pays for someone else.
Today is the day of giving out money rewards in XYZ school. The XYZ school Principal will invite students into his office one by one, rewarding each one for the hard work this month. The Principal knows who owes money to whom. And he also understands that if he invites student x to his office for a reward, and then immediately invite student y, who has lent some money to student x, then they can meet. Of course, in such a situation, the joy of student x from his brand new money reward will be much less. Therefore, the XYZ Principal decided to invite the students in such an order that the described situation will not happen for any pair of students invited one after another.
However, there are a lot of students in the school, and the Principal doesn't have a lot of time. Therefore, the task has been assigned to you. Given the debt relationships between all the students, determine in which order they should be invited to the office of the XYZ school Principal, or determine that the described order does not exist.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- 1st line of each test case consists of two space separated integers n, m where n denotes number of students and m denotes number of debt relations between students.
- Each of the next m lines contains two space separated integers a, b which denotes that student a owes money to student b.
- For each test case print -1 if the described order doesn't exist else print the order. If there are multiple orders print any of them.
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 104
- 1 ≤ m ≤ min(105, n*(n-1)/2)
- 1 ≤ a,b ≤ n
1 3 3 1 2 2 3 3 1
2 1 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.