graf1

#include <bits/stdc++.h>

using namespace std;

ifstream fin("graf1.in");
ofstream fout("graf1.out");

int n, m, start, stop;

vector < int > lis[7501];
vector < int > rez;
bitset < 7501 > viz;
vector < int > ap;

int lMin = INT_MAX;

void dfs(int l, int nod, int antnod, int cate = 0)
{
    viz[nod] = 1;
    rez.push_back(nod);
    cout << antnod << ' ' <<  nod << ' ' << l << '\n';

    if(nod == stop)
    {
        cout << cate << '\n';
        if(l < lMin)
        {
            ap.clear();
            for(int el : rez)
                ap[el]++;

            lMin = l;
        }
        else if(l == lMin)
        {
            for(int el : rez)
                ap[el]++;
        }

        return;
    }

    if(l >= lMin)
        return;

    for(int vecin : lis[nod])
    {
        if(!viz[vecin])
        {
            dfs(l + 1, vecin, nod, cate + 1);
            rez.pop_back();
        }
    }
    viz[nod] = 0;
}

int main()
{
    ap.resize(7501);

    fin >> n >> m >> start >> stop;

    int a, b;

    while(m--)
    {
        fin >> a >> b;
        lis[a].push_back(b);
        lis[b].push_back(a);
    }

    dfs(1, start, 0);

    int c = 0;

    for(int i = 1; i <= n; i++)
        fout << i << ' ' << ap[i] << '\n', c++;

    fout << c;

    fin.close();
    fout.close();
    return 0;
}