Cerinţa

Se dă un graf orientat cu n vârfuri și m arce. Să se determine toate circuitele elementare formate din vârfuri care au aceeași paritate.

Date de intrare

Fişierul de intrare circuiteparitate.in conţine pe prima linie numerele n și m, reprezentând numărul de vârfuri ale grafului și numărul de arce ale grafului. Fiecare dintre următoarele m linii conține câte o pereche de numere i j, cu semnificația că există arc de la vârful i la vârful j.

Date de ieşire

Fişierul de ieşire circuiteparitate.out va conține, în ordine lexicografică și pe linii separate, circuitele elementare formate din vârfuri care au aceeași paritate. Vărfurile care formează fiecare circuit se separă prin exact un spațiu. Dacă graful nu conține niciun circuit elementar cu proprietatea cerută, atunci se va afișa NU EXISTA.

Restricţii şi precizări

• 1 ≤ n ≤ 20
• 1 ≤ m ≤ 100
• 1 ≤ i, j ≤ n
• muchiile se pot repeta în fișierul de intrare
• două circuite se consideră diferite dacă diferă succesiunea de vârfuri din care sunt formate

Exemplu:

circuiteparitate.in

6 9
1 4
1 3
3 5
4 5
2 4
1 2
4 6
3 1
6 2

circuiteparitate.out

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