SP262 CONNECT - Connections

Byteotian Ministry of Infrastructure has decided to create a computer program that helps to find quickly the lengths of routes between arbitrary towns. It would be small wonder if the inhabitants of Byteotia always wanted to find the shortest route. However, it happens that they want to know the _k_-th shortest route. Moreover, cycles in routes are possible, i.e. routes that have recurring towns. For example, if there are 4 routes between two towns and their lengths are 2, 4, 4 and 5, then the length of the shortest connection is 2, the second shortest is 4, the third is 4, and the fourth is 5. ### Task Write a program that for each test case: - Reads a description of Byteotian road network and queries concerning lengths of journey routes. - Computes and writes answers to the queries read.

One integer in the first line, stating the number of test cases, followed by a blank line. There will be not more than 15 tests. For each test case, at the first line, there are two positive integers _n_ and _m_, separated by a single space, 1

For each test case, your program should write the answers to the queries read, one answer per line. In the i-th line the answer to the i-th query should be written: one integer equal to the length of the route being sought or -1, when such a route does not exist. Each test case should be separated by a single blank line.