亚历克斯决定去全国各地旅游。
为简单起见,我们假设该国家有 $$$n$$$ 个城市和连接它们的 $$$m$$$ 双向道路。亚历克斯住在城市 $$$s$$$ 并最初位于其中。为了比较不同的城市,Alex 为每个城市分配了一个分数 $$$w_i$$$,该分数与 Alex 认为有趣的城市一样高。
Alex 相信,只有当他不连续两次使用任何道路时,他的旅行才会有趣。也就是说,如果Alex从$$$u$$$来到城市$$$v$$$,他可以选择任何与$$$v$$$有公路相连的城市作为行程中的下一个城市,除了城市$$$u$$$。
你的任务是帮助 Alex 规划他的城市,使他访问过的所有城市的总得分最大化。请注意,对于每个城市,其得分最多计算一次,即使 Alex 在旅途中多次去过那里。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$,($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$),它们是该国的城市和道路的数量。
第二行包含 $$$n$$$ 整数 $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 10^9$$$),它们是所有城市的分数。
以下 $$$m$$$ 行包含道路的描述。每条 $$$m$$$ 行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),它们是这条道路连接的城市。
保证任意两个城市之间至多有一条直达道路,没有城市通过道路与自身相连,最后,可以仅通过道路从任何城市前往任何其他城市。
最后一行包含单个整数$$$s$$$ ($$$1 \le s \le n$$$),它是初始城市的编号。
输出
输出单个整数,它是访问过的城市的最大可能得分总和。
示例
输入 #1
5 7 2 2 8 6 9 1 2 1 3 2 4 3 2 4 5 2 5 1 5 2
输出 #1
27
输入 #2
10 12 1 7 1 9 3 3 6 30 1 10 1 2 1 3 3 5 5 7 2 3 5 4 6 9 4 6 3 7 6 8 9 4 9 10 6
输出 #2
61