vjudge

luogu

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=1e5+10;
ll n,m,age[maxn];
#define AT(x) (x)
#define BT(x) (x+n)
#define CT(x) (x+n*2)
vector<int>g[maxn*3];

int dfn[maxn*3+100],low[maxn*3+100],cnt,belong[maxn*3+100],scc;
stack<int>st;
bool instack[maxn*3];
void tarjan(int u){
	low[u]=dfn[u]=++cnt;
	st.push(u);instack[u]=1;
	for(int v:g[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(instack[v])low[u]=min(low[u],low[v]);
	}
	if(dfn[u]==low[u]){
		++scc;
		while(1){
			int v=st.top();
			st.pop();
			instack[v]=0;
			belong[v]=scc;
			if(v==u)break;
		}
	}return ;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int asi,asj;ll X=0;
	while(cin>>n>>m){
		if(n==0&&m==0)return 0;
		for(int i=1;i<=3*n;++i)g[i].clear(),low[i]=dfn[i]=belong[i]=instack[i]=0;
		scc=cnt=X=0;
		for(int i=1;i<=n;++i)cin>>age[i],X+=age[i];
		for(int i=1;i<=m;++i){
			cin>>asi>>asj;
			if(1ll*age[asi]*n>=X&&1ll*age[asj]*n>=X)g[AT(asi)].push_back(CT(asj)),g[AT(asj)].push_back(CT(asi)),g[CT(asi)].push_back(AT(asj)),g[CT(asj)].push_back(AT(asi));
			else if(1ll*age[asi]*n>=X&&1ll*age[asj]*n<X)g[CT(asi)].push_back(BT(asj)),g[CT(asj)].push_back(AT(asi));
			else if(1ll*age[asi]*n<X&&1ll*age[asj]*n>=X)g[CT(asi)].push_back(AT(asj)),g[CT(asj)].push_back(BT(asi));
			else if(1ll*age[asi]*n<X&&1ll*age[asj]*n<X)g[BT(asi)].push_back(CT(asj)),g[BT(asj)].push_back(CT(asi)),g[CT(asi)].push_back(BT(asj)),g[CT(asj)].push_back(BT(asi));
		}
	
		for(int i=1;i<=n*3;++i)if(!dfn[i])tarjan(i);
		
		for(int i=1;i<=n;++i){
			if(1ll*age[i]*n>=X){
				if(belong[AT(i)]==belong[CT(i)]){
					cout<<"No solution.\n";
					return 0;
				}
			}else if(1ll*age[i]*n<X){
				if(belong[BT(i)]==belong[CT(i)]){
					cout<<"No solution.\n";
					return 0;
				}	
			}
			if(belong[AT(i)]==belong[BT(i)]){
				cout<<"No solution.\n";
				return 0;
			}
			
		}
			
		for(int i=1;i<=n;++i){
			if(1ll*age[i]*n>=X){
				if(belong[AT(i)]<belong[CT(i)])cout<<"A\n";
				else cout<<"C\n";
			}if(1ll*age[i]*n<X){
				if(belong[BT(i)]<belong[CT(i)])cout<<"B\n";
				else cout<<"C\n";
			}
		}
	}
	return 0;
} 
/*
 16 20
 21
 22
 23
 24
 25
 26
 27
 28
 101
 102
 103
 104
 105
 106
 107
 108
 1 2
 3 4
 5 6
 7 8
 9 10
 11 12
 13 14
 15 16
 1 10
 2 9
 3 12
 4 11
 5 14
 6 13
 7 16
 8 15
 1 12
 1 13
 3 16
 6 15
 0 0
*/