## Yet Another Contest 6 P2 - No More Telemarketers

View as PDF

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 512M

Author:
Problem types

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 succesfully 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 exist). All moves must still be valid and outputted in the correct format, although the company does not need to be reorganised succesfully.

#### 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.