#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> h(n + 1, 0), t(m + 1), x(m + 1), hr(n + 1, 0), tr(m + 1), xr(m + 1), uo(m + 1), vo(m + 1), id(n + 1, 0), od(n + 1, 0);
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
uo[i] = u;
vo[i] = v;
t[i] = v;
x[i] = h[u];
h[u] = i;
tr[i] = u;
xr[i] = hr[v];
hr[v] = i;
id[v]++;
od[u]++;
}
vector<int> ir(n + 1, 0), q(n + 1);
int hq = 0, tq = 0;
for (int i = 1; i <= n; i++)
if (id[i] == 0 || od[i] == 0)
q[tq++] = i;
while (hq < tq)
{
int u = q[hq++];
if (ir[u])
continue;
ir[u] = 1;
for (int i = h[u]; i; i = x[i])
if (!ir[t[i]])
if (--id[t[i]] == 0)
q[tq++] = t[i];
for (int i = hr[u]; i; i = xr[i])
if (!ir[tr[i]])
if (--od[tr[i]] == 0)
q[tq++] = tr[i];
}
vector<int> cc, vs(n + 1, 0), p(n + 1, 0), pe(n + 1, 0), ic(m + 1, 0);
int f = 1;
auto find_c = [&](auto self, int u, int skip) -> int {
vs[u] = 1;
for (int i = h[u]; i; i = x[i])
{
if (i == skip || ir[t[i]])
continue;
int v = t[i];
if (vs[v] == 1)
{
if (f)
{
ic[i] = 1;
cc.push_back(i);
}
int cur = u;
while (cur != v)
{
if (f)
{
ic[pe[cur]] = 1;
cc.push_back(pe[cur]);
}
cur = p[cur];
}
return 1;
}
if (vs[v] == 0)
{
p[v] = u;
pe[v] = i;
if (self(self, v, skip))
return 1;
}
}
vs[u] = 2;
return 0;
};
int st = -1;
for (int i = 1; i <= n; i++)
if (!ir[i])
{
st = i;
break;
}
if (st != -1)
find_c(find_c, st, -1);
f = 0;
int e0 = -1;
vector<int> iv(n + 1, 0), in(m + 1, 0);
while (true)
{
int et = -1;
for (int i : cc)
if (ic[i])
{
et = i;
break;
}
if (et == -1)
break;
int nrem = 0;
for (int i = 1; i <= n; i++)
if (!ir[i])
{
iv[i] = 0;
nrem++;
}
for (int i = 1; i <= n; i++)
if (!ir[i])
for (int j = h[i]; j; j = x[j])
if (j != et && !ir[t[j]])
iv[t[j]]++;
hq = 0;
tq = 0;
for (int i = 1; i <= n; i++)
if (!ir[i] && iv[i] == 0)
q[tq++] = i;
int remc = 0;
while (hq < tq)
{
int u = q[hq++];
remc++;
for (int i = h[u]; i; i = x[i])
if (i != et && !ir[t[i]])
if (--iv[t[i]] == 0)
q[tq++] = t[i];
}
if (remc == nrem)
{
e0 = et;
break;
}
else
{
int ns = -1;
for (int i = 1; i <= n; i++)
if (!ir[i] && iv[i] > 0)
{
ns = i;
break;
}
for (int i = 1; i <= n; i++)
vs[i] = 0;
vector<int> nce;
auto find_c2 = [&](auto self, int u, int skip) -> int {
vs[u] = 1;
for (int i = h[u]; i; i = x[i])
{
if (i == skip || ir[t[i]])
continue;
int v = t[i];
if (vs[v] == 1)
{
nce.push_back(i);
int cur = u;
while (cur != v)
{
nce.push_back(pe[cur]);
cur = p[cur];
}
return 1;
}
if (vs[v] == 0)
{
p[v] = u;
pe[v] = i;
if (self(self, v, skip))
return 1;
}
}
vs[u] = 2;
return 0;
};
find_c2(find_c2, ns, et);
for (int i : nce)
in[i] = 1;
vector<int> ncc;
for (int i : cc)
if (ic[i] && in[i])
ncc.push_back(i);
else
ic[i] = 0;
for (int i : nce)
in[i] = 0;
cc = ncc;
}
}
if (e0 == -1)
{
cout << 0 << '\n';
return 0;
}
int u0 = uo[e0], v0 = vo[e0];
for (int i = 1; i <= n; i++)
if (!ir[i])
iv[i] = 0;
for (int i = 1; i <= n; i++)
if (!ir[i])
for (int j = h[i]; j; j = x[j])
if (j != e0 && !ir[t[j]])
iv[t[j]]++;
hq = 0;
tq = 0;
for (int i = 1; i <= n; i++)
if (!ir[i] && iv[i] == 0)
q[tq++] = i;
vector<int> top;
while (hq < tq)
{
int u = q[hq++];
top.push_back(u);
for (int i = h[u]; i; i = x[i])
if (i != e0 && !ir[t[i]])
if (--iv[t[i]] == 0)
q[tq++] = t[i];
}
ll m1 = 1000000007, m2 = 1000000009;
vector<ll> f1(n + 1, 0), f2(n + 1, 0), t1(n + 1, 0), t2(n + 1, 0);
f1[v0] = 1;
f2[v0] = 1;
for (int u : top)
for (int i = h[u]; i; i = x[i])
if (i != e0 && !ir[t[i]])
{
f1[t[i]] = (f1[t[i]] + f1[u]) % m1;
f2[t[i]] = (f2[t[i]] + f2[u]) % m2;
}
t1[u0] = 1;
t2[u0] = 1;
for (int i = (int)top.size() - 1; i >= 0; i--)
{
int u = top[i];
for (int j = h[u]; j; j = x[j])
if (j != e0 && !ir[t[j]])
{
t1[u] = (t1[u] + t1[t[j]]) % m1;
t2[u] = (t2[u] + t2[t[j]]) % m2;
}
}
ll k1 = f1[u0], k2 = f2[u0];
vector<pair<int, int>> ans;
ans.push_back({u0, v0});
for (int i = 1; i <= n; i++)
if (!ir[i])
for (int j = h[i]; j; j = x[j])
if (j != e0 && !ir[t[j]])
if ((f1[i] * t1[t[j]]) % m1 == k1 && (f2[i] * t2[t[j]]) % m2 == k2)
ans.push_back({i, t[j]});
cout << ans.size() << '\n';
for (auto &p : ans)
cout << p.first << ' ' << p.second << '\n';
return 0;
}