Change one pair of vertices to create a cycle in an oriented graph

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.

Solution

If I understood the problem definition correctly, conceptually, you're on the right track: you want to see if there is an MST of size n - 1, such that changing/adding one more edge produces a cycle of size n. In other words:

if your MST has size n, then there is nothing that can be changed (your example 1 is one such case where each student gifts their own self);
if your MST has size < n - 1, then there is nothing that can be changed because you're only allowed to change one configuration; and
if your MST has size n - 1, then there is a solution since you have one more student who's unaccounted for in the current MST and you can add them (your example 2 falls in this case). The multiple solutions arise in this case because a graph can have multiple MSTs.

Taken together, you can fail fast by checking the size of set(students). If the size is n - 1, then you'd need to track who got double-gifted and who got left out.