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
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100000;
int t, n, m;

int g[2][MAXN];
vector<int> in[2][MAXN];
vector<int> out[2][MAXN];

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;

        for (int z = 0; z < 2; z++) {
            for (int i = 0; i < n; i++) {
                g[z][i] = 0;
                in[z][i].clear();
                out[z][i].clear();
            }
        }

        for (int i = 0; i < m; i++) {
            int x, y;
            string s;
            cin >> x >> s >> y;
            x--; y--;
            if (s == ">") {
                out[0][x].push_back(y);
                in[1][y].push_back(x);

                g[0][x]++;
                g[1][y]--;
            } else {
                out[1][y].push_back(x);
                in[0][x].push_back(y);

                g[0][x]--;
                g[1][y]++;
            }
        }

        set<pair<int, int>> S[2];

        for (int i = 0; i < n; i++) {
            S[0].insert({-g[0][i], i});
            S[1].insert({-g[1][i], i});
        }

        for (int i = 0; i < n - 1; i++) {
            for (int p = 0; p < 2; p++) {
                int q = 1 - p;
                auto z = *S[q].begin();
                S[q].erase(S[q].begin());
                int j = z.second;
                //cerr << p << " " << j << " " << -z.first << "\n";

                for (auto x: out[q][j]) {
                    auto it = S[p].find({-g[p][x], x});
                    if (it == S[p].end() || it->second != x) continue;
                    S[p].erase(it);
                    g[p][x]++;
                    S[p].insert({-g[p][x], x});
                }
                for (auto x: in[q][j]) {
                    auto it = S[p].find({-g[p][x], x});
                    if (it == S[p].end() || it->second != x) continue;
                    S[p].erase(it);
                    g[p][x]--;
                    S[p].insert({-g[p][x], x});
                }
            }
        }

        int res = -S[0].begin()->first;
        if (res < 0) cout << "PRZEGRANA\n";
        else if (res > 0) cout << "WYGRANA\n";
        else cout << "REMIS\n";


    }
    return 0;
}