Recently, people have discovered a simple trick to spot telemarketers. As the owner of a telemarketing company, you have decided that the entire structure of the company needs to be changed in order to inspire innovation in anti-detection telemarketing services!

The company consists of ~N~ workers labelled from ~1~ to ~N~. Each worker has a boss, except for the CEO who has no boss. Worker ~X~ is a manager of worker ~Y~ if and only if worker ~X~ is worker ~Y~'s boss, or worker ~X~ is a manager of worker ~Y~'s boss. No two workers are managers of each other.

To reorganise the company, you can perform some moves. In each move, you perform the following procedure:

• Choose two different workers ~A~ and ~B~, such that worker ~A~ is not a manager of worker ~B~.
• Then, change the boss of worker ~A~ to worker ~B~.

Initially, ~s_i~ is equal to ~-1~ if worker ~i~ is the CEO, and the boss of worker ~i~ otherwise. After the company reorganisation, you would like ~t_i~ to be equal to ~-1~ if worker ~i~ is the CEO, and the boss of worker ~i~ otherwise. Can you determine the shortest possible sequence of moves to successfully reorganise the company, or determine that no such sequence of moves exists? Note that no moves may be necessary.

Constraints

~2 \le N \le 10^6~

~-1 \le s_i \le N~, ~s_i \ne 0~, ~s_i \ne i~

There is exactly one ~x~ such that ~s_x = -1~.

~-1 \le t_i \le N~, ~t_i \ne 0~, ~t_i \ne i~

There is exactly one ~x~ such that ~t_x = -1~.

In both the initial and desired configurations, no two workers are managers of each other.

For ~30\%~ of the points, you only need to determine the fewest possible number of moves (or that no such sequence of moves exists). All moves must still be valid and outputted in the correct format, although the company does not need to be reorganised successfully.

Input Specification

The first line contains a single integer ~N~.

The second line contains ~N~ space-separated integers, ~s_1, s_2, \dots, s_N~.

The third line contains ~N~ space-separated integers, ~t_1, t_2, \dots, t_N~.

Output Specification

If it is impossible to successfully reorganise the company, output ~-1~.

Otherwise, on the first line, output an integer ~M~, representing the fewest number of moves to successfully reorganise the company.

Then, the ~i~-th of the following ~M~ lines should contain two distinct space-separated integers ~A~ and ~B~, representing that the ~i~-th move reassigns worker ~B~ as the boss of worker ~A~.

Note that a solution which does not heed the output format provided above, or makes an invalid move, will not be rewarded with any points.

Sample Input 1

4
-1 1 1 3
-1 1 2 1

Sample Output 1

2
3 2
4 1

Explanation for Sample Output 1

It is optimal to perform the following moves:

• First, reassign worker ~2~ as the boss of worker ~3~.

• Then, reassign worker ~1~ as the boss of worker ~4~.

Note that reversing this sequence of moves yields another valid sequence which would be accepted.

Sample Input 2

2
-1 1
2 -1

Sample Output 2

-1

Explanation for Sample Output 2

No valid moves which change the company's structure can be made, so the company cannot be successfully reorganised.