K-th Shortest Simple Path in a Directed Graph

You are given a directed graph with n cities (numbered 1 to n) and m one-way roads. Each road connects two distinct cities, and any two roads have either different start points or different endpoints, ensuring that m ≤ n(n-1).

Given two cities a and b, consider all simple paths from a to b (a simple path visits every city at most once, including the source and destination). The paths are ordered as follows:

• First, by the number of roads (i.e. path length) in ascending order.
• If two paths have the same length, they are compared in lexicographical order based on the sequence of city numbers.

Your task is to find the k-th shortest simple path from a to b according to the order specified above. If there are fewer than k simple paths, output None.

The ordering using lexicographical order is defined in \( \LaTeX \) as follows: if two paths are \( P = (p_1, p_2, \dots, p_r) \) and \( Q = (q_1, q_2, \dots, q_r) \) (with the same number of nodes), then \( P < Q \) if there exists an index \( i \) such that \( p_i < q_i \) and \( p_j = q_j \) for all \( 1 \le j < i \).

inputFormat

The first line contains two integers n and m, representing the number of cities and the number of one-way roads.

The following m lines each contain two integers u and v, indicating that there is a road from city u to city v.

The last line contains three integers a, b, and k — the starting city, the destination city, and the rank of the simple path to find.

outputFormat

If the k-th shortest simple path exists, output the sequence of cities on that path separated by a single space.

If it does not exist, output None.

sample

4 4
1 2
2 3
1 3
3 4
1 3 2

1 2 3