#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;

void bfs(vector<vector<int>>& adj, vector<int>& dist, int v){
    queue<int> q;
    q.push(v);
    dist[v]=0;
    while(!q.empty()){
        int v=q.front();q.pop();
        for(int u:adj[v])if(dist[u]==-1){
            dist[u]=dist[v]+1;
            q.push(u);
        }
    }
}

int main(){
    int n,m,a,b;cin>>n>>m>>a>>b;
    vector<vector<int>> adj(n+1);
    for(int i=0;i<m;i++){
        int v,u;cin>>v>>u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    vector<int> dista(n+1,-1), distb(n+1,-1);
    bfs(adj, dista, a);
    bfs(adj, distb, b);

    vector<char> ans(n+1, 'B');
    vector<pii> diff(n);
    long long cost=0;
    for(int i=1;i<=n;i++){
        diff[i-1]={dista[i]-distb[i], i};
        cost+=distb[i];
    }
    sort(diff.begin(),diff.end());
    for(int i=0;i<n/2;i++){
        ans[diff[i].second]='A';
        cost+=diff[i].first;
    }
    cout<<cost<<'\n';
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';cout<<'\n';
}