Un graf orientat se numește graf turneu dacă oricare ar fi două noduri diferite i, j, între ele există un singur arc: arcul (i j) sau arcul (j i). În orice graf turneu există un drum elementar care trece prin toate nodurile grafului.

Cerința

Se dă un graf turneu cu n noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.

Date de intrare

Programul citește de la tastatură numărul de noduri n, iar apoi n*(n-1)/2 perechi i j, cu semnificația că există arcul (i j).

Date de ieșire

Programul va afișa pe ecran cele n noduri ale drumului determinat, separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• orice drum corect determinat este acceptat

Exemplu:

Intrare

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

Ieșire

1 4 3 2