Circuits

Jane and Joe are planning their winter vacation. They already have a list with N cities that they want to visit and another list with M flights connecting the cities.

Since Jane and Joe just won the lottery, instead of finding the cheapest circuit that visits all the cities exactly once, they want to choose the Kth such circuit in lexicographic order because this is their lucky number.

The first line contains three integers N, M and K.

The following M lines contain the list of flight connections in the format: u v meaning that there is a flight leaving from city u and arriving in city v.

The first line contains N + 1 numbers representing the circuit that Jane and Joe want to take, if it exists. Otherwise print a single number: 0 .

• A circuit starts and finishes in city number 1 (Jane and Joe's home city).
• A flight connection allows them to fly from city u to city v but not the other way around.
• Two circuits are different if the order the cities are visited is different.
• 3 ≤ N ≤ 18.
• 0 ≤ M ≤ N ⋅ (N − 1).
• 1 ≤ K ≤ 1018.
• 1 ≤ u, v ≤ N, u ≠ v for all flights.

There are 3 possible circuits. In lexicographic order, they are:

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