老虎和蒜头是好朋友。
一天老虎在黑板上画了一个无向连通图，然后他跟蒜头说，我能把这个图的点用四种颜色染色，满足相邻点不同色。
蒜头不服气，在黑板上画了一个五个点的完全图。老虎跟蒜头说，这个图我能找到一个奇环，并且删掉这个奇环上的边之后图仍然联通。
蒜头发现他构不出反例了。蒜头很生气，他想让你也来解决一下这个问题。
一句话题意：对于一个无重边无自环的连通无向图，你可以选择两件事之一：把它的每个点用1 2 3 4这四种颜色染色，满足有边相连的点不同色；找到一个不重复顶点序列 v 1 , v 2 ⋯ v k v_1,v_2 \cdots v_k v1,v2⋯vk ( k ≥ 3 , k ≥ 3 , k 为 奇 数 ) ( k \ge 3,k≥3,k 为奇数) (k≥3,k≥3,k为奇数)满足相邻两个点之间有边，并且删掉这个环上的边之后图仍然联通。如果这两件事都干不了，请输出一行wxh ak ioi2019（这显然是事实）。
四色问题不可能直接解决，于是考虑奇环的特殊性。
发现若存在奇环，就输出。
若不存在，那么原图非树边必然构成二分图，那么奇偶染色就可以了。
最后并上原树的颜色即可。
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int read(){
int op=1,sum=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') op=-1;ch=getchar();}
while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+ch-'0',ch=getchar();
return op*sum;
}
int n,m,fa[N];
struct node{
vector<int> to[N];
int cl[N],sta[N],top,fr[N],dep[N];
inline void init(){
for(int i=1;i<=n;++i)cl[i]=-1;
top=0;sta[0]=0;
}
inline void add(int x,int y){
to[x].push_back(y);to[y].push_back(x);
}
void dfs(int x,int las){
sta[++top]=x;
for(int i=0;i<to[x].size();++i){
int y=to[x][i];
if(y==las)continue;
if(cl[y]==-1){
cl[y]=(cl[x]^1);
fr[y]=x;dep[y]=dep[x]+1;
dfs(y,x);
}else{
if(cl[x]==cl[y]){
printf("B %d ",dep[x]-dep[y]+1);
for(int j=x;j!=y;j=fr[j])printf("%d ",j);
printf("%d\n",y);
exit(0);
}
}
}
--top;
}
void work(){
init();
for(int i=1;i<=n;++i){
if(cl[i]==-1){
cl[i]=0;fr[i]=0;dep[i]=1;
dfs(i,0);
}
}
}
}T[2];
inline int get(int x){return fa[x]^x?fa[x]=get(fa[x]):x;}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<=m;++i){
int x=read(),y=read(),fx=get(x),fy=get(y);
if(fx^fy){
fa[fx]=fy;T[0].add(x,y);
}else{
T[1].add(x,y);
}
}
T[1].work();
T[0].work();
printf("A ");
for(int i=1;i<=n;++i){
T[1].cl[i]=max(T[1].cl[i],0);
printf("%d ",((T[0].cl[i]<<1)|T[1].cl[i])+1);
}
return 0;
}