leximin

Se dă $N$, $M$, $K$ și un graf orientat aciclic (DAG) format din $N$ noduri (numerotate de la $1$ la $N$) și $M$ muchii. Să se afle drumul minim lexicografic care se termină în nodul $K$.

Un șir $a_1 \ a_2 \ \dots \ a_p$ este mai mic lexicografic decât șirul $b_1 \ b_2 \ \dots \ b_q$ dacă și numai dacă:

1. $p < q$ și $a_1 = b_1$, $a_2 = b_2$, $\dots a_p = b_p$ sau
2. Există o valoare $pos$ astfel încât $1 \leq pos \leq min(p, q)$ și $a_1 = b_1$, $a_2 = b_2$, $\dots$, $a_{pos-1} = b_{pos-1}$, iar $a_{pos} < b_{pos}$.

Date de intrare

Pe prima linie se găsesc trei numere naturale, $N$, $M$ și $K$, reprezentănd numărul de noduri, numărul de muchii și nodul în care se va termina drumul. Următoarele $M$ linii conțin câte două numere $u$ si $v$, semnificând că există muchie de la nodul $u$ la nodul $v$.

Date de ieșire

Pe prima linie se află numărul $L$, reprezentând lungimea drumului minim lexicografic. Pe a doua linie, se află un șir de lungime $L$, reprezentând drumul minim lexicografic.

Restricții și precizări

• $1 \leq N, M \leq 500 \ 000$
• $1 \leq u, v \leq N$, $u \neq v$ 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