#include<bits/stdc++.h>
typedef long long ll;
#define nl "\n"
#define pb push_back
using namespace std;
int k,t,x,y,tim;
vector< vector<int> > v;
vector<bool> vis;
vector<int> out;
void dfs(int node){
vis[node]=true;
for(int j=0; j<k; j++)
{
if(v[node][j]==1 && !vis[j])
dfs(j);
}
out[node]=tim++;
}
bool isDag(){
tim=0;
fill(vis.begin(), vis.end(), false);
for(int i=0; i<k; i++){
if(!vis[i]){
dfs(i);
}
}
for(int i=0; i<k; i++)
{
for(int j=0; j<k; j++){
if(v[i][j]==1 && out[j]>=out[i])
return false;
}
}
return true;
}
void solve()
{
cin>>k>>t;
v.resize(k);
vis.resize(k);
out.resize(k);
for(int i=0; i<k; i++)
{
v[i].resize(k);
fill(v[i].begin(),v[i].end(),0);
}
for(int idx=1; idx<=t; idx++){
cin>>x>>y;
x--; y--;
v[x][y]=1;
if(!isDag()){
v[x][y]=0;
cout<<x+1<<" "<<y+1<<"\n";
}
}
cout<<0<<" "<<0<<"\n";
}
int main()
{
solve();
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdHlwZWRlZiBsb25nIGxvbmcgbGw7CiNkZWZpbmUgbmwgIlxuIgojZGVmaW5lIHBiIHB1c2hfYmFjawp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBrLHQseCx5LHRpbTsKdmVjdG9yPCB2ZWN0b3I8aW50PiA+IHY7CnZlY3Rvcjxib29sPiB2aXM7CnZlY3RvcjxpbnQ+IG91dDsKCnZvaWQgZGZzKGludCBub2RlKXsKCXZpc1tub2RlXT10cnVlOwoJZm9yKGludCBqPTA7IGo8azsgaisrKQoJewoJCWlmKHZbbm9kZV1bal09PTEgJiYgIXZpc1tqXSkKCQkJZGZzKGopOyAKCX0KCQoJb3V0W25vZGVdPXRpbSsrOwp9Cgpib29sIGlzRGFnKCl7Cgl0aW09MDsKCWZpbGwodmlzLmJlZ2luKCksIHZpcy5lbmQoKSwgZmFsc2UpOwoJCglmb3IoaW50IGk9MDsgaTxrOyBpKyspewoJCWlmKCF2aXNbaV0pewoJCQlkZnMoaSk7CgkJfQoJfQkKCWZvcihpbnQgaT0wOyBpPGs7IGkrKykKCXsKCQlmb3IoaW50IGo9MDsgajxrOyBqKyspewoJCQlpZih2W2ldW2pdPT0xICYmIG91dFtqXT49b3V0W2ldKQoJCQkJcmV0dXJuIGZhbHNlOwoJCX0KCX0KCXJldHVybiB0cnVlOwp9CgoKdm9pZCBzb2x2ZSgpCnsKCWNpbj4+az4+dDsKCXYucmVzaXplKGspOwoJdmlzLnJlc2l6ZShrKTsKCW91dC5yZXNpemUoayk7Cglmb3IoaW50IGk9MDsgaTxrOyBpKyspCgl7CgkJdltpXS5yZXNpemUoayk7CgkJZmlsbCh2W2ldLmJlZ2luKCksdltpXS5lbmQoKSwwKTsKCX0KCQoJZm9yKGludCBpZHg9MTsgaWR4PD10OyBpZHgrKyl7CgkJY2luPj54Pj55OwoJCXgtLTsgeS0tOwoJCXZbeF1beV09MTsKCQlpZighaXNEYWcoKSl7CgkJCXZbeF1beV09MDsKCQkJY291dDw8eCsxPDwiICI8PHkrMTw8IlxuIjsKCQl9CQkKCX0JCgljb3V0PDwwPDwiICI8PDA8PCJcbiI7Cn0KaW50IG1haW4oKQp7CgogICAgICAgIHNvbHZlKCk7CiAgcmV0dXJuIDA7Cn0K