I'm trying to solve this task: At New Year students play Secret Santa. Each student i is given a student a_i to whom they must give a gift. The administrator of the game assigned each student their own number. But then his colleague asked: Is it true that if you start a chain of gifts from student 1 to student a_1, then and so on, then the chain will close with the student 1 after it has involved all the other students exactly once? The administrator doesn’t know whether this is true or not, but he is going to change exactly one a_i number to get a configuration that will suit his colleague. Help him with this. The first line contains a natural number n (2 <= n <= 10 ** 5) — the number of schoolchildren. The next line contains n numbers a_i — the student who went to Secret Santa with the number i (1 <= a_i <= n). First line of output should contain two numbers (1 <= x, y <= n; x != y) - student with number x who's a_x should be changed and new value of a_x. Note that a_x != y. If several answers exists print any. If this is not possible print -1 -1. Examples: Input: 3 1 2 3 Output: -1 -1 Input: 3 1 3 1 Output: 1 2 I wrote this code to solve this task: n = int(input()) students = [int(x) for x in input().split()] a, b = -1, -1 for x in range(1, n + 1): d = [x] vals = set() vals.add(x) for i in range(1, n + 1): val = students[d[i - 1] - 1] d.append(val) if val in vals: break vals.add(val) # print(f'x = {x} | d = {d}') if len(set(d)) == n: if d[-1] != d[0]: a = d[-2] b = d[0] print(a, b) I thought it is basically the same as finding whether there exists a graph that is one step away from being a cycle. The code seems to solve the cases that I try. However, it doesn't pass all the tests. Could somebody please help with suggesting what could be wrong here? Thanks in advance. Continue reading...
