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
import java.util.*;

public class reo {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int employees = sc.nextInt();
        List<Integer> employeeNumbers = new ArrayList();
        for (int i = 1; i <= employees; i++) {
            employeeNumbers.add(i);
        }
        int preferencesCount = sc.nextInt();
        List<Integer> allowed = new ArrayList();
        List<Integer> notAllowed = new ArrayList();
        Map<Integer, List<Integer>> possitive = new HashMap();
        Map<Integer, List<Integer>> reversePossitive = new HashMap();
        Map<Integer, List<Integer>> negative = new HashMap();
        Map<Integer, List<Integer>> reverseNegative = new HashMap();
        for (int i = 0; i < preferencesCount; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            String c = sc.next();
            if (c.equals("T")) {
                allowed.add(b);
                notAllowed.add(a);
                addToMap(possitive, a, b);
                addToMap(reversePossitive, b, a);
            } else {
                addToMap(negative, a, b);
                addToMap(reverseNegative, b, a);
                notAllowed.add(b);
            }
        }
//        checkMap(possitive, negative, employees, employeeNumbers);
        employeeNumbers.removeAll(notAllowed);
        if (employeeNumbers.isEmpty()) {
            System.out.println("NIE");
        } else {
            Map<Integer, Employee> hierarchy = new HashMap();
            int director = employeeNumbers.get(0);
            hierarchy.put(director, new Employee(employeeNumbers.get(0), 0));
            employeeNumbers = new ArrayList<>();
            for (int i = 1; i <= employees; i++) {
                employeeNumbers.add(i);
            }
            employeeNumbers.remove(director - 1);
            boolean changeWas = true;
            List toRemove = new ArrayList();
            while (!employeeNumbers.isEmpty() && changeWas) {
                employeeNumbers.removeAll(toRemove);
                if(!employeeNumbers.isEmpty()){
                    changeWas = false;
                }
                toRemove = new ArrayList();
                for (int currentNumber : employeeNumbers) {
                    Set<Integer> a = new HashSet<>();
                    a.addAll(hierarchy.keySet());
                    boolean breakNow = false;
                    for (int key : a) {
                        if(!breakNow){
                            Employee e = hierarchy.get(key);
                            List<Integer> toCheck = new ArrayList();
                            toCheck.add(e.getId());
                            toCheck.addAll(e.getOver());
                            boolean check1 = true;
                            boolean check2 = true;
                            if (null != possitive.get(currentNumber)) {
                                if (!toCheck.containsAll(possitive.get(currentNumber))) {
                                    check1 = false;
                                }
                            }
                            if (null != negative.get(currentNumber)) {
                                if (negative.get(currentNumber).retainAll(toCheck)) {
                                    check2 = false;
                                }
                            }
                            if (check1 && check2) {
                                Employee newEmp = new Employee(currentNumber, e.getId());
                                newEmp.bind(e);
                                hierarchy.put(currentNumber, newEmp);
                                toRemove.add(currentNumber);
                                changeWas = true;
                                breakNow = true;
                            }
                        }
                    }
                }
            }
            if (!changeWas) {
                System.out.println("NIE");
            } else {
                for (int i = 1; i <= employees; i++) {
                    System.out.println(hierarchy.get(i).getDirectOver());
                }
            }
        }
    }

//    private static void checkMap(Map<Integer, List<Integer>> map1, Map<Integer, List<Integer>> map2, int employees, List<Integer> employeeNumbers){
//        for (int i =1; i<= employees; i++){
//            if(null == map1.get(i)){
//                map1.put(i, employeeNumbers);
//            }
//            if(null == map2.get(i)){
//                map2.put(i, employeeNumbers);
//            }
//        }
//    }

    private static void addToMap(Map<Integer, List<Integer>> map, int a, int b) {
        if (null != map.get(a)) {
            map.get(a).add(b);
        } else {
            List<Integer> list = new ArrayList<>();
            list.add(b);
            map.put(a, list);
        }
    }


    static class Employee {

        int id;
        int directOver;
        List<Integer> over = new ArrayList();
        List<Integer> topPreferences = new ArrayList();

        public Employee(Integer integer, int i) {
            this.id = integer;
            this.directOver = i;
        }

        public void bind(Employee emp) {
            over.addAll(emp.getOver());
            over.add(emp.getId());
            directOver = emp.getId();
        }

        public List<Integer> getOver() {
            return over;
        }

        public List<Integer> getTopPreferences() {
            return topPreferences;
        }

        public int getId() {
            return id;
        }

        public int getDirectOver() {
            return directOver;
        }
    }

}