3407. [NOI Online 2020 3rd]魔法值

【题目描述】

$H$ 国的交通由 $n$ 座城市与 $m$ 条道路构成，城市与道路都从 $1$ 开始编号，其中 $1$ 号城市是 $H$国的首都。$H$ 国中一条道路将把两个不同城市直接相连，且任意两个城市间至多有一条道路。

$H$ 国是一个信奉魔法的国家，在第 $j$ 天，$i$ 号城市的魔法值为 $f_{i,j}$。$H$ 国的魔法师已观测到第 $0$ 天时所有城市的魔法值 $f_{i,0}$,且他们还发现，之后的每一天每个城市的魔法值，都将会变为所有与该城市直接相连的城市的前一天魔法值的异或值，即

$f_{x,j}$ $=$ $f_{v_1,j-1}$ $xor$ $f_{v_2,j-1}$ $xor$ $\ldots$ $xor$ $f_{v_k,j-1}$

其中$j \geq 1$且$v_1....v_k$是与$x$直接相连的城市

现在 $H$ 国的国王问了你$q$个问题，对于第$i$个问题你需要回答:第$a_i$天时首都的魔法值是多少。

【输入格式】

第一行三个用空格分隔的整数$n,m,q$表示城市数、道路数与问题数。

第二行$n$个用空格分隔的整数，第$i$个整数表示$f_{i,0}$。

接下来$m$行,每行两个用空格分隔的正整数 $u,v$表示一条连接$u$号城市与$v$号城市的道路。

接下来$q$行每行一个整数，第$i$行的整数表示$a_i$。

【输出格式】

按顺序输出$q$行每行一个整数，表示对应问题的答案

【样例输入】

3 3 1
0 0 1
1 2
1 3
2 3
1

【样例输出】

1

【提示】

对于 $20$% 的数据，满足：$a_i \leq 100$

对于 $40$% 的数据，满足：$1 \leq n \leq 20$

另有 $30$% 的数据，满足：$m = \frac{n(n-1)}{2}$

对于 $100$% 的数据，满足：$1 \leq n , q \leq 100 \ , \ 1 \leq m \leq \frac{n(n-1)}{2}， 1 \leq a_i < 2^{32} \ ， \ 0 \leq f_{i,0} < 2^{32}$

【来源】

$NOI$ $Online$能力测试 第$3$场 提高组 $problem$ $2$