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
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

/**
 * Created by stawicad on 2016-11-21.
 */
public class kar {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] bajtek = new int[m][2];
            int last = 0;
            boolean[] used = new boolean[n + 1];
            int usedCount = 0;
            for (int j = 0; j < m; j++) {
                int a = sc.nextInt();
                String cmp = sc.next();
                int b = sc.nextInt();
                if (">".equals(cmp)) {
                    bajtek[last][0] = a;
                    bajtek[last][1] = b;
                    last++;
                } else {
                    if (!used[b]) {
                        used[b] = true;
                        usedCount++;
                    }
                }
            }
            if(all(bajtek, last, new boolean[n+1])) {
                System.out.println("WYGRANA");
            }
            else if(usedCount == n) System.out.println("PRZEGRANA");
            else System.out.println("REMIS");
        }
    }

    private static boolean all(final int[][] bajtek, final int last, final boolean[] used) {
        Arrays.sort(bajtek, 0, last, (a, b) -> Integer.compare(a[0], b[0]));
        Set<Integer> global = null;
        Set<Integer> current = new HashSet<>();
        int usedCount = 0;
        for (int i = 0; i < last; i++) {
            if(!used[bajtek[i][0]]) {
                used[bajtek[i][0]] = true;
                usedCount++;
            }
            if(i > 0 && bajtek[i - 1][0] != bajtek[i][0]) {
                global = union(global, current);
            }
            current.add(bajtek[i][1]);
        }
        global = union(global, current);
        return usedCount + 1 == used.length && !global.isEmpty();
    }

    private static Set<Integer> union(final Set<Integer> union, final Set<Integer> current) {
        if(union == null) {
            HashSet<Integer> result = new HashSet<>(current);
            current.clear();
            return result;
        }
        Iterator<Integer> it = union.iterator();
        while (it.hasNext()) {
            if(!current.contains(it.next())) it.remove();
        }
        current.clear();
        return union;
    }
}