

NetflixNetflix stocks are approaching an alltime low, so the company is forced to take desperate steps. The plan is to go back to the basics and hire traveling salesmen that will go door to door and will try to convince possible clients to subscribe to the service. Your friend was out of job for some time now (in case making TikTok videos doesn't count as one), so in order to pay the bills, he decided to try out this salesman thing at Netflix. He was assigned to a strange neighborhood, with oneway streets only, and having the property that starting from any house, there is no way to get back there. Your friend needs your help to determine if it's possible for him to knock on all the doors in the neighborhood. Input SpecificationThe first line of the input contains t, the number of test cases to follow (1 ≤ t ≤ 20). Each test case starts with a line containing n, the number of houses in the neighborhood (1 ≤ n ≤ 100 000), and m, the number of streets (1 ≤ m ≤ 1 000 000). The following m lines contain two numbers x and y, with the meaning that there is a street going from house x to house y. The houses are numbered from 1 to n. Whitespaces can occur freely in the input. Output SpecificationFor each test case, you must output a single line. If your friend can visit all the houses, output a possible order in which he can visit them. Otherwise output 1. Sample Input
Output for Sample Input


University of Debrecen; Faculty of Informatics; v. 03/01/2019 