配点 : 600 点
問題文
頂点 1 植根于 N 我有一棵有根的顶点树。顶点 i 的父级是顶点 P_i 。从现在开始,每个顶点 我想写 0 ,而其余数字之间一定会放入 1 。
对于满足以下给定条件的顶点 找到一种分配 0 和 1 的方法。另外,如果不存在这样的分配方法,请报告。
- K 顶点 分别为 M_1 ,M_2, \cdots M_K 。 写入 S_1 ,S_2, \cdots S_K 。
- 頂点 i 至 如果写入 1 ,则顶点 A_i 及其后代的顶点有 1 。
- 頂点 i 至 如果写入 0 ,则顶点 A_i 及其后代的顶点有 0 。
制約
- 2 \leq N \leq 10^5
- 1 \leq P_i < i (2 \leq i \leq N)
- 0 \leq K \leq N-1
- 1 \leq M_i \leq N (1 \leq i \leq K)
- M_i \neq M_j (1 \leq i < j \leq K)
- S_i \in \lbrace 0,1 \rbrace (1 \leq i \leq K)
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。 请按降序输出
N P_2 P_3 P_4 \cdots P_N K M_1 S_1 M_2 S_2 \vdots M_K S_K A_1 A_2 A_3 \cdots A_N
出力
第一行对应解决方案 N 字符
由 01 请输出字符串。i 字符的顶点
请输出 i 中写入的数字。
如果没有解决方案,则第一行
请输出 IMPOSSIBLE 。
入力例 1
4 1 1 2 1 2 1 3 4 3 2
出力例 1
1111
入力例 2
5 1 2 3 4 2 1 1 2 0 3 1 4 1 5
出力例 2
IMPOSSIBLE