B'Nezzar designs a brand new game "Hidden Permutations" and shares it with his best friend, Nanako. At the beginning of the game, Nanako and Nezzar both know integers n and m . The game goes in the following way: However, Nezzar accidentally knows Nanako 's unordered pairs and decides to take advantage of them. Please help Nezzar find out two permutations p and q such that the score is maximized. The first line contains a single integer t ( 1 <= t <= 5 cdot 10^5 ) -- the number of test cases. The first line of each test case contains two integers n,m ( 1 <= n <= 5 cdot 10^5, 0 <= m <= min( frac{n(n-1)}{2},5 cdot 10^5) ). Then m lines follow, i -th of them contains two integers l_i,r_i ( 1 <= l_i,r_i <= n , l_i neq r_i ), describing the i -th unordered pair Nanako chooses. It is guaranteed that all m unordered pairs are distinct. It is guaranteed that the sum of n for all test cases does not exceed 5 cdot 10^5 , and the sum of m for all test cases does not exceed 5 cdot 10^5 . For each test case, print two permutations p_1,p_2, ldots,p_n and q_1,q_2, ldots,q_n such that the score Nezzar gets is maximized. For first test case, for each pair given by Nanako: As Nezzar does not lose instantly, Nezzar gains the score of 4 as p_i neq q_i for all 1 <= q i <= q 4 . Obviously, it is the maximum possible score Nezzar can get. '...