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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <set>
#include <map>
using namespace std;

void wypisz(set<int> mr, set<int> jr,  map<int,set<int>>  mw,  map<int,set<int>>  jw,  map<int,set<int>>  mp,  map<int,set<int>>  jp)
{
#if defined (DEBUG)
printf("\nmr: ");
for(auto r : mr) printf("%d ",r);

printf("\njr: ");
for(auto r : jr) printf("%d ",r);

printf("\nmw:\n");
for(auto w : mw)
{
        printf("{%d}-> ",w.first);
        for(auto i : w.second) printf("%d ",i);
        printf("\n");
}

printf("\njw:\n");
for(auto w : jw)
{
        printf("{%d}-> ",w.first);
        for(auto i : w.second) printf("%d ",i);
}

printf("\nmp:\n");
for(auto w : mp)
{
        printf("{%d}-> ",w.first);
        for(auto i : w.second) printf("%d ",i);
}

printf("\njp:\n");
for(auto w : jp)
{
        printf("{%d}-> ",w.first);
        for(auto i : w.second) printf("%d ",i);
}

printf("\n");
#endif
}

void usun_strzalke(int ktory, int co, map<int,set<int>> &skad, set<int> &dokad)
{
	if(skad.find(ktory)!=skad.end())
	{
		skad[ktory].erase(co);
		if(skad[ktory].empty())
		{
			skad.erase(ktory);
			dokad.insert(ktory);
		}
	}
}

int main()
{
	int t,n,m,a,b;
	char c;
	scanf("%d",&t);
	while(t--)
	{
		set<int> mr,jr;
		map<int,set<int>> mw,mp,jw,jp;
		scanf("%d%d",&n,&m);
//printf("n %d m %d\n",n,m);
		for(int i=1;i<=n;i++)
		{
			mr.insert(i);
			jr.insert(i);
		}
		while(m--)
		{
			scanf("%d %c %d",&a,&c,&b);
			if(c=='<')
			{
				mr.erase(a);
				jr.erase(b);
				mp[a].insert(b);
				jw[b].insert(a);
			}
			else
			{
				mr.erase(a);
				jr.erase(b);
				mw[a].insert(b);
				jp[b].insert(a);
			}
		}


		wypisz(mr,jr,mw,jw,mp,jp);

		while (jw.size() + jr.size() + jp.size() >1)
		{
//		printf("while\n");
			if(jw.size()>0)
			{
				int w = jw.begin()->first;
				for( auto i : jw.begin()->second )
					usun_strzalke(i,w,mp,mr);
				for( auto i : jp[w])
					usun_strzalke(i, w, mw,mr);
				jp.erase(w);
				jw.erase(w);
			} else if (jr.size()>0)
			{
				jr.erase(*jr.begin());
			} else if(jp.size()>0)
			{
                                int w = jp.begin()->first;
                                for( auto i : jp.begin()->second )
					usun_strzalke(i,w,mw,mr);
                                for( auto i : jw[w])
					usun_strzalke(i,w,mp,mr);
                                jp.erase(w);
                                jw.erase(w);
			}
//			else printf("ERROR1\n");

                        if(mw.size()>0)
                        {
                                int w = mw.begin()->first;
                                for( auto i : mw.begin()->second )
					usun_strzalke(i,w,jp,jr);
                                for( auto i : mp[w])
					usun_strzalke(i,w,jw,jr);
                                mp.erase(w);
                                mw.erase(w);
                        } else if (mr.size()>0)
                        {       
                                mr.erase(*mr.begin());
                        } else if(mp.size()>0)
                        {
                                int w = mp.begin()->first;
                                for( auto i : mp.begin()->second )
					usun_strzalke(i,w,jw,jr);
                                for( auto i : mw[w])
					usun_strzalke(i,w,jp,jr);
                                mp.erase(w);
                                mw.erase(w);
                        }
//			else printf("ERROR2\n");

		}
		                wypisz(mr,jr,mw,jw,mp,jp);
		if(!mw.empty())
		{
			printf("WYGRANA\n");
		}
		else if(!mp.empty())
		{
			printf("PRZEGRANA\n");
		}
		else printf("REMIS\n");
	}
	return 0;
}