랑데부

바이트아사르는 화살 동굴의 관리인입니다. 이 동굴은 연인들이 즐겨 찾는 만남의 장소입니다. 동굴에는 $n$개의 방이 있고, 방들은 일방통행 통로로 연결되어 있습니다. 각 방에서 나가는 통로 중 정확히 하나에 화살표가 그려져 있으며, 모든 통로는 어떤 방(자기 자신일 수도 있습니다)으로 곧장 이어집니다.

화살 동굴에서 만나기로 한 연인들은 정확한 방을 정하지 않는 경우가 많아 서로를 찾지 못하곤 합니다. 각 방에 당직 관리인과 연결되는 비상 전화가 설치된 뒤로, 연인들이 서로를 찾도록 돕는 일이 관리인의 주된 업무가 되었습니다.

관리인들은 다음 방법을 씁니다. 두 사람의 현재 위치를 알고 있을 때, 각자 화살표를 몇 번 따라가면 같은 방에서 만날 수 있는지 알려 줍니다. 연인들은 되도록 빨리 만나고 싶어 하므로, 두 값 중 더 큰 값이 가능한 한 작은 답이 좋은 답입니다.

바이트아사르는 이 일이 번거로워 여러분에게 프로그램 작성을 부탁했습니다. 동굴의 구조와 $k$쌍의 연인의 현재 위치가 주어질 때, $i$번째 쌍에 대해 다음을 만족하는 두 수 $x_i$, $y_i$를 출력하세요.

• 남자가 화살표를 $x_i$번, 여자가 $y_i$번 따라가면 두 사람이 같은 방에 도착합니다.
• $\max(x_i, y_i)$가 최소입니다.
• 그 조건에서 $\min(x_i, y_i)$가 최소입니다.
• 그래도 답이 유일하게 정해지지 않으면 여자가 더 짧은 거리를 이동합니다. 즉 $x_i \ge y_i$입니다.

그러한 $x_i$, $y_i$가 존재하지 않으면 $x_i = y_i = -1$을 출력합니다. 여러 쌍이 같은 방에서 만나도 괜찮습니다.

첫째 줄에 방의 수 $n$과 연인 쌍의 수 $k$가 공백 하나로 구분되어 주어집니다 ($1 \le n \le 500000$, $1 \le k \le 500000$). 방은 $1$번부터 $n$번까지 번호가 매겨져 있습니다.

둘째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 $i$번 방에서 나가는 화살표가 가리키는 방의 번호입니다.

이어지는 $k$개의 줄에 각 쌍의 질의가 주어집니다. 각 줄에는 두 정수가 공백 하나로 구분되어 주어지며, 먼저 남자가 있는 방, 그다음 여자가 있는 방의 번호입니다.

전체 점수의 40%에 해당하는 테스트에서는 추가로 $n \le 2000$, $k \le 2000$을 만족합니다.

정확히 $k$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 쌍에 대한 $x_i$와 $y_i$를 공백 하나로 구분하여 출력합니다.