← 返回题目列表

AtCoder · pakencamp_2022_day1_m

M. 01 树

中文机器翻译题面 查看原题

配点 : 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