QBCIRARC - VOI06

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

using ll = long long;
using pii = pair<int, int>;

const int maxN = 1e3 + 5;
const int INF = 1e9 + 7;

int n, m;
vector<int> graph[maxN];

int cycle = 0;
bool act[maxN], visited[maxN];
bool connect[maxN][maxN], skip[maxN][maxN];

void dfs(int u) {
    act[u] = visited[u] = 1;
    for (int v : graph[u]) {
        if (!connect[u][v]) continue;

        if (act[v]) { // cycle found
          ++cycle;
          return;
        }
        else if (!visited[v]) dfs(v);
    }
    act[u] = 0;
}

bool check() {
    cycle = 0;
    memset(visited, 0, sizeof(visited));
    memset(act, 0, sizeof(act));
    for (int i = 1; i <= n && cycle == 0; i++)
        if (!visited[i]) dfs(i);
    return (cycle > 0);
}

int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#else
    freopen("QBCIRARC - VOI06.inp", "r", stdin);
    freopen("QBCIRARC - VOI06.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        if (connect[u][v]) {
            skip[u][v] = 1;
            continue;
        }
        graph[u].push_back(v);
        connect[u][v] = 1;
    }

    if (!check()) {
        cout << -1 << '\n';
        return 0;
    }

    vector<pii> edge;
    for (int u = 1; u <= n; ++u) {
        for (int v: graph[u]) {
            if (skip[u][v]) continue;
            connect[u][v] = 0;
            if (!check()) edge.push_back({u, v});
            connect[u][v] = 1;
        }
    }

    cout << (edge.size() == 0 ? -1: edge.size()) << '\n';
    sort(edge.begin(), edge.end());
    for (auto it : edge)
        cout << it.first << ' ' << it.second << '\n';

    return 0;
}