Problem E: Soldiers

Problem E: Soldiers

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 664  Solved: 174
[Submit][Status][Web Board]

Description

Pisces has many soldiers, and he wants to train them in a line. Considering the height, weight and other factors of soldiers, Pisces wants some soldiers to stand in front of others. Besides, if there are multiple orders available, soldiers with smaller indices must stand as in the front as possible. It is guaranteed that the answer exists.

Input

The first line contains an integer \(T\) \((1\leq T \leq 10)\), which denotes the number of test cases.

For each of the test cases, the first line contains \(2\) integers \(n\) and \(m\) \((2\leq n \leq 2*10^5,1\leq m\leq 4*10^5)\), which represents the number of soldiers and the number of constrains, respectively. Each of the next \(m\) lines contains \(2\) integers \(u\) and \(v\) \((1\leq u,v\leq n)\), which means soldier \(u\) must stand in front of soldier \(v\).

Output

For each of the test cases, print the order.

Sample Input

1
6 4
6 5
5 1
4 3
3 2

Sample Output

6 5 1 4 3 2

HINT

[Submit][Status]