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
166
167
168
169
170
171
172
173
174
175
176
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * Created by michal on 21.11.16.
 */

public class kar {
    static class Graph {
        private final int playerCardCount; //number of cards per player
        private final int edges;

        private Player[][] graph;

        Graph(int cardCount, int edges) {
            this.playerCardCount = cardCount;
            this.edges = edges;
            this.graph = new Player[cardCount][];
        }

        void addEdge(int x, int y, Player p) {
            if (this.graph[x-1] == null) {
                this.graph[x-1] = new Player[playerCardCount];
            }
            this.graph[x-1][y-1] = p;
        }

    }

    static class Player {
        private LinkedList<Integer> enabledCards;
        private int[] winCards; //tab[i] mean card i win with tab[i] cards
        private int[] loseCards;//tab[i] mean card i lose with tab[i] cards
        private String name;

        int strongestCard() {
            LinkedList<Integer> candidates = new LinkedList<>();
            int max = 0;
            for(int i : enabledCards) {
                if(winCards[i] > max) {
                    max = winCards[i];
                    candidates = new LinkedList<>();
                    candidates.add(i);
                } else if(winCards[i] == max) {
                    candidates.add(i);
                }
            }
            int min_i = candidates.getFirst();
            if(candidates.size() > 1) {
                int min = loseCards[min_i];
                for (int i : candidates) {
                    if (loseCards[i] < min) {
                        min = loseCards[i];
                        min_i = i;
                    }
                }
            }
            return min_i;
        }

        Player(String name, int cardCount, Graph graph) {
            this.name = name;
            this.winCards = new int[cardCount];
            this.loseCards = new int[cardCount];
            this.enabledCards = new LinkedList<>();
            for(int i=0; i<cardCount; ++i) {
                enabledCards.add(i);

            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(bi.readLine());

        int n;
        int m;
        String[] input;
        int x;
        int y;
        String w;
        for (int i=0; i<t; ++i) {
            input = bi.readLine().split(" ");
            n = Integer.parseInt(input[0]);
            m = Integer.parseInt(input[1]);

            if(m == 0) {
                System.out.println("REMIS");
                continue;
            }

            Graph graph = new Graph(n, m);
            Player bajtek = new Player("A", n, graph);
            Player bitek = new Player("B", n, graph);

            for (int j=0; j<m; ++j) {
                input = bi.readLine().split(" ");
                x = Integer.parseInt(input[0]);
                w = input[1];
                y = Integer.parseInt(input[2]);

                if(">".equals(w)) {
                    graph.addEdge(x, y, bajtek);
                    ++bajtek.winCards[x-1];
                    ++bitek.loseCards[y-1];
                } else {
                    graph.addEdge(x, y, bitek);
                    ++bitek.winCards[y-1];
                    ++bajtek.loseCards[x-1];
                }
            }
            doIt(bajtek, bitek, graph);
        }
    }

    private static void doIt(Player p1, Player p2, Graph graph) {
        Player current = p1;
        Player opponent = p2;
        Player tmp;

        while (p1.enabledCards.size() > 1 || p2.enabledCards.size() > 1) {
            int strongestCard = opponent.strongestCard();
            opponent.enabledCards.removeFirstOccurrence(strongestCard);
            opponent.winCards[strongestCard] = 0;
            opponent.loseCards[strongestCard] = 0;

            for(int i : current.enabledCards) {
                if (current == p1) {
                    if (graph.graph[i] == null) {
                        tmp = null;
                    } else {
                        tmp = graph.graph[i][strongestCard];
                    }
                } else {
                    if (graph.graph[strongestCard] == null) {
                        tmp = null;
                    } else {
                        tmp = graph.graph[strongestCard][i];
                    }
                }

                if (tmp == current) {
                    --current.winCards[i];
                } else if(tmp == opponent) {
                    --current.loseCards[i];
                }
            }

            if (opponent == p2) { //current == bajtek
                opponent = p1;
                current = p2;
            }
            else {  //current == bitek
                opponent = p2;
                current = p1;
            }
        }

        if (graph.graph[p1.enabledCards.getFirst()] == null ) {
            tmp = null;
        } else {
            tmp = graph.graph[p1.enabledCards.getFirst()][p2.enabledCards.getFirst()];
        }

        if (tmp == p1) {
            System.out.println("WYGRANA");
        } else if (tmp == p2) {
            System.out.println("PRZEGRANA");
        } else {
            System.out.println("REMIS");
        }
    }
}