#include <iostream>

using namespace std;

const int N = 410, INF = 1e9;

int n, m;
int d1[N][N], d2[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            if (i == j) d1[i][j] = d2[i][j] = 0;
            else d1[i][j] = INF, d2[i][j] = 1;
        }

    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        d1[a][b] = d1[b][a] = 1;
        d2[a][b] = d2[b][a] = INF;
    }

    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]),
                d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);

    int res = max(d1[1][n], d2[1][n]);
    if (res > INF / 2) res = -1;

    cout << res << endl;

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 210, M = 20010, INF = 1e9;

int n, m, q;
int dist[N][N];

void floyd()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

int main()
{
    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = INF;

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        dist[a][b] = min(dist[a][b], c);
    }

    floyd();

    while (q--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        if (dist[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", dist[a][b]);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool st[N];
bool used[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i), st[i] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] == n) return true;
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j]) q.push(j), st[j] = true;
            }
        }
    }
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    spfa();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

priority_queue<PII, vector<PII>, greater<PII>> heap;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dijkstra()
{
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int v = t.y;
        if (st[v]) continue;
        st[v] = true;

        for (int i = h[v]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[v] + w[i])
                dist[j] = dist[v] + w[i], heap.push({dist[j], j});
        }
    }
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }


    memset(dist, 0x3f, sizeof dist);

    int k;
    cin >> k;
    while (k--)
    {
        int x;
        scanf("%d", &x);
        dist[x] = 0;
        heap.push({0, x});
    }

    dijkstra();

    int q;
    cin >> q;
    while (q--)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", dist[x]);
    }

    return 0;
}

#include <iostream>
#include <queue>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];

priority_queue<PII, vector<PII>, greater<PII>> heap;

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dijkstra()
{
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int v = t.y;
        if (st[v]) continue;
        st[v] = true;

        for (int i = h[v]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[v] + w[i])
                dist[j] = dist[v] + w[i], heap.push({dist[j], j});
        }
    }
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }


    memset(dist, 0x3f, sizeof dist);

    int k;
    cin >> k;
    while (k--)
    {
        int x;
        scanf("%d", &x);
        dist[x] = 0;
        heap.push({0, x});
    }

    dijkstra();

    int q;
    cin >> q;
    while (q--)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", dist[x]);
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size())
    {
        auto tp = heap.top();
        heap.pop();

        int t = tp.y;
        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
                dist[j] = dist[t] + w[i], heap.push({dist[j], j});
        }
    }
}

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    dijkstra();

    if (dist[n] > 1e9) dist[n] = -1;
    cout << dist[n] << endl;

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; ++i)
    {
        int t = 0;
        for (int j = 1; j <= n; ++j)
            if (!st[j] && dist[j] < dist[t])
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; ++j)
            dist[j] = min(dist[j], dist[t] + g[t][j]);        
    }
}

int main()
{
    cin >> n >> m;

    memset(g, 0x3f, sizeof g);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    dijkstra();

    if (dist[n] >= 1e9) dist[n] = -1;
    cout << dist[n] << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m;
bool g[N][N];
int ind[N], q[N];
int sta[N];
bool st[N];

int toposort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; ++i)
        if (!ind[i])
            q[++tt] = i;

    int res = 0;
    while (hh <= tt)
    {
        int sz = tt - hh + 1;
        while (sz--)
        {
            auto &t = q[hh++];
            for (int i = 1; i <= n; ++i)
                if (g[t][i])
                    if (--ind[i] == 0) q[++tt] = i;
        }
        res++;
    }
    return res;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        memset(st, 0, sizeof st);

        int cnt;
        scanf("%d", &cnt);
        for (int j = 0; j < cnt; ++j)
        {
            scanf("%d", &sta[j]);
            if (j > 0 && j < cnt - 1) st[sta[j]] = true;
        }

        for (int j = sta[0] + 1; j < sta[cnt - 1]; ++j)
            if (!st[j])
                for (int k = 0; k < cnt; ++k)
                {
                    if (!g[sta[k]][j]) ind[j]++;
                    g[sta[k]][j] = true;
                }
    }

    cout << toposort() << endl;

    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

const int N = 110;

int n;
int ind[N], q[N];
vector<int> h[N];

void toposort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; ++i)
        if (!ind[i])
            q[++tt] = i;

    while (hh <= tt)
    {
        auto &t = q[hh++];
        for (auto &x : h[t])
            if (--ind[x] == 0)
                q[++tt] = x;
    }
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        int son;
        while (cin >> son && son)
            h[i].push_back(son), ind[son]++;
    }

    toposort();

    for (int i = 0; i < n; ++i) cout << q[i] << ' ';

    return 0;
}