minhocão

#include <bits/stdc++.h>

using namespace std;
bool vis[3007];
vector<int> grafo[3007];
int planetas, kek;

void dfs(int no){
    vis[no] = true;
    kek++;
    for(int i = 0; i < grafo[no].size(); i++){
        if(!vis[grafo[no][i]]){
            dfs(grafo[no][i]);
        }
    }
}

int resp(){
    if(kek < planetas) {
        printf("N\n");
        return 0;
    }
    kek = 0;
    for(int i = 0; i < planetas; i++) vis[i] = 0;
    dfs(planetas);
    if(kek < planetas) {
        printf("N\n");
        return 0;
    }

    printf("S\n");
    return 0;
}

int main(){
    int cont = 1;
    while(true){
        int buracos;
        kek = 0;
        scanf("%d %d", &planetas, &buracos);
        if(!(planetas + buracos)) break;

        for(int i = 1; i <= planetas; i++) {
            grafo[i].clear();
            vis[i] = 0;
        }
        for(int i = 0; i < buracos; i++){
            int x, y;
            cin >> x >> y;
            grafo[x].push_back(y);
        }
        printf("Teste %d\n", cont++);
        dfs(1);
        resp();
        printf("\n");
    }
    return 0;
}