1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include <vector>
#include <stdexcept>
#define ll long long
using namespace std;

vector<vector<int> > G;
vector<vector<int> > RG;
int n;
vector<vector<int> >M;
int win(int left, int m1, int m2) {
    int res = -11;
    if(M[m1][m2]!=8)return M[m1][m2];
    for(int b=0;b<n;b++) {
        if ((m2&(1<<b)) !=0 ) continue;
        int r1=1;
        for(int a=0;a<n;a++) {
            if ((m1&(1<<a)) !=0 ) continue;
            if(left==1) {
                if(find(G[a].begin(), G[a].end(), b)!=G[a].end()) return 1;
                else if (find(RG[b].begin(), RG[b].end(), a)!=RG[b].end()) return -1;
                return 0;
            } else {
                r1 = min(r1, win(left-1, m1|(1<<a), m2|(1<<b)));
            }
        }
        res = max(r1,res);
    }
    return M[m1][m2]=res;
}



void solve_brut() {
    M.resize(1<<n);
    for(int i=0;i<1<<n;i++){
        M[i].resize(1<<n);
        fill(M[i].begin(), M[i].end(),8);
    }
    int r = win(n, 0,0);

    if(r==1)cout<<"WYGRANA\n";
    if(r==-1)cout<<"PRZEGRANA\n";
    if(r==0)cout<<"REMIS\n";
}

void test () {
    istream& my_in = cin;
    //ifstream my_in; my_in.open("karrand.in");
    int t=0;
    my_in >> t;
    while(t--) {
        int  m;
        my_in >> n >> m;

        G.resize(n);
        RG.resize(n);
        for(int i=0;i<n;i++){
            G[i].resize(0);
            RG[i].resize(0);
        }
        for(int i=0;i<m;i++) {
            int a=-1,b=-1;
            char c =0;
            my_in >> a>>c>>b;
            a--;b--;
            if(c=='<') {
                RG[b].push_back(a);
      //          cout << a+1 <<"<"<<b+1<<endl;
            }else if(c=='>') {
                G[a].push_back(b);
         //       cout << a+1 <<">"<<b+1<<endl;
            } else {
                throw std::invalid_argument(""+c);
            }
        }
        solve_brut();
    //    cout << "-------------\n";
    }

}
int main() {
    std::ios::sync_with_stdio(false);
    istream& my_in = cin;
     int t=0;
    my_in >> t;
    while(t--) {
        int  m;
        my_in >> n >> m;
        vector<int>A(n,0);
        vector<int>B(n,0);
        for(int i=0;i<m;i++) {
            int a=-1,b=-1;
            char c =0;
            my_in >> a>>c>>b;
            a--;b--;
            if(c=='<') {
                B[b]++;
            }else if(c=='>') {
                A[b]++;
            } else {
                throw std::invalid_argument(""+c);
            }
        }
        bool win = false;
        bool loss = true;
        for(int i=0;i<n;i++) {
            if(A[i]==n)win = true;
            if(B[i]==0)loss = false;
        }
        if(win)cout <<"WYGRANA\n";
        else if (loss)cout <<"PRZEGRANA\n";
        else cout << "REMIS\n";

    }
    return 0;
}