Time limit: 2s
Memory limit: 128MB
Input:
Output:
Se dă , , și un graf orientat aciclic (DAG) format din noduri (numerotate de la la ) și muchii. Să se afle drumul minim lexicografic care se termină în nodul .
Un șir este mai mic lexicografic decât șirul dacă și numai dacă:
- și , , sau
- Există o valoare astfel încât și , , , , iar .
Date de intrare
Pe prima linie se găsesc trei numere naturale, , și , reprezentănd numărul de noduri, numărul de muchii și nodul în care se va termina drumul. Următoarele linii conțin câte două numere si , semnificând că există muchie de la nodul la nodul .
Date de ieșire
Pe prima linie se află numărul , reprezentând lungimea drumului minim lexicografic. Pe a doua linie, se află un șir de lungime , reprezentând drumul minim lexicografic.
Restricții și precizări
- , pentru fiecare muchie
Exemplul 1
stdin
9 11 6
4 1
6 9
5 3
3 9
1 5
3 6
2 9
8 9
4 8
7 8
7 4
stdout
4
1 5 3 6