Rezolvare PBinfo #1551

Se dă mulțimea V a arcelor unui graf orientat cu n vârfuri.

Cerința

Să se determine drumul simplu de lungime maximă cu extremitatea inițială în vârful p din graf. Un drum simplu parcurge o singură dată un arc de pe traseul descris de drum în graf.

Date de intrare

Fișierul de intrare dslm.in conține pe prima linie numerele n și p, iar pe fiecare din următoarele linii, câte două numere a b reprezentând câte un arc (a,b) din V.

Date de ieșire

Fișierul de ieșire dslm.out va conține pe prima linie cel mai mic drum în sens lexicografic dintre drumurile simple de lungime maximă cu extremitatea inițială în nodul p; vârfurile din drum sunt separate prin câte un singur spațiu.

Restricții și precizări

• 1 ≤ n ≤ 20
• 1 ≤ a , b ≤n
• 1 ≤ p ≤ n
• mulțimea V are cel mult 30 de elemente
• pentru fiecare test există soluție
• dacă există mai multe soluții, atunci se va scrie în fișier cel mai mic drum în sens lexicografic dintre soluțiile obținute

Exemplu:

dslm.in

12 2
1 2
2 3
3 1
1 4
6 4
4 5
5 7
7 5
8 9
9 8
10 11
11 12

dslm.out

2 3 1 4 5 7 5

Explicație

Graful conține un singur drum simplu de lungime maximă cu extremitatea inițială în vârful p=2, D=[2,3,1,4,5,7,5]