#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
#define lowbit(x) (x&(-x))
typedef long long LL;
typedef unsigned long long ull;
int n, m, k;
const int N = 1e6 + 10, M = 2e5, mod = 998244353;
int inf;
int num[N], book[N];
int res, cnt;


int h[N],e[N<<1],ne[N<<1],idx;
int dp[N][2],dep[N],du[N];
bool flag=1;
void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void meg(int id,vector<pll> pl)
{
	dp[id][0]=1,dp[id][1]=0;
	if(pl.size()==1) dp[id][0]+=pl[0].fi*2,dp[id][1]+=pl[0].se;
	else if(pl.size()==2)
	{
		dp[id][0]+=pl[0].fi*2+pl[1].fi*2;
		dp[id][1]+=pl[0].se+pl[1].se+min(pl[0].fi,pl[1].fi);
	}
	dp[id][0]=min(dp[id][0],inf);
	dp[id][1]=min(dp[id][1],inf);
	
}

void dfs(int id,int f)
{
	vector<pll> pl;
	dep[id]=0;
	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		dfs(j,id);
		dep[id]=max(dep[id],dep[j]+1);
		pl.push_back({dp[j][0],dp[j][1]});
	}
	meg(id,pl);
//	cout<<"A : " <<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
}

void DFS(int id,int f,int a,int b,int dap)
{
	int tp=max(dep[id],dap);
	
	vector<pll> pl;
	if(f!=-1) pl.push_back({a,b});
	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		pl.push_back({dp[j][0],dp[j][1]});
	}
	if(pl.size()<=2)
	{
		 meg(id,pl);
	//	 cout<<"B : "<<id<<" "<<dp[id][0]<<" "<<dp[id][1]<<endl;
	}
	int ans=inf;
	if(du[id]==2&&tp<=31) ans=min(ans,dp[id][0]+dp[id][1]),cout<<"A\n";
	else if(du[id]==1&&tp<=32) ans=min(ans,pl[0].fi+pl[0].se),cout<<"B\n";
	if(ans>=0&&ans<res) res=ans;
	
	for(int i=h[id];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==f) continue;
		pl.clear();
		if(f!=-1) pl.push_back({a,b});
		int tp=dap;
		for(int ii=h[id];ii!=-1;ii=ne[ii])
		{
			int jj=e[ii];
			if(jj==f||jj==j) continue;
			pl.push_back({dp[jj][0],dp[jj][1]});
			tp=max(tp,dep[jj]);
		}
		meg(id,pl);
		DFS(j,id,dp[id][0],dp[id][1],tp+1);
	}
}

void solve() {
	cin>>n>>m;
	inf=(1ll<<32)*200000;
	if(n==1)
	{
		cout<<"0\n";
		return;
	}
	if(m!=n-1) flag=0;
	memset(h,-1,sizeof h);
	int rt=1;
	int bk=-1;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		if(bk==-1) bk=a;
		add(a,b);
		add(b,a);
		du[a]++,du[b]++;
		if(du[a]==4||du[b]==4) flag=0;
	}
	for(int i=1;i<=n;i++)
	{
		 if(du[i]==1) 
		 {
		 	rt=i;
		 	break;
		 }
	}
	if(flag)
	{
		res=inf;
		dfs(rt,-1),
		DFS(rt,-1,0,0,0);
	}
	if(res==inf) flag=0;
	if(flag) cout<<res<<endl;
	else cout<<"NIE\n";
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}
/*
63 62
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
*/