#pragma comment(linker, "/stack:200000000")
       #pragma GCC optimize ("Ofast")
        #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
         
         
        #include <iostream>
        #include <iomanip>
        #include <sstream>
        #include <cstring>
        #include <vector>
        #include <deque>
        #include <queue>
        #include <set>
        #include <map>
        #include <valarray>
        #include <iterator>
        #include <functional>
        #include <limits>
        #include <algorithm>
        #include <numeric>
        #include <cmath>
        #include <cassert>
        #include <unordered_map>
        #include <stack>
        using namespace std;
        #define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
         #define trace(x) cerr << #x << ": " << x << " " << endl;
     
        typedef int64_t ll;
     
        #define endl '\n'
        #define int ll
        ll mod=1e9+7;
        ll mod1=1e9+5;
        ll power(ll a,ll b)
        {
            if(b==0) return 1;
            else if(b%2==0)
                return power((((a%mod)*(a%mod))%mod),b/2)%mod;
            else return ((a%mod)*(power((((a%mod)*(a%mod))%mod),b/2)%mod))%mod;
        }
        
        
        int n,m;
        
        vector<int> v[1001];
        
        int djik(int s,int t)
        {   
           
            int dis[n+1];
            for(int i=1;i<=n;++i)
                dis[i]=1e18;
                 
            dis[s]=0;
            priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq;
            pq.push({0,s});
            while(!pq.empty())
            {
                int u=pq.top().second;
                pq.pop();
                for(int i=0;i<v[u].size();++i)
                {
                    int dest=v[u][i];
                    int cos=1;
                    if(dis[dest]>dis[u]+cos)
                    {
                        dis[dest]=dis[u]+cos;
                        pq.push({dis[dest],dest});
                    }
                }
            }
            
            return dis[t];
            
            
        }
        void djik1(int s,int t)
        {   
           
            int dis[n+1];
            for(int i=1;i<=n;++i)
                dis[i]=1e18;
                int parent[n+1];
                memset(parent,-1,sizeof(parent));
            dis[s]=0;
            priority_queue< pair<int,int>, vector <pair<int,int>> , greater<pair<int,int>> > pq;
            pq.push({0,s});
            while(!pq.empty())
            {
                int u=pq.top().second;
                pq.pop();
                for(int i=0;i<v[u].size();++i)
                {
                    int dest=v[u][i];
                    int cos=1;
                    if(dis[dest]>dis[u]+cos)
                    {
                        dis[dest]=dis[u]+cos;
                        parent[dest]=u;
                        pq.push({dis[dest],dest});
                    }
                }
            }
            vector<int> v1;
            int temp=t;
            while(parent[temp]!=-1)
            {
                v1.push_back(temp);
                temp=parent[temp];
            }
            reverse(v1.begin(),v1.end());
            cout<<s<<endl;
            for(int i=0;i<v1.size();++i)
                cout<<v1[i]<<endl;
            
           
            
            
        }
        int32_t main()
        {
            IOS
           
         
            
            cin>>n>>m;
            int a[m+1],b[m+1];
            for(int i=0;i<m;++i)
                cin>>a[i]>>b[i];
            map<pair<int,int>,int> m1;map<pair<int,int>,int> m2;
            for(int i=0;i<m;++i)
            {
                for(int j=1;j<=n;++j)
                    v[j].clear();
                for(int j=0;j<m;++j)
                {
                    if(i==j)
                        continue;
                    v[a[j]].push_back(b[j]);
                }
                int x=djik(b[i],a[i]);
                
                m1[make_pair(b[i],a[i])]=x;
                m2[make_pair(b[i],a[i])]=i;
                
            }
            int fin=1e18;
            int st=-1,en=-1;
            for(auto i:m1)
            {
                if(i.second<fin)
                {
                    fin=i.second;
                    st=i.first.first,en=i.first.second;
                }
            }
            if(fin==1e18)
            {
                cout<<-1<<endl;
                return 0;
            }
            cout<<fin+1<<endl;
           
                for(int j=1;j<=n;++j)
                    v[j].clear();
                for(int j=0;j<m;++j)
                {
                    if(j==m2[make_pair(st,en)])
                        continue;
                    v[a[j]].push_back(b[j]);
                }
               
             
            
            djik1(st,en);

        }

Measured memory_bytes: 640