mesa.cpp

#include <bits/stdc++.h>

using namespace std;
const int maxn = 110;
vector<int> grafo[maxn];
int cor[maxn];

void bfs(int l){
    cor[l] = 0;
    queue<int> fila;
    fila.push(l);
    while(!fila.empty()){
        int u=fila.front();
        fila.pop();

        for(auto v : grafo[u]){
            if(cor[v] == -1){
                cor[v] = !cor[u];
                fila.push(v);
            }
        }
    }
}

bool bipartido(int n){
    for(int i=1;i<=n;i++){
        if(cor[i] == -1)
            bfs(i);
    }
    for(int u=1;u<=n;u++){
        for(auto v : grafo[u]){
            if(cor[v] == cor[u]) return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    int k=0;

    while(cin >> n >> m && n+m){
        memset(cor, -1, sizeof cor);
        for(int i=0;i<maxn;i++) grafo[i].clear();

        for(int i=1;i<=m;i++){
            int a, b;
            cin >> a >> b;
            grafo[a].push_back(b);
            grafo[b].push_back(a);
        }

        cout << "Instancia " << ++k << "\n";
        cout << (bipartido(n) ? "sim" : "nao") << "\n\n";
    }



    return 0;
}