cycle find

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > grafo;
vector<pair<int, int> > env;

bool cf(int start){
    env[start].second = true;
    env[start].first = true;
    for(int i = 0;i < grafo[start].size(); i++){
        if(!env[grafo[start][i]].first){
            if (cf(grafo[start][i])) return true;
        } if (env[grafo[start][i]].second) return true;
    }
    env[start].second = false;
    return false;
}

string resp(int N){
    for(int i = 1; i <= N; i++){
        if(!env[i].first){
            if(cf(i)) return "SIM";
        }
    }
    return "NAO";
}
int main(){
    int cases, N, M;
    scanf("%d", &cases);
    while(cases--){
        scanf("%d %d", &N, &M);
        grafo.assign(N+1, vector<int> ());
        env.assign(N+1, make_pair(0,0));
        while(M--){
            int A, B;
            scanf("%d %d", &A, &B);
            grafo[A].push_back(B);
        }
        cout << resp(N) << endl;
        grafo.clear();
        env.clear();
    }
}