33OJ
登录 注册

#CF2109D. D/D/D

D/D/D

题目描述

给定一张简单、连通的无向图,有 nn 个顶点、mm 条边,不存在自环与重边。同时给定一个大小为 ℓ\ell 的多重集合 AA:

A={A1,A2,…,Aℓ}A = \{A_1, A_2, \ldots, A_\ell\}

从顶点 11 出发,只要多重集合 AA 不为空,你可以执行任意次下述操作:

  • 从集合 AA 中选出一个数 kk,将它从集合中移除(只删掉这一个 kk)。
  • 走一条恰好经过 kk 条边的途径,到达某个顶点(可以是出发顶点本身)。

对每一个 ii(1≤i≤n1 \le i \le n),判断是否存在一种操作顺序,从顶点 11 出发,用原始多重集合 AA 里的某些元素之后停在顶点 ii(也可以不用,详细看样例解释)。

注意:对每个顶点 ii 的判定互相独立——每次判定都重新从顶点 11 出发,使用原始的多重集合 AA。

∗^{\text{∗}}一条长度为 kk 的途径是顶点序列 v0,v1,…,vk−1,vkv_0, v_1, \ldots, v_{k-1}, v_k,相邻两个顶点 (vi,vi+1)(v_i,v_{i+1}) 在图中存在边,途径可以重复经过顶点。

输入格式

本题包含多组测试用例。第一行一个整数 tt(1≤t≤1041 \le t \le 10^4),代表测试用例数量。

每组测试用例第一行三个整数 n,m,ℓn,m,\ell(2≤n≤2⋅1052 \le n \le 2\cdot 10^5,n−1≤m≤4⋅105n-1 \le m \le 4\cdot 10^5,1≤ℓ≤2⋅1051 \le \ell \le 2\cdot 10^5),依次为顶点数、边数、多重集合大小。

第二行 ℓ\ell 个整数 A1,A2,…,AℓA_1,A_2,\dots,A_\ell(1≤Ai≤1041 \le A_i \le 10^4),代表多重集合内的元素。

接下来 mm 行,每行两个整数 u,vu,v(1≤u<v≤n1 \le u<v \le n),代表图的一条边。

保证给出的图是简单连通无向图,无自环、无重边。

保证所有测试用例中,nn 的总和不超过 2⋅1052\cdot 10^5,mm 的总和不超过 4⋅1054\cdot 10^5,ℓ\ell 的总和不超过 2⋅1052\cdot 10^5。

输出格式

对每组测试用例,输出一个长度为 nn 的二进制字符串;第 ii 位字符为 1\mathtt{1} 表示存在方案最后停在顶点 ii,否则为 0\mathtt{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

说明

第一个测试用例:

  • 顶点 11:不执行任何操作就可以到达。
  • 顶点 22:选取集合中的 33;一条可行途径是 [1→2→1→2][1\rightarrow2\rightarrow1\rightarrow2]。
  • 顶点 33:选取集合中的 22;一条可行途径是 [1→2→3][1\rightarrow2\rightarrow3]。
  • 顶点 44:选取集合中的 33;一条可行途径是 [1→2→3→4][1\rightarrow2\rightarrow3\rightarrow4]。
  • 顶点 55:不存在任何合法操作序列可以到达。
  • 顶点 66:先选 22,走途径 [1→2→3][1\rightarrow2\rightarrow3];再选 33,走途径 [3→4→5→6][3\rightarrow4\rightarrow5\rightarrow6]。

原题链接

原题链接