ZOJ Problem Set - 4103
The famous traveler BaoBao is visiting the Dream Kingdom now. There are $n$ cities in Dream Kingdom, numbered from $1$ to $n$. The cities are connected by directed roads. For all $1 \le i \le n$:
BaoBao starts his travel from the 1st city. As he doesn't like visiting a city more than once, he wants to find a route which goes through each of the $n$ cities exactly once. Can you help him find such a route?
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first and the only line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of cities in Dream Kingdom.
It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.
For each test case output one line. If there exists a route which starts from the 1st city and visits each city exactly once, output $n$ integers $c_1, c_2, \dots, c_n$ separated by a space, where $c_i$ indicates the $i$-th city in the route (note that according to the description, there must be $c_1 = 1$). If there is no valid route, output "-1" (without quotes) instead. If there are multiple valid answers, you can output any of them.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
2 2 9
1 2 1 3 6 5 2 4 9 8 7
Author: CHEN, Shihan; WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple