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

#include <bits/stdc++.h>
using namespace std;

int n , a[101][101] , ok , x[101] , x1 , y , p[101];

void afisare()
{
    for(int i = 1 ; i <= n ; i++)
        cout << x[i] << " ";
    ok = 1;
}

void back(int k)
{
    for(int i = 1 ; i <= n && !ok; i++)
    if(!p[i])
    {
        x[k] = i;
        p[i] = 1;
        if(k == 1 || a[x[k - 1]][x[k]] == 1)
        {
            if(k == n) afisare();
            else back(k + 1);
        }
        p[i] = 0;
    }
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n * (n - 1) / 2 ; i++)
    {
        cin >> x1 >> y;
        a[x1][y] = 1;
    }
    back(1);
}