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
#include <iostream>
#include <vector>
#include <map>
#include <cassert>
using namespace std;

// -1 przegrana
//  0 remis
//  1 wygrana
vector<int> karty_bajtka, karty_bitka;
map<pair<int,int>,int> wynik;

int ruch_bajtka();
int ruch_bitka();

int ruch_bajtka()
{
    int r;
    if(karty_bitka.size() == 1)
    {
        assert(karty_bajtka.size() == 1);
        auto w = wynik.find(make_pair(karty_bajtka[0], karty_bitka[0]));
        r = w == wynik.end() ? 0 : w->second;
        return r;
    }

    r = -2;


    assert(karty_bitka.size() > 1);
    for(size_t i=0; i<karty_bitka.size(); i++)
    {
        int store = karty_bitka[i];
        karty_bitka[i] = karty_bitka.back();
        karty_bitka.pop_back();
        r = max(r, ruch_bitka());
        karty_bitka.push_back(karty_bitka[i]);
        karty_bitka[i] = store;
    }
    return r;
}

int ruch_bitka()
{
    assert(karty_bajtka.size() > 1);
    int r = 2;
    for(size_t i=0; i<karty_bajtka.size(); i++)
    {
        int store = karty_bajtka[i];
        karty_bajtka[i] = karty_bajtka.back();
        karty_bajtka.pop_back();
        r = min(r, ruch_bajtka());
        karty_bajtka.push_back(karty_bajtka[i]);
        karty_bajtka[i] = store;
    }
    return r;
}

int main(int argc, char **argv)
{
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	for(; t>0; t--)
	{
		int n, m;

		cin >> n >> m;
        assert(1 <= n);
        assert(n <= 100000);
        assert(1 <= m);
        assert(m <= 200000);

        karty_bajtka.resize(n);
        karty_bitka.resize(n);
        for(int i=0; i<n; i++)
        {
            karty_bajtka[i] = karty_bitka[i] = i+1;
        }
        wynik.clear();

		for(int i=0; i<m; i++)
		{
			int a, b;
			char w;
			cin >> a >> w >> b;
			assert(a > 0);
			assert(a <= n);
			assert(w == '<' || w == '>');
			assert(b > 0);
			assert(b <= n);
            wynik[make_pair(a,b)] = w == '<' ? -1 : 1;
        }
        switch(int r = ruch_bajtka())
        {
        case -1: cout << "PRZEGRANA"     "\n"; break;
        case  0: cout << "REMIS"         "\n"; break;
        case  1: cout << "WYGRANA"       "\n"; break;
        default: cout << "BŁĄD " << r << "\n"; break;
        }
	}
	return 0;
}