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
164
165
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

struct talia
{
    bool wuzyciu = true;
    vector<int> wygrywaz;
    vector<int> przegrywaz;
};

int main()
{
    int t, n, m;
    vector<talia> wbajtka, wbitka;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQBajtka;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQBitka;

    int sumwbajtek, sumwbitek;

    int a, b;
    char w;
    
    scanf("%d", &t);

    while(t>0)
    {
        sumwbajtek = 0; sumwbitek = 0;
        wbajtka.clear(); wbitka.clear();

        scanf("%d %d", &n, &m);
        wbajtka.resize(n);
        wbitka.resize(n);

        for(int i = 0; i < m; ++i)
        {
            scanf("%d %c %d", &a, &w, &b);
            if (w == '>')
            {
                wbajtka[a-1].wygrywaz.push_back(b-1);
                wbitka[b-1].przegrywaz.push_back(a-1);
            }
            else
            {
                wbitka[b-1].wygrywaz.push_back(a-1);
                wbajtka[a-1].przegrywaz.push_back(b-1);
            }
        }

        for(int i = 0; i < n; ++i)
        {
            PQBitka.push(make_pair(wbitka[i].wygrywaz.size() * (-1) + wbitka[i].przegrywaz.size(), i));

            PQBajtka.push(make_pair(wbajtka[i].wygrywaz.size() * (-1) + wbajtka[i].przegrywaz.size(), i));
        }

        for(int i = 1; i < n; ++i) // O 1 zamiana za malo - zeby potem porownac
        {
            // RUCH BAJTKA
            auto p = PQBitka.top();
            while(wbitka[p.second].wuzyciu == false || p.first != (wbitka[p.second].wygrywaz.size() * (-1) + wbitka[p.second].przegrywaz.size())) // SPR czy zgadzaja sie dane
            {
                PQBitka.pop();
                p = PQBitka.top();
            }
            PQBitka.pop();

            //printf("Bajtek odrzucil: %d (%d)\n", p.second, p.first);
            wbitka[p.second].wuzyciu = false;
            for (auto x : wbitka[p.second].przegrywaz)
            {
                for(auto it = wbajtka[x].wygrywaz.begin(); it != wbajtka[x].wygrywaz.end(); ++it)
                    if (*it == p.second)
                    {
                        wbajtka[x].wygrywaz.erase(it);
                        PQBajtka.push(make_pair(wbajtka[x].wygrywaz.size() * (-1) + wbajtka[x].przegrywaz.size(), x));
                        //printf("bajtek +: %d (%d)\n", x, wbajtka[x].wygrywaz.size() * (-1) + wbajtka[x].przegrywaz.size());
                        
                        it = wbajtka[x].wygrywaz.end()-1;
                    }
            }

            for(auto x : wbitka[p.second].wygrywaz)
            {
                for(auto it = wbajtka[x].przegrywaz.begin(); it != wbajtka[x].przegrywaz.end(); ++it)
                    if (*it == p.second)
                    {
                        wbajtka[x].przegrywaz.erase(it);
                        PQBajtka.push(make_pair(wbajtka[x].wygrywaz.size() * (-1) + wbajtka[x].przegrywaz.size(), x));
                        //printf("bajtek +: %d (%d)\n", x, wbajtka[x].wygrywaz.size() * (-1) + wbajtka[x].przegrywaz.size());
                        
                        it = wbajtka[x].przegrywaz.end()-1;                        
                    }
            }

            // RUCH BITKA
            p = PQBajtka.top();
            while(wbajtka[p.second].wuzyciu == false || p.first != (wbajtka[p.second].wygrywaz.size() * (-1) + wbajtka[p.second].przegrywaz.size())) // SPR czy zgadzaja sie dane
            {
                PQBajtka.pop();
                p = PQBajtka.top();
            }
            PQBajtka.pop();

            //printf("Bitek odrzucil: %d (%d)\n", p.second, p.first);
            wbajtka[p.second].wuzyciu = false;
            for (auto x : wbajtka[p.second].przegrywaz)
            {
                for(auto it = wbitka[x].wygrywaz.begin(); it != wbitka[x].wygrywaz.end(); ++it)
                    if (*it == p.second)
                    {
                        wbitka[x].wygrywaz.erase(it);
                        PQBitka.push(make_pair(wbitka[x].wygrywaz.size() * (-1) + wbitka[x].przegrywaz.size(), x));
                        it = wbitka[x].wygrywaz.end() - 1;
                        //printf("bitek +: %d (%d)\n", x, wbitka[x].wygrywaz.size() * (-1) + wbitka[x].przegrywaz.size());
                        
                    }
            }

            for(auto x : wbajtka[p.second].wygrywaz)
            {
                for(auto it = wbitka[x].przegrywaz.begin(); it != wbitka[x].przegrywaz.end(); ++it)
                    if (*it == p.second)
                    {
                        wbitka[x].przegrywaz.erase(it);
                        PQBitka.push(make_pair(wbitka[x].wygrywaz.size() * (-1) + wbitka[x].przegrywaz.size(), x));
                        it = wbitka[x].przegrywaz.end() - 1;
                        //printf("bitek +: %d (%d)\n", x, wbitka[x].wygrywaz.size() * (-1) + wbitka[x].przegrywaz.size());
                                                
                    }
            }

        }

        // Ostatni ruch - szukamy ocalalych i sprawdzamy, kto wygrywa
        auto p = PQBajtka.top();
        while(wbajtka[p.second].wuzyciu == false)
        {
            PQBajtka.pop();
            p = PQBajtka.top();
        }
        PQBajtka.pop();

        //printf("W: %d (%d)\n", p.second, p.first);

        if (wbajtka[p.second].przegrywaz.size() == 0 && wbajtka[p.second].wygrywaz.size() == 0)
            printf("REMIS\n");
        else if (wbajtka[p.second].wygrywaz.size() > 0)
            printf("WYGRANA\n");
        else
            printf("PRZEGRANA\n");

        while(!PQBajtka.empty())
            PQBajtka.pop();
        
        while(!PQBitka.empty())
            PQBitka.pop();

        --t;
    }
    return 0;
}