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 workers labelled from
to
. Each worker has a boss, except for the CEO who has no boss. Worker
is a manager of worker
if and only if worker
is worker
's boss, or worker
is a manager of worker
'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
and
, such that worker
is not a manager of worker
.
- Then, change the boss of worker
to worker
.
Initially, is equal to
if worker
is the CEO, and the boss of worker
otherwise. After the company reorganisation, you would like
to be equal to
if worker
is the CEO, and the boss of worker
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
,
,
There is exactly one such that
.
,
,
There is exactly one such that
.
In both the initial and desired configurations, no two workers are managers of each other.
For 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 .
The second line contains space-separated integers,
.
The third line contains space-separated integers,
.
Output Specification
If it is impossible to successfully reorganise the company, output .
Otherwise, on the first line, output an integer , representing the fewest number of moves to successfully reorganise the company.
Then, the -th of the following
lines should contain two distinct space-separated integers
and
, representing that the
-th move reassigns worker
as the boss of worker
.
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
as the boss of worker
.
Then, reassign worker
as the boss of worker
.
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.
Comments