Cerința

Se dă un graf orientat cu n noduri. Determinați, dacă există, un drum hamiltonian – drum elementar care conține toate nodurile.

Date de intrare

Fișierul de intrare drum_hamiltonian.in conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există arc de la i la j.

Date de ieșire

Fișierul de ieșire drum_hamiltonian.out va conține pe prima linie numărul 1, dacă s-a determinat un drum hamiltonian, respect nu 0, în caz contrar. Dacă s-a determinat un drum hamiltonian, pe linia următoare se vor afișa nodurile acestui drum, separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 10
• 1 ≤ i,j ≤ n
• orice drum hamiltonian afișat corect va fi acceptat

Exemplu:

drum_hamiltonian.in

5
1 5
2 1
2 5
3 1
4 2
5 3

drum_hamiltonian.out

1
4 2 1 5 3