În Iași a fost constituit grupul de sprijin “Împreună pentru A8”. Printre manifestările acestui grup este și o grevă în care trebuie să fie blocată o singură șosea din județ. Autoritățile județene vor să autorizeze aceste manifestări însă doar pe anumite șosele, astfel încât traficul să rămână posibil între oricare două localități.

Cerința

Cunoscând N numărul de localități din județ, acestea fiind codificate prin numere naturale din mulțimea 1, 2, …, N și M numărul de șosele care leagă direct câte două localități ale județului, să se afle K numărul de șosele pe care nu trebuie aprobate manifestările și care sunt aceste șosele. Fiecare șosea este determinată în mod unic de două numere naturale X și Y reprezentând cele două localități legate direct de șosea.

Date de intrare

Fișierul de intrare autostrada.in conține pe prima linie N M două numere naturale reprezentând numărul de localități din județ, respectiv numărul de șosele directe între perechi distincte de localități, iar pe următoarele M linii perechi de numere naturale X Y, reprezentând codurile localităților legate direct prin șosea.

Date de ieșire

Fișierul de ieșire autostrada.out va conține pe prima linie un singur număr natural K, reprezentând numărul de șosele pe care nu trebuie aprobate manifestații, iar pe următoarele K linii se află câte o pereche de numere X Y, reprezentând numerele de ordine ale localităților între care există șosea pe care nu trebuie autorizată greva. Perechile sunt afișate în ordine lexicografică.

Restricții și precizări

• 1 ≤ N ≤ 50
• 1 ≤ M ≤ 120
• 1 ≤ X, Y ≤ N
• Perechea A B este mai mică lexicografic decât perechea C D dacă A < C sau A = C și B < D
• Pentru datele de test există întotdeauna soluție
• În concurs s-au acordat 10 puncte din oficiu; aici se acordă 10 puncte pentru testul din exemplu

Exemplu

autostrada.in

6 7
1 2
2 4
1 4
3 4
3 5
5 6
3 6

autostrada.out

1
3 4

Explicație

Singura șosea pe care nu se poate autoriza greva este 3 4. Dacă eliminăm șoseaua 3 4 nu va fi posibil traficul între localitățile 1 3, 2 3 șamd.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("autostrada.in");
ofstream cout("autostrada.out");

int a[51][51], n, m, st[1001], dr[1001], l;

bool parcurg(){
    int P[100] = {0};
    queue<int> Q;
    Q.push(1);
    P[1] = 1;
    int cnt = 1;
    while(!Q.empty()){
        int x = Q.front();
        for(int j = 1; j <= n; ++j)
            if(a[x][j] == 1 && !P[j])
                P[j] = 1, Q.push(j), cnt++;
        Q.pop();
    }
    return cnt == n;
}

int main(){
    int x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(a[i][j] == 1){
                a[i][j] = a[j][i] = 0;
                if(!parcurg())
                    st[++l] = i, dr[l] = j;
                a[i][j] = a[j][i] = 1;
            }
    cout << l << endl;
    for(int i = 1; i <= l; ++i)
        cout << st[i] << ' ' << dr[i] << endl;
    return 0;
}