Welcome to ZOJ Contests Information Problems Runs Statistics Ranklist Clarification 137 - ZOJ Monthly, November 2014 - B
Permutation

Time Limit: 4 Seconds      Memory Limit: 131072 KB      Special Judge

Given two sequences {A(1), A(2), ..., A(N)} and {B(1), B(2), ..., B(N)}.

You task is to find a sequence {σ(1), σ(2), ..., σ(N)} satisfy the following conditions:

1. {σ(1), σ(2), ..., σ(N)} is a permutation of sequence {1, 2, ..., N}
2. ∀ 1 ≤ iN, A(σ(i)) = σ(B(i))

#### Input

There are multiple test cases. Each case begin with a line contains an integer N (1 ≤ N ≤ 50000). The second line contains N integers, A(1), A(2), ..., A(N) (1 ≤ A(i) ≤ N). The third line contains N integers, B(1), B(2), ..., B(N) (1 ≤ B(i) ≤ N).

#### Output

For each test case, if you cannot find the sequence, you should just output "IMPOSSIBLE" (without quotes). If you find the sequence, you should output two lines. In the first line, you should just output "FOUND num" (without quotes), where num is the number of sequences you find. The number may be very large, so the answer should modulo 109 + 7. And in the second line, you should output N integers σ(1), σ(2), ..., σ(N), separated by a space. If there are multiple sequences meeting the conditions, you can output any one of them.

#### Sample Input

```4
2 3 1 3
3 3 4 1
4
2 3 1 3
1 1 2 3
12
2 1 2 2 1 1 8 7 8 8 7 7
2 1 2 2 1 1 8 7 8 8 7 7
```

#### Sample Output

```FOUND 1
2 4 3 1
IMPOSSIBLE
FOUND 128
1 2 3 4 5 6 7 8 9 10 11 12
```

Author: LIN, Xi
Submit    Status