The traveller Tommy is having a great time on ACM (Amazing-Chrysanthemum-Mountain) and there are N
tastefully landscapes and M
paths between landscapes. Now he will design a travelling route which consists of L
landscapes. Since Tommy is very interested in mathematics, he expects that the total length of route is a multiple of K
Your task is to help Tommy design such a route. If there are several solutions, choose the lexicographically smallest one. Note that any landscape can be visited more than once.
The path p
, ... , p
-1] is considered lexicographically smaller than the path q
, ..., q
-1] if there is an index i
such that p
] < q
] and the equation p
] = q
] holds for all j
The first line of the input contains one integer T
, which indicates the number of test cases.
For each test case, there are four integers N, M, K
separated by spaces.
There are three integers S, T
in each of the next M
lines, representing a path between S
whose length is V
. All the paths are bidirectional.
The last line of each test case contains an integers P
indicating the landscape site where Tommy starts (0-based indexing)
2 ≤ N, K, L
1 ≤ M
- 1) / 2
You should output a path sequence for each case separated by spaces. If there is no such a path, output -1 instead.
4 5 2 3
0 1 1
0 2 1
1 2 2
1 3 1
2 3 1
0 1 0