Meeting Point Routing

Byteasar is a ranger working in the Arrow Cave – a famous rendezvous spot among lovers. The cave consists of \(n\) chambers connected with one-way corridors. In each chamber exactly one outgoing corridor is marked with an arrow, and every corridor leads directly to some (possibly the same) chamber.

The enamoured couples who meet in the cave often end up wandering due to not agreeing on a precise meeting chamber. To help, the rangers now instruct each person with a number: the man should follow the arrow \(x_i\) times and the woman \(y_i\) times so that they meet in the same chamber. They want to meet as soon as possible. In other words, for each couple, you must find nonnegative integers \(x_i\) and \(y_i\) such that, if starting from their initial positions and following the corridors exactly \(x_i\) and \(y_i\) times respectively, they arrive at the same chamber, and the value

[ T = \max(x_i, y_i) ]

is minimized. Subject to that, the value

[ S = \min(x_i, y_i) ]

should be minimized. If there is still more than one candidate pair, choose the one where the man walks at least as much as the woman (i.e. (x_i \ge y_i)). If no such pair exists, output (-1 -1) for that couple.

You are given the description of the cave and the current locations of \(k\) couples. For each couple, determine and output the corresponding pair \(x_i\) and \(y_i\) meeting the above criteria.

inputFormat

The first line contains a single integer \(n\) \((1 \le n \le 10^5)\) — the number of chambers.

The next line contains \(n\) integers; the \(i\)th integer \(f_i\) \((1 \le f_i \le n)\) indicates that the arrow in chamber \(i\) points to chamber \(f_i\).

The next line contains an integer \(k\) \((1 \le k \le 10^5)\) — the number of couples.

Each of the following \(k\) lines contains two integers \(a\) and \(b\) \((1 \le a, b \le n)\) representing the starting chambers of the man and the woman, respectively.

outputFormat

For each couple, output a line containing two space-separated integers \(x_i\) and \(y_i\) according to the problem statement. If no solution exists, output -1 -1.

sample

3
2 3 3
2
1 2
2 3

1 0
1 0