406172: GYM102299 H Course recommendation

One of the biggest challenges in an online course platform is to recommend to a student one of its over 800 courses.

For instance, João took courses on Java and Java for the Web, with grades 10 and 9, respectively. What should he be recommended next? If we recommend him something much easier, much harder, or simply something that does not go with his profile, we will waste his time. Just as an undergraduate student is very careful for choosing the appropriate courses and not waste a semester due to poor choices, we wish to help students in this platform to make the best choices.

In this problem, we have (N) students and (M) courses. Students are numbered from 1 to (N), the courses from (1) to (M). For each student, we know which courses he or she already took and the respective grades. To recommend a course to a student, we first find another student who is closest to him or her. The distance between two students is defined as the euclidean distance between the grades of the courses both students took. If there are no shared courses, the distance is defined as infinity. Among the courses already taken by the closest student, we recommend the course with the highest grade which was not already taken by the original student. In case of a tie, recommend the course with the smallest index. If the original student already took all the courses that were taken by his closest student, no recommendation is make.

Your task is to code a program that recommend a course to all the students in the platform.

The first line has two integers $$$N$$$ and $$$M$$$, the number of students and courses, respectively. After this there are (N) blocks of lines, each one contains a line with an integer (Q_i), the amount of courses already taken by the (i)th student, and then (Q_i) lines, each one containing two integers (c) and (g), which indicate that the (i)th student got grade (g) for course (c).

Constraints

• $$$2 \leq N \leq 100$$$
• $$$1 \leq M \leq 100$$$
• $$$1 \leq Q_i, c \leq M$$$
• $$$0 \leq g \leq 10$$$
• You may assume that each student has already taken at least one course that another student took.

Print (N) lines, where the (i)th line has the course recommended to the (i)th student. If student (i) has already taken all courses that his closest student already took, print (-1).

2 3
2
1 10
2 10
2
2 9
3 5

3
1

2 4
3
1 7
2 8
3 10
3
4 10
2 9
1 5

4
3

In the first example, the distance between students is given by $$$\sqrt{(10-9)^2}$$$

In the second, it is given by $$$\sqrt{(7-5)^2 + (8-9)^2}$$$