#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

const int N = 505;

bool seen[N][N][2];
array<int, 3> bck[N][N][2];

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1;
    while(t --)
    {
        int n, m;
        cin >> n >> m;

        vector<vector<int>> adj(2 * n);
        for(int i = 0; i < m; i ++)
        {
            int s, t;
            cin >> s >> t;
            -- s, -- t;
            adj[s].push_back(t);
        }

        bool can = false;
        vector<int> route;

        queue<array<int, 3>> q;
        vector<array<int, 3>> toclear;

        for(int cross = n + 1; cross < 2 * n and !can; cross ++)
        {
            q.push({0, cross - n, 0});
            seen[0][cross - n][0] = true;
            bck[0][cross - n][0] = {-1, -1, 0};
            
            while(!q.empty())
            {
                auto [p1, p2, t] = q.front();
                q.pop();

                toclear.push_back({p1, p2, t});

                if(p1 < p2 and t == 0)
                {
                    for(auto v : adj[p1])
                        if(v < n and v != p2)
                            if(!seen[v][p2][0])
                            {
                                seen[v][p2][0] = true;
                                bck[v][p2][0] = {p1, p2, t};
                                q.push({v, p2, 0});
                            }
                }
                
                if(t == 1 or (t == 0 and p1 < p2))
                {
                    for(auto v : adj[n + p2])
                        if(v - n != p1)
                            if(!seen[p1][v - n][1])
                            {
                                seen[p1][v - n][1] = true;
                                bck[p1][v - n][1] = {p1, p2, t};
                                q.push({p1, v - n, 1});
                            }
                }
                else if(t == 0 and p1 > p2)
                {
                    for(auto v : adj[n + p2])
                        if(v - n != p1)
                            if(!seen[p1][v - n][t])
                            {
                                seen[p1][v - n][t] = true;
                                bck[p1][v - n][t] = {p1, p2, t};
                                q.push({p1, v - n, t});
                            }
                }
            }
            
            for(int bc = 0; bc < n - 1 and !can; bc ++)
                for(int t = 0; t <= 1 and !can; t ++)
                    if(seen[bc][n - 1][t])    
                        for(auto v : adj[bc])
                            if(v == cross)
                            {
                                can = true;

                                array<int, 3> at = {bc, n - 1, t};
                                while(at[0] != -1)
                                {
                                    route.push_back(at[0]);
                                    route.push_back(n + at[1]);
                                    at = bck[at[0]][at[1]][at[2]];
                                }

                                sort(route.begin(), route.end());
                                route.erase(unique(route.begin(), route.end()), route.end());

                                break;
                            }

            for(auto [u, v, t] : toclear)
                seen[u][v][t] = false, bck[u][v][t] = {0, 0};
            toclear.clear();
        }

        if(can)
        {
            cout << route.size() << endl;
            for(auto i : route)
                cout << i + 1 << " ";
            cout << endl;
        }
        else
            cout << "*" << endl;
    }
}