시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB5000.000%

문제

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.

서브태스크

번호배점제한
130

N ≤ 10

220

K ≤ 104

350

none

예제 입력 1

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

예제 출력 1

1 3 4 2 1

힌트

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

채점 및 기타 정보

  • 예제는 채점하지 않는다.