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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define MAX 100007
#define REP(x,n) for (int x = 0; x < (n); x++)
#define FOR(x,b,e) for (int x = (b); x <= (e); x++)
#define LL long long
#define ULL unsigned long long
#define MP std::make_pair
#define ST first
#define ND second

typedef std::pair<int, int>  PII;


struct classcomp {
	bool operator() (const PII& lhs, const PII& rhs) const{	
	  	if (lhs.ST != rhs.ST)
	  		return lhs.ST > rhs.ST;
	  	else
	  		return lhs.ND < rhs.ND;
	  }
};


int main(){
	std::set<PII, classcomp> neighbours_a_set, neighbours_b_set;                 // class as Compare

	int t, n, m;
	int a, b;
	char c;
	int neighbours_a_arr[MAX], neighbours_b_arr[MAX];

	vector<int> rev_neighbours_a_arr[MAX], rev_neighbours_b_arr[MAX];
	scanf("%d", &t);
	REP(iter, t){
		scanf("%d%d", &n, &m);
		REP(x, n+5){
			neighbours_a_arr[x]=0;
			neighbours_b_arr[x]=0;
			rev_neighbours_a_arr[x].clear();
			rev_neighbours_b_arr[x].clear();
			neighbours_a_set.clear();
			neighbours_b_set.clear();
		}

		REP(i, m){
			scanf("%d %c %d", &a, &c, &b);
			if(c == '>'){
				neighbours_a_arr[a]++;
				rev_neighbours_b_arr[b].push_back(a);

			}
			else
				neighbours_b_arr[b]++;
				rev_neighbours_a_arr[a].push_back(b);
		}

		for (int i=1; i< n+1; i++){

			int s_a = neighbours_a_arr[i];
			if (s_a > 0)
				neighbours_a_set.insert(MP(s_a, i));

			int s_b = neighbours_b_arr[i];
			if (s_b > 0)
				neighbours_b_set.insert(MP(s_b, i));


		}




		auto r = neighbours_a_set.begin();
		PII p = *r;

		int counter = 0;
		while((neighbours_a_set.size() > 0 || neighbours_b_set.size() > 0) && counter < n-1){

			if(neighbours_b_set.size() > 0){
				PII elem_b = *(neighbours_b_set.begin());
				std::vector<int> v = rev_neighbours_b_arr[elem_b.ND];
				for (std::vector<int>::iterator it = v.begin() ; it != v.end(); ++it){
					//printf("AA:%d %d\n", *it, neighbours_a_arr[*it]);

					if (neighbours_a_arr[*it] > 0){
			  			int val = neighbours_a_arr[*it]--;
			  			//printf("BB:%d %d\n", val ,*it);

			  			neighbours_a_set.erase(MP(val ,*it));
			  			if (val-1 > 0)
			  				neighbours_a_set.insert(MP(--val ,*it));
		  			}
				}
				 neighbours_b_arr[elem_b.ND] = 0;
				 neighbours_b_set.erase(neighbours_b_set.begin());
			}





		 	if(neighbours_a_set.size()==0)
		 		continue;
			PII elem_a = *(neighbours_a_set.begin());
			std::vector<int> v = rev_neighbours_a_arr[elem_a.ND];
			for (std::vector<int>::iterator it = v.begin() ; it != v.end(); ++it){
				if (neighbours_b_arr[*it] > 0){
		  			int val = neighbours_b_arr[*it]--;
		  			neighbours_b_set.erase(MP(val ,*it));
		  			if (val-1 > 0)
		  				neighbours_b_set.insert(MP((val-1) ,*it));
	  			}
			}
			neighbours_a_arr[elem_a.ND] = 0;
			neighbours_a_set.erase(neighbours_a_set.begin());




			counter++;
		}
		if (neighbours_a_set.size() > 0 && neighbours_b_set.size() == 0)
			printf("WYGRANA\n");
		else if (neighbours_a_set.size() == 0 && neighbours_b_set.size() > 0)
			printf("PRZEGRANA\n");
		else 
			printf("REMIS\n");
	}
	return 0;
}