Submission #71015240

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j, k) for(int i = (j); i >= (k); i--)
#define pb emplace_back
#define fi first
#define se second
using vi = vector<int>;
using pi = pair<int, int>;

template<typename T0, typename T1> bool chmin(T0 &x, const T1 &y){
	if(y < x){x = y; return true;} return false;
}
template<typename T0, typename T1> bool chmax(T0 &x, const T1 &y){
	if(x < y){x = y; return true;} return false;
}

template<typename T> void debug(char *s, T x){
	cerr << s <<" = "<< x <<endl;
}
template<typename T, typename ...Ar> void debug(char *s, T x, Ar... y){
	int dep = 0;
	while(!(*s == ',' && dep == 0)){
		if(*s == '(') dep++;
		if(*s == ')') dep--;
		cerr << *s++;
	}
	cerr <<" = "<< x <<",";
	debug(s + 1, y...);
}
#define gdb(...) debug((char*)#__VA_ARGS__, __VA_ARGS__)

void solve(){
	int n, m;
	cin >> n >> m;
	vector<vi> G(n);
	rep(i, 0, m - 1){
		int u, v;
		cin >> u >> v;
		u --, v --;
		G[u].pb(v);
		G[v].pb(u);
	}
	if(n % 2 == 1){
		cout << "Bob\n";
		return;
	}
	int cnt_0 = 0, cnt_2 = 0;
	vi cnt(n);
	rep(i, 0, n - 1){
		cnt_0 += (G[i].size() == 0);
		if(G[i].size() == 1){
			if(G[ G[i][0] ].size() == 1){
				cnt_2 ++;
			} else{
				cnt[ G[i][0] ] ++;
			}
		}
	}
	if(*max_element(cnt.begin(), cnt.end()) + 1 + cnt_0 + cnt_2 == n){
		cout << "Alice\n";
	} else{
		cout << "Bob\n";
	}
}
signed main(){
	#ifdef LOCAL
	assert( freopen(".in", "r", stdin) );
	assert( freopen(".out", "w", stdout) );
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t --){
		solve();
	}
}

Submission Info

Judge Result