题目描述

给定两棵 $N$ 个节点的有根树，节点编号均为 $1\sim N$。第一棵树中，节点编号为 $i$ 的父亲编号为 $A_i$，若节点 $i$ 是根节点，则 $A_i=-1$；第二棵树中，节点编号为 $i$ 的父亲编号为 $B_i$，若节点 $i$ 是根节点，则 $B_i=-1$。

请你构造一个长度为 $N$ 的整数序列 $X$，要求满足以下条件：

• 对于任意节点，设以其为根的子树内节点的编号为 $a_1,a_2,\cdots,a_k$，有 $\left|\sum\limits_{i=1}^kX_{a_i}\right|=1$。

判断是否存在满足条件的整数序列 $X$，若存在，给出任意一种合法方案。

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个整数 $A_i$，表示第一棵树内节点 $i$ 的父亲编号（如果是根，则 $A_i=-1$）。

第三行 $N$ 个整数 $B_i$，表示第二棵树内节点 $i$ 的父亲编号（如果是根，则 $B_i=-1$）。

输出格式

若不存在满足条件的方案，一行输出 IMPOSSIBLE。

若存在满足条件的方案，第一行输出 POSSIBLE，第二行 $N$ 个整数 $X_1,X_2,\cdots,X_N$，用空格隔开。

样例 1

输入

5
3 3 4 -1 4
4 4 1 -1 1

输出

POSSIBLE
1 -1 -1 3 -1

样例 2

输入

6
-1 5 1 5 1 3
6 5 5 3 -1 3

输出

IMPOSSIBLE

样例 3

输入

8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4

输出

POSSIBLE
1 2 -1 0 -1 1 0 -1

说明/提示

样例 $\textbf 1$ 解释

以节点 $3$ 为例，其子树内有节点 $3,1,2$，根据样例输出的 $X$，有 $|X_3+X_1+X_2|=|-1+1-1|=1$，满足题目要求。其他节点可以同样地验证，发现满足题目要求。

样例 $\textbf 2$ 解释

可以证明，无法构造出一个满足题目要求的序列，因此无解，输出了 IMPOSSIBLE。

数据范围

• $1\le N\le 10^5$。
• 若在第一棵树内，节点 $i$ 不是根，则 $1\le A_i\le N$。
• 若在第一棵树内，节点 $i$ 是根，则 $A_i=-1$。
• 若在第二棵树内，节点 $i$ 不是根，则 $1\le B_i\le N$。
• 若在第二棵树内，节点 $i$ 是根，则 $B_i=-1$。
• 保证输入的是一棵合法的树。