#P18702. Treelection

Treelection

Treelection

公司 X 有 NN 名员工,编号为 11 到 NN。对于每个 2≤u≤N2\le u\le N,编号为 PuP_u(1≤Pu<u1\le P_u<u)的员工是员工 uu 的直属经理。员工 11 是 CEO,没有经理。

如果员工 vv 是员工 uu 的直属经理,或者存在员工 ww,使得 vv 是 ww 的直属经理且 ww 是 uu 的领导,则称 vv 是 uu 的领导。也就是说,领导是管理树中的严格祖先,不包括员工自己。

公司 X 想通过选举成立员工委员会。每位员工都会投票,CEO 除外。不幸的是,选举受到操纵:每位投票员工只能投给自己的一位领导。

请找出哪些员工有可能成为选举的唯一胜者。一名员工是唯一胜者,当且仅当他获得的票数严格多于其他任意员工。

输入格式

第一行包含整数 TT,表示测试用例数。

每个测试用例包含两行:第一行包含整数 NN;第二行包含 N−1N-1 个整数 P2,P3,…,PNP_2,P_3,\ldots,P_N。保证对所有合法下标 ii,均有 1≤Pi<i1\le P_i<i。

数据范围

  • 1≤T1\le T。
  • 2≤N≤1062\le N\le10^6。
  • 所有测试用例中,NN 的总和不超过 10610^6。
  • 对所有 2≤i≤N2\le i\le N,有 1≤Pi<i1\le P_i<i。

输出格式

对每个测试用例输出一行,一个长度为 NN 的字符串。如果员工 ii 有可能成为唯一胜者,则第 ii 个字符为 1,否则为 0。

样例输入

2
4
1 2 3
5
1 1 2 2

样例输出

1100
10000

样例说明

在第一个测试用例中,如果员工 22 投给员工 11,员工 33 和员工 44 都投给员工 22,则员工 11 得到 11 票,员工 22 得到 22 票。因此员工 22 可以成为唯一胜者。