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-----

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-----

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


-----Examples-----
Input
5 7
2 2 8 6 9
1 2
1 3
2 4
3 2
4 5
2 5
1 5
2

Output
27

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

Output
61

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
W=[0]+list(map(int,input().split()))
E=[tuple(map(int,input().split())) for i in range(m)]
S=int(input())

ELIST=[[] for i in range(n+1)]
EW=[0]*(n+1)

for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)

    EW[x]+=1
    EW[y]+=1


from collections import deque
Q=deque()
USED=[0]*(n+1)

for i in range(1,n+1):
    if EW[i]==1 and i!=S:
        USED[i]=1
        Q.append(i)

EW[S]+=1<<50
USED[S]=1

while Q:
    x=Q.pop()
    EW[x]-=1

    for to in ELIST[x]:
        if USED[to]==1:
            continue
        EW[to]-=1

        if EW[to]==1 and USED[to]==0:
            Q.append(to)
            USED[to]=1

#print(EW)
LOOP=[]

ANS=0
for i in range(1,n+1):
    if EW[i]!=0:
        ANS+=W[i]
        LOOP.append(i)

SCORE=[0]*(n+1)
USED=[0]*(n+1)

for l in LOOP:
    SCORE[l]=ANS
    USED[l]=1

Q=deque(LOOP)

while Q:
    x=Q.pop()

    for to in ELIST[x]:
        if USED[to]==1:
            continue

        SCORE[to]=W[to]+SCORE[x]
        Q.append(to)
        USED[to]=1

print(max(SCORE))


from collections import defaultdict

def get_neighbors(edges):
    neighbors = defaultdict(set, {})
    for v1, v2 in edges:
        neighbors[v1].add(v2)
        neighbors[v2].add(v1)

    return dict(neighbors)


def get_component(neighbors_map, root):
    if root not in neighbors_map:
        return {root}

    horizon = set(neighbors_map[root])
    component = {root}

    while horizon:
        new_node = horizon.pop()
        if new_node in component:
            continue

        component.add(new_node)
        new_neighbors = neighbors_map[new_node].difference(component)
        horizon |= new_neighbors

    return component


def fn(weights, edges, root):
    neihgbors_map = get_neighbors(edges)
    if root not in neihgbors_map:
        return weights[root]

    first_component = get_component(neihgbors_map, root)

    neihgbors_map = {k: v for k, v in list(neihgbors_map.items()) if k in first_component}
    degrees = {}
    leaves = []
    for n, neigh in list(neihgbors_map.items()):
        degrees[n] = len(neigh)
        if len(neigh) == 1 and n != root:
            leaves.append(n)

    extra_values = defaultdict(int, {})
    max_extra = 0
    removed_set = set()
    while leaves:
        leaf = leaves.pop()
        value = weights[leaf] + extra_values[leaf]
        parent = neihgbors_map.pop(leaf).pop()
        neihgbors_map[parent].remove(leaf)
        degrees[parent] -= 1
        if degrees[parent] == 1 and parent != root:
            leaves.append(parent)

        mm = max(extra_values[parent], value)
        extra_values[parent] = mm
        max_extra = max(mm, max_extra)
        removed_set.add(leaf)

    return sum(weights[n] for n in neihgbors_map) + max_extra

def print_answer(source):
    n, m = list(map(int, source().split()))
    weights = list(map(int, source().split()))
    edges = [[int(k) - 1 for k in source().split()] for _ in range(m)]
    root = int(source()) - 1

    print(fn(weights, edges, root))

print_answer(input)

if False:
    from string_source import string_source

    print_answer(string_source("""3 2
1 1335 2
2 1
3 2
2"""))

    from string_source import string_source
    print_answer(string_source("""1 0
1000000000
1"""))

    print_answer(string_source("""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"""))

    print_answer(string_source(
            """5 7
    2 2 8 6 9
    1 2
    1 3
    2 4
    3 2
    4 5
    2 5
    1 5
    2"""))

    source = string_source("""3 2
1 1335 2
2 1
3 2
2""")
    n, m = list(map(int, source().split()))
    weights = list(map(int, source().split()))
    edges = [[int(k) - 1 for k in source().split()] for _ in range(m)]
    root = int(source())

    fn(weights, edges, root)

    from graphviz import Graph

    dot = Graph(format="png", name="xx", filename=f"_files/temp/graph.png")

    for idx, w in enumerate(weights):
        dot.node(str(idx), label=f"{idx} - {w}")

    for s,e in edges:
        dot.edge(str(s),str(e))

    dot.view(cleanup=True)

    sum(weights)



import sys
input = sys.stdin.readline
n,m=map(int,input().split())
W=[0]+list(map(int,input().split()))
E=[tuple(map(int,input().split())) for i in range(m)]
S=int(input())
 
ELIST=[[] for i in range(n+1)]
EW=[0]*(n+1)
 
for x,y in E:
    ELIST[x].append(y)
    ELIST[y].append(x)
 
    EW[x]+=1
    EW[y]+=1
 
#print(ELIST,EW) 
from collections import deque
Q=deque()
USED=[0]*(n+1)
for i in range(1,n+1):
    if EW[i]==1 and i!=S:
        USED[i]=1
        Q.append(i)
#print(Q) 
EW[S]+=1<<50
USED[S]=1
 
while Q:
    x=Q.pop()
    EW[x]-=1
    #print(x,EW)
 
    for to in ELIST[x]:
        if USED[to]==1:
            continue
        EW[to]-=1
 
        if EW[to]==1 and USED[to]==0:
            Q.append(to)
            USED[to]=1
#print(EW)
LOOP=[]
 
ANS=0
for i in range(1,n+1):
    if EW[i]!=0:
        ANS+=W[i]
        LOOP.append(i)
#print(LOOP) 
SCORE=[0]*(n+1)
USED=[0]*(n+1)
for l in LOOP:
    SCORE[l]=ANS
    USED[l]=1
#print(USED) 
Q=deque(LOOP)
#print(Q)
while Q:
    x=Q.pop()
    #print(x,ELIST[x],USED)
    for to in ELIST[x]:
        if USED[to]==1:
            continue
 
        SCORE[to]=W[to]+SCORE[x]
        Q.append(to)
        USED[to]=1
 
print(max(SCORE))