题目描述
给定一张简单、连通的无向图,有 n 个顶点、m 条边,不存在自环与重边。同时给定一个大小为 ℓ 的多重集合 A:
A={A1,A2,…,Aℓ}
从顶点 1 出发,只要多重集合 A 不为空,你可以执行任意次下述操作:
- 从集合 A 中选出一个数 k,将它从集合中移除(只删掉这一个 k)。
- 走一条恰好经过 k 条边的途径,到达某个顶点(可以是出发顶点本身)。
对每一个 i(1≤i≤n),判断是否存在一种操作顺序,从顶点 1 出发,用原始多重集合 A 里的某些元素之后停在顶点 i(也可以不用,详细看样例解释)。
注意:对每个顶点 i 的判定互相独立——每次判定都重新从顶点 1 出发,使用原始的多重集合 A。
∗一条长度为 k 的途径是顶点序列 v0,v1,…,vk−1,vk,相邻两个顶点 (vi,vi+1) 在图中存在边,途径可以重复经过顶点。
输入格式
本题包含多组测试用例。第一行一个整数 t(1≤t≤104),代表测试用例数量。
每组测试用例第一行三个整数 n,m,ℓ(2≤n≤2⋅105,n−1≤m≤4⋅105,1≤ℓ≤2⋅105),依次为顶点数、边数、多重集合大小。
第二行 ℓ 个整数 A1,A2,…,Aℓ(1≤Ai≤104),代表多重集合内的元素。
接下来 m 行,每行两个整数 u,v(1≤u<v≤n),代表图的一条边。
保证给出的图是简单连通无向图,无自环、无重边。
保证所有测试用例中,n 的总和不超过 2⋅105,m 的总和不超过 4⋅105,ℓ 的总和不超过 2⋅105。
输出格式
对每组测试用例,输出一个长度为 n 的二进制字符串;第 i 位字符为 1 表示存在方案最后停在顶点 i,否则为 0。
3
6 5 2
2 3
1 2
2 3
3 4
4 5
5 6
5 5 1
5
1 2
2 3
3 4
4 5
3 5
5 4 3
100 200 300
1 2
1 3
1 4
2 5
111101
11111
10001
说明
第一个测试用例:
- 顶点 1:不执行任何操作就可以到达。
- 顶点 2:选取集合中的 3;一条可行途径是 [1→2→1→2]。
- 顶点 3:选取集合中的 2;一条可行途径是 [1→2→3]。
- 顶点 4:选取集合中的 3;一条可行途径是 [1→2→3→4]。
- 顶点 5:不存在任何合法操作序列可以到达。
- 顶点 6:先选 2,走途径 [1→2→3];再选 3,走途径 [3→4→5→6]。
原题链接
原题链接