已经确认是判二分图这里写TLE了，但是这里应该是O（n+m）的时间复杂度来着，求救大佬们 用的是

https://www.cnblogs.com/dx123/p/16418198.html

这里的二分图判定

#include<bits/stdc++.h>
using namespace std;
int _;
#define p 1e9+7
const int N = 1e4 + 10;
struct node {
   int v, ne;
}e[N];
int h[N];
int color[N];
int idx;
void add(int a, int b) {
   e[++idx] = { b,h[a] };
   h[a] = idx;
}
bool dfs(int u, int c) {//节点和颜色
   color[u] = c;
   for (int i = h[u]; i; i = e[i].ne) {
       int v = e[i].v;
       if (!color[v]) {
           if (dfs(v, 3 - c)) {
               return 1;
           }
       }
       else if (color[v] == c) {
           return 1;
       }
       
   }
   return 0;
}

void solve() {
   idx = 0;
   int n, m; cin >> n >> m;
   for(int i=1;i<=n;++i) color[i]=0;
   for(int i=1;i<=n;++i) h[i]=0;
   for(int i=1;i<=m;++i) e[i].v=0,e[i].ne=0;
   for (int i = 1; i <= m; ++i) {
       int x, y; cin >> x >> y;
       add(x, y);
       add(y, x);
   }
   bool flag=0;//0就是有二分图

   for(int i=1;i<=n;++i){
       if(!color[i]){
           if(dfs(i,1)){
               flag=1;
               break;
           }
       }
   }

   if (flag) {//不存在二分图，alice随便赢
       cout << "Alice" << endl;
       for (int i = 1; i <= n; ++i) {
           int x, y;
           cout << 1 << ' ' << 2 << endl;
           cin >> x >> y;
       }
   }
   else {
       vector<int> ac;
       vector<int> bc;
       for (int i = 1; i <= n; ++i) {
           if (color[i] == 1) ac.push_back(i);
           else bc.push_back(i);
       }
       cout << "Bob" << endl;
       for (int q = 1; q <= n; ++q) {
           int x, y;
           cin >> x >> y;
           if (x == 1 || y == 1) {
               if (!ac.empty()) {
                   cout << *ac.rbegin() << " " << 1 << endl;
                   ac.pop_back();
                   continue;
               }
           }
           if (x == 2 || y == 2) {
               if (!bc.empty()) {
                   cout << *bc.rbegin() << " " << 2 << endl;
                   bc.pop_back();
                   continue;
               }
           }
           if (ac.empty()) {
               cout << *bc.rbegin() << " " << 3 << endl;
               bc.pop_back();
           }
           else {
               cout << *ac.rbegin() << " " << 3 << endl;
               ac.pop_back();
           }
       }
   }


}

signed main() {
   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
   cin >> _;
   while (_--) {
       solve();
   }
   return 0;

}