解题思路

还能互相走到的芯片，构成无向图上的一个连通块。芯片连向自己，或者同一对端点写了多次，都不会让连通块变大或变小。每个连通块里，时标权重最大的芯片是时标源；权重并列时，编号更小的芯片是时标源。一次询问只需要回答这块芯片所在连通块的时标源编号。

用并查集维护连通关系。每一条双向链路都把两个端点合并到同一块。两端已经同块时直接跳过，自环和重复链路都落在这里。
查找代表元时把路径压平，合并时按秩把矮的一块挂到高的一块下面，这样一条长链也不会把查找拖成线性。
链路全部处理完以后，按编号从小到大扫描芯片。把当前芯片和它所在块已经记下的时标源比较：权重更大就换上它；权重相同则留下编号更小的。没有任何链路的芯片单独成块，时标源就是它自己。
对每次询问，先找到该芯片的代表元，再读出代表元上保存的时标源编号。

题目内容

整套装置里安放了 $A$ 块转发芯片，编号从 $0$ 编到 $A-1$ 。报文进出这些芯片时，时间戳必须对齐。对齐靠芯片互相传递时标信息完成，这一过程叫做时标同步。

对齐遵守下列约定。

每块芯片把自身的时标权重 $w$ 写进时标信息，再沿着尚未断开的链路，把信息交给所有还能走到的芯片。
能够彼此走到的芯片组成一个时标域。域内挑出权重 $w$ 最高的芯片当作时标源，其他芯片改用它的时标。若好几块芯片的权重同为最高，就改挑其中编号最小的那一块。走不到任何其他芯片的，自己单独组成一个时标域。

眼下大量链路已经损坏，不少芯片再也走不到对方，装置会裂成好几个时标域。排查并修复时，要查出指定芯片正跟随哪一个时标源，也就是它所在域里被挑中的那块芯片的编号。

评测机经由标准输入送入全部数据。

第一行是两个整数 $A$ 和 $B$ 。 $A$ 为芯片块数， $B$ 为仍然保留的链路条数。
第二行是 $A$ 个整数，按编号 $0$ 到 $A-1$ 的顺序，给出每块芯片的时标权重 $w$ 。
其后 $B$ 行，每行两个整数 $U$ 和 $V$ ，表示编号 $U$ 与编号 $V$ 之间有一条双向链路。同一对端点可以写多次，芯片也可以连到自己，这些写法都不增加新的可达关系。
下一行是一个整数 $T$ ，表示询问次数。
最后一行是 $T$ 个整数 $G$ ，为被点名芯片的编号。点名从左到右各回答一次。

数据范围：

只打印一行。这一行含有 $T$ 个整数，彼此以单个空格相隔，开头和结尾都不留空格。从左往右，第 $k$ 个整数就是第 $k$ 次询问所对应的时标源编号。

输入

输出

0 3 0 0

说明

输入

7 4
2 6 8 5 9 9 1
0 1
1 3
3 0
4 5
6
0 3 1 5 2 6

输出

1 1 1 4 2 6

说明

四条链路实际分成四块，重复的 $3$ — $0$ 不改变分块。
编号 $0$ 、 $1$ 、 $3$ 在同一块，权重为 $2$ 、 $6$ 、 $5$ 。最大权重在编号 $1$ 。编号 $0$ 更靠前，但权重更低，不能当基准。
编号 $2$ 单独成块，基准是 $2$ 。编号 $6$ 同样单独成块，基准是 $6$ 。
编号 $4$ 与编号 $5$ 的权重都是 $9$ ，取更小的编号 $4$ 。
六次点名依次是 $0$ 、 $3$ 、 $1$ 、 $5$ 、 $2$ 、 $6$ ，答案依次是 $1$ 、 $1$ 、 $1$ 、 $4$ 、 $2$ 、 $6$ 。

分块示意（括号内为编号）：

(0)---(1)---(3)

(2)

(4)---(5)

(6)

选择提交后点击「开始AI分析」