Tour
Tourist agency “Programmer” has to organize tour to the monasteries in the Fruška Gora mountain. In the Fruška Gora mountain there is n (3 <= n <= 1000) monasteries denoted by integers 1 to n. Because of lack of time the tour can contain not all the monasteries, but only k (3 <= k <= n) of them. There is direct road between any two monasteries in Fruška Gora. Since the mountain roads are very narrow, all roads are one way only.
You are to write a program to determine the tour of exactly k monasteries. The tour has to start and finish at the same monastery, and in the tour no monastery should be visited twice.
InputIn the first line contains two integers n (3 <= n <= 1000) and k (3 <= k <= n), separated by one blank. Each of the next n*(n-1)/2 lines contains two integers a and b (1 <= a, b <= n) which indicate that there is one way road from monastery a to monastery b.
OutputIf there is required tour then print k integers. These integers represent monasteries in the tour in order of their visits. If there is more than one such tour, write any of them. If there is no required tour then print number 0.
Input:
6 3
3 4
1 3
3 5
3 6
3 2
4 1
4 5
4 6
4 2
1 5
1 6
1 2
5 6
2 5
6 2Output:
1 3 4Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.