#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

const int nmax=7500;
int vas[nmax+5],frecv[nmax+5],frecv2[nmax+5],vas2[nmax+5];
int n,m,X,Y;
vector<vector<int>> graf;
vector<int> ve;

void bfs(int x,int y){
    deque<int>q;
    q.push_back(x);
    vas[x]=1;
    frecv[x]=1;
    while(!q.empty()){
        int t;
        t=q.front();
        q.pop_front();
        for(int i:graf[t]){
            if(vas[t]<vas[i]){
                frecv[i]+=frecv[t];
            }
            else if(!vas[i]){
                q.push_back(i);
                vas[i]=1+vas[t];
                frecv[i]+=frecv[t];
            }

        }
    }
}
void bfs2(int x,int y){
    deque<int>q;
    q.push_back(x);

    vas2[x]=1;
    frecv2[x]=1;
    while(!q.empty()){
        int t;
        t=q.front();
        q.pop_front();
        for(int i:graf[t]){
            if(vas2[t]+1==vas2[i]){
                frecv2[i]+=frecv2[t];
            }
            else if(!vas2[i]){
                q.push_back(i);
                vas2[i]=1+vas2[t];
                frecv2[i]+=frecv2[t];
            }

        }
    }
}


void tat(int x,int y){
    for(int i=1;i<=n;i++){
        cout<<frecv[i]<<" "<<frecv2[i]<<'\n';
        if(frecv[i]*frecv2[i]==frecv[y]&&vas[i]+vas2[i]==vas[y]+1)ve.push_back(i);
    }
    sort(ve.begin(),ve.end());
    fout<<ve.size()<<'\n';
    for(auto i=ve.begin();i!=ve.end();i++){
        fout<<*i<<" ";
    }
}



int main()
{
    fin>>n>>m>>X>>Y;
    graf.assign(n+1,vector<int>());

    for(int i=1;i<=m;i++){
            int x,y;
        fin>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    bfs(X,Y);
    bfs2(Y,X);
    tat(X,Y);

}