Тайные комнаты

면접 대비

시간 제한2초메모리 제한1024 MB

요약

방마다 나가는 간선이 하나씩 있을 때, 간선 하나만 바꿔 방 1에서 시작해 모든 방을 한 번씩 도는 순환 경로를 만들 수 있는지 판별하고, 가능하면 그 간선을 출력한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

К Мистеру Саламандеру в руки попал план некоторого здания. На этом плане $n$ тайных комнат, пронумерованных от $1$ до $n$ . Из каждой команты существует ровно один выход. Выход из $i$ -й комнаты ведет в $a\_i$ -ю комнату.

Мистер Саламандер любит гулять по кругу, но с текущим планом это может ему не удасться. К тому же, он любит некоторый эффект неожиданности, поэтому хочет изменить выход ровно одной комнаты, на некоторый другой, отличный от изначального, чтобы существовал такой циклический маршрут, который начинается в комнате номер $1$ , посещает все вершины и не посещает никакую вершину дважды.

Помогите ему выяснить, можно ли это сделать.

Обратите внимание, что так как комнаты волшебные, выход из комнаты может вести в нее же саму, то есть $a\_i = i$ .

입력

В первой строке находится натуральное число $n$ --- количество комнат ( $2 \le n \le 10^5$ ).

В следующей строке находится $n$ натуральных чисел $a\_i$ --- в какую комнату ведет выход из комнаты c номером $i$ ( $1 \le a\_i \le n$ ).

출력

В первой строке выведите два числа ( $1 \le x, y \le n, x \neq y$ ) --- номер комнаты, в которой нужно изменить выход, и номер комнаты, в который должен вести новый выход из комнаты с номером $x$ . Новый выход не должен совпадать со старым, то есть должно выполняться условие $a\_x \ne y$ . Если таких ответов несколько --- выведите любой.

Если сделать этого невозможно --- выведите -1 -1.

예제3

예제 1
입력
```
3
1 2 3
```
예상 출력
```
-1 -1
```
예제 2
입력
```
3
1 3 1
```
예상 출력
```
1 2
```
예제 3
입력
```
4
2 3 4 1
```
예상 출력
```
-1 -1
```