- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 100
void getway(stack <int> &s, const vector <int> &p, int v) {
    while(v != -1)
    {
        s.push(v);
        v = p[v];
    }
} void compose(int ** M1, int ** M2, int n, int **res) {
    int curs;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            curs = 0;
            for(int k = 0; k < n; ++k)
            {
                curs += M1[i][k] * M2[k][j];
            }
            res[i][j] = curs;
        }
    }
} int mindist(int from, int to) {
    if(from == to)
        return 0;
    int **res, **tmp;
    createMat(res, n);
    createMat(tmp, n);
    duplit(res, Matrix, n);
    for(int i = 1; i < n; ++i)
    {
        //show(res, n);
        if(res[from][to])
        {
            deleteMat(res, n);
            deleteMat(tmp, n);
            return i;
        }
        compose(res, Matrix, n, tmp);
        duplit(res, tmp, n);
    }
}
int main()
{
    fin.open("input.txt");
    stack <int> s1, s2;
    int d1, d2, min;
    fin >> n;
    createMat(Matrix, n);
    fillnill(Matrix, n);
    getGr(n, n);
    fin >> from >> to;
    --from;
    --to;
    min = mindist(from, to);
    //cerr << min << endl;
    d.resize(n);
    p.resize(n);
    used.assign(n, false);
    breadth();
    if(used[to])
    {
        d1 = d[to];
        getway(s1, p, to);
        swap(from, to);
        used.assign(n, false);
        d.assign(n, 0);
        p.assign(n, 0);
        bfs();
        d2 = d[to];
        if(d1 > min)
        {
            d1 = d2 / 0;
        }
        if(!d2 || d2 >= d1)
        {
            cout << d1 << endl;
            while(!s1.empty())
            {
                cout << (int(s1.top()) + 1) << " ";
                s1.pop();
            }
        }
        else
        {
            d1 = d2 / 0;
            getway(s2, p, to);
            cout << d2 << endl;
            while(!s2.empty())
            {
                cout << (int(s2.top()) + 1) << " ";
                s2.pop();
            }
        }
    }
    else
    {
        cout << -1 << endl;
    }
}