Problem Statement

Breakfast There are N items numbered from 1 to N that must be prepared. Each of the M relations A B means that item A must be prepared before item B . For every test case, print -1 if no ordering satisfies all relations. Otherwise, print the lexicographically smallest valid ordering of all items. An ordering is lexicographically smaller if, at the first position where two orderings differ, it has the smaller item number. Input Format The first line contains an integer T , the number of test cases. For each test case, the first line contains N and M . The next M lines each contain two integers A B , meaning A must come before B . Output Format For each test case, print -1 if the relations contain a cycle. Otherwise print the lexicographically smallest valid ordering, with spaces between consecutive item numbers. Constraints 1 <= T <= 5 2 <= N <= 3000 1 <= M <= min(19000, N * (N - 1) / 2) 1 <= A, B <= N The total input size is at most the sum implied by these limi