Tourism
Contest: Codeforces Round 586 (Div. 1 + Div. 2)
Difficulty rating: 2200
Tags: dfs and similar, dp, dsu, graphs, greedy, trees

Alex decided to go on a touristic trip over the country.

For simplicity let's assume that the country has $$$n$$$ cities and $$$m$$$ bidirectional roads connecting them. Alex lives in city $$$s$$$ and initially located in it. To compare different cities Alex assigned each city a score $$$w_i$$$ which is as high as interesting city seems to Alex.

Alex believes that his trip will be interesting only if he will not use any road twice in a row. That is if Alex came to city $$$v$$$ from city $$$u$$$, he may choose as the next city in the trip any city connected with $$$v$$$ by the road, except for the city $$$u$$$.

Your task is to help Alex plan his city in a way that maximizes total score over all cities he visited. Note that for each city its score is counted at most once, even if Alex been there several times during his trip.

Input format:
First line of input contains two integers $$$n$$$ and $$$m$$$, ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) which are numbers of cities and roads in the country.

Second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$ ($$$0 \le w_i \le 10^9$$$) which are scores of all cities.

The following $$$m$$$ lines contain description of the roads. Each of these $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) which are cities connected by this road.

It is guaranteed that there is at most one direct road between any two cities, no city is connected to itself by the road and, finally, it is possible to go from any city to any other one using only roads.

The last line contains single integer $$$s$$$ ($$$1 \le s \le n$$$), which is the number of the initial city.

Output format:
Output single integer which is the maximum possible sum of scores of visited cities.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 7
2 2 8 6 9
1 2
1 3
2 4
3 2
4 5
2 5
1 5
2

Example output:
27

Example input:
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

Example output:
61

Editorial:
Let's note that if you visit a vertex $$$u$$$ located on a loop, you can always add the numbers on vertices in this loop to answer and you can also add the numbers on vertices between $$$u$$$ and $$$s$$$. It is true because you can just visit $$$u$$$, go through the vertices of the cycle, return to $$$u$$$ and then go back to $$$s$$$. But if from the given vertex we can't get to the cycle, then we can't return back. So the problem is to choose the best branch leading only to the leaves. And from this point there are several solutions for this problem. Let's discuss one of them:
Let $$$e_u$$$ be the maximum extra value we could get, if we are in $$$u$$$ and we want to go only to leaves. First of all just put all the leaves except $$$s$$$ in stack or queue. Then we choose the next vertex $$$u$$$ from our queue and look at its parent $$$v$$$. Let's decrease $$$v$$$'s degree and update $$$e_v = \max(e_v, e_u + w_u)$$$. If $$$v$$$'s deegre became $$$1$$$, it means that $$$v$$$ is the leave now, so let's push it in our queue, if it isn't $$$s$$$. It looks like at each step, we just erase one leave from our graph and recompute $$$e$$$ value for its parent.
At the end, we considered all vertexes which are not belong to the cycles and not belong to the pathes from $$$s$$$ to one of the cycles. So we need to sum up the biggest $$$e_u$$$ with the sum of all $$$w_v$$$, where $$$v$$$ wasn't considered during our leaves removing.
There are also solutions that build edge-connectivity components and compute the value using DP on tree.