#include<stdio.h>
#define mkp make_pair
#include<vector>

using namespace std;

#define pb push_back
const int maxn = 300;

vector<int> vect[maxn];
vector<int> vect1[maxn];
int dr[maxn];
int st[maxn];
int ver[maxn];
int n,m,i,x,y;
int sti[maxn];
int nrm;
pair <int,int> mu[maxn];
vector<int> vectinv[maxn];

bool cupl(int i)
{
        if (ver[i]) return 0;
        ver[i] = 1;

        for(vector <int> :: iterator it = vect[i].begin();it != vect[i].end(); ++it)
        {
                if ((!st[*it]) || cupl(st[*it]))
                {
                        dr[i] = *it;
                        st[*it] = i;
                        return 1;
                }
        }
        return 0;
}

void dfs(int i)
{
        for(vector <int> :: iterator it = vect1[i].begin(); it != vect1[i].end(); ++it)
        {
                if (!ver[*it])
                {
                        ver[*it] = 1;
                        sti[++sti[0]] = *it;
                        dfs(*it);
                }
        }
}


int main()
{
        freopen("strazi.in","r",stdin);
        freopen("strazi.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(i = 1;i <= m; ++i)
        {
                scanf("%d %d",&x,&y);
                vect[x].pb(y);
               // vect[y].pb(x);
        }

        for(i = 1;i <= n; ++i)
        {
                if (!dr[i]) cupl(i);
                memset(ver,0,sizeof(ver));
        }
        memset(ver,0,sizeof(ver));
        for(i = 1;i <= n; ++i)
        {
                if (dr[i])
                {
                        vect1[i].pb(dr[i]);
                        vectinv[dr[i]].pb(i);
                }
                
        }
        for(i = 1;i <= n; ++i)
        {
                if (!ver[i])
                {
                        int j = i;
                        while(vectinv[j].size() != 0)
                        {
                                j = vectinv[j][0];
                        }
                        if (sti[0] != 0) mu[++nrm] = mkp(sti[sti[0]],j);
                        ver[j] = 1;
                        sti[++sti[0]] = j;
                        dfs(j);
                }
        }

        printf("%d\n",nrm);
        for(i = 1;i <= nrm; ++i) printf("%d %d\n",mu[i].first,mu[i].second);
        for(i = 1;i < sti[0]; ++i) printf("%d ",sti[i]);
        printf("%d\n",sti[sti[0]]);


        return 0;
}