Problem: Escape

An undirected graph with positive values ​​at the vertices is given. The vertices are numbered from 1 to N, and the i-th vertex has a value of w_i. You can start from the first vertex and move on the graph with the constraint that you cannot pass the edge that you just passed. At each vertex, you can get the score of the value that the vertex has only when you visit it for the first time.

Find the maximum sum of the points you can get.

Constraints

* 1 ≤ N ≤ 100000
* N − 1 ≤ M ≤ 100000
* 1 ≤ w_i ≤ 1000
* 1 ≤ u_i, v_i ≤ N
* There are no multiple edges or self edges
* The graph is concatenated



Input Format

Input is given from standard input in the following format.


N M
w_1 w_2 ... w_N
u_1 v_1
u_2 v_2
...
u_M v_M


In the first line, the number of vertices N of the graph and the integer M representing the number of edges are entered.
The value w_i of each vertex is entered in the second line.
In addition, the number of the two vertices connected by each side is entered in the M line.


Output Format

Print the answer on one line.

Sample Input 1


6 6
1 2 3 4 5 6
1 2
twenty three
3 4
14
4 5
5 6


Sample Output 1


twenty one


<image>
You can collect the points of all vertices by going from vertices 1 → 2 → 3 → 4 → 5 → 6.

Sample Input 2


7 8
1 3 3 5 2 2 3
1 2
twenty three
3 1
14
1 7
1 5
1 6
5 6


Sample Output 2


16


<image>
You can collect 16 points by going from vertices 1 → 2 → 3 → 1 → 5 → 6 → 1 → 4.





Example

Input

6 6
1 2 3 4 5 6
1 2
2 3
3 4
1 4
4 5
5 6


Output

21

Solution (in CPP):

Solution:
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <utility>
#include <iostream>
#include <queue>
using namespace std;
using pii = pair<int, int>;

// 移動元と行先と辺のコストを記録する構造体
template <typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T>
using Graph = vector< vector< Edge<T> > >;

// 関節点を求める (artPoints)
// 橋を求める (bridges)
// 二重辺連結成分分解をする (BICC)

// 関節点は、取り除いたときに連結でなくなってしまうような頂点のこと
// 橋は、取り除いた時に連結でなくなってしまうような辺のこと

template <typename T>
struct graphLink {
    vector<int> ord, low, parent, cmp;
    vector< vector< Edge<T> > > G, H;

    // 橋の情報 (first < second となるように格納)
    vector< pair<int, int> > bridges;
    int cnt, v;

    // init
    graphLink(vector< vector< Edge<T> > > &S, int root=0) {
        int n = S.size();
        ord.resize(n, -1), low.resize(n, 0),
        parent.resize(n, -1), cmp.resize(n, -1);
        cnt = 0, v = n;
        G = S;
        dfs(root);
    }

    // 橋であるかの判定
    bool is_bridge(int x, int y) {
        if(ord[x] > ord[y]) swap(x, y);
        return ord[x] < low[y];
    }

    // dfs 木の作成と橋の列挙 (初期化と同時にやる)
    // usage: dfs(root);
    void dfs(int cur, int prev=-1) {
        low[cur] = cnt;
        ord[cur] = cnt++;

        for(auto x : G[cur]) {
            if(x.to == prev) continue;
            if(ord[x.to] < 0) {
                parent[x.to] = cur;
                dfs(x.to, cur);

                low[cur] = min(low[cur], low[x.to]);
            }
            else {
                low[cur] = min(low[cur], ord[x.to]);
            }
            if(is_bridge(cur, x.to)) {
                int a = min(cur, x.to);
                int b = max(cur, x.to);
                bridges.emplace_back(make_pair(a, b));
            }
        }
    }

    // 関節点を求める (root は dfs 木の root と一致させる)
    // root は子を 2 つ持っていれば関節点になる
    // それ以外の頂点に関しては ord[parent] <= low[i] のとき関節点になる
    // (lowlink でも親より深さが低い頂点にたどり着けないため)
    set<int> artPoints(int root) {
        set<int> se;
        int num = 0;
        for(int i=0; i<v; i++) {
            if(parent[i] < 0) continue;
            if(parent[i] == root) num++;
            else if(ord[parent[i]] <= low[i]) se.insert(parent[i]);
        }
        if(num >= 2) se.insert(0);
        return se;
    }

    // 二重辺連結成分分解 (橋となる辺を使わないように DFS)
    // Verified: AtCoder Regular Contest D: 旅行会社高橋君
    void BICC() {
        int k = 0;
        // point, number
        stack<pii> S;
        for(int i=0; i<v; i++) {
            if(cmp[i] >= 0) continue;
            cmp[i] = k;
            S.push(make_pair(i, k++));
            while(!S.empty()) {
                pii cur = S.top(); S.pop();
                for(auto x : G[cur.first]) {
                    if(cmp[x.to] >= 0) continue;
                    if(is_bridge(cur.first, x.to)) continue;
                    cmp[x.to] = cur.second;
                    S.push(make_pair(x.to, cmp[x.to]));
                }
            }
        }

        set< pair<int, int> > edge_set;
        H.resize(k);
        for(int i=0; i<v; i++) {
            for(auto x : G[i]) {
                int ca = cmp[i], cb = cmp[x.to];
                if(ca == cb) continue;
                if(ca > cb) swap(ca, cb);
                if(edge_set.count(make_pair(ca, cb))) continue;
                edge_set.insert(make_pair(ca, cb));
                H[ca].push_back(Edge<T>(cb, 1));
                H[cb].push_back(Edge<T>(ca, 1));
            }
        }
    }
};

// par[i] = 頂点 i の親
void construct(Graph<int> &G, int root, vector<int> &par) {
    vector<int> checked(G.size());

    queue<int> que;
    que.push(root);
    checked[root] = true;
    while(que.size()) {
        int cur = que.front(); que.pop();
        for(auto e : G[cur]) {
            int to = e.to;
            if(checked[to]) continue;
            checked[to] = true;
            par[to] = cur;
            que.push(to);
        }
    }
}

long long int ans = 0;

void solve_one(int p, vector<int> par, vector<int> &points) {
    for(; p!=-1 && points[p]>0; p=par[p]) {
        ans += points[p];
        // printf("add: p = %d, value = %d\n", p, points[p]);
        points[p] = 0;
    }
}

long long int solve_two(int p, Graph<int> &G, vector<int> &points) {
    vector<long long int> ret(G.size()), checked(G.size());
    long long int sl = 0;

    queue<int> que;
    checked[p] = true;
    ret[p] = points[p];
    sl = max(sl, ret[p]);
    que.push(p);

    while(que.size()) {
        int cur = que.front(); que.pop();
        for(auto e : G[cur]) {
            int to = e.to;
            if(checked[to]) continue;
            checked[to] = true;

            ret[to] = ret[cur] + points[to];
            sl = max(sl, ret[to]);
            que.push(to);
        }
    }
    return sl;
}

int main() {
    int N, M; cin >> N >> M;
    vector<int> value(N);

    for(int i=0; i<N; i++) {
        cin >> value[i];
    }

    Graph<int> G(N);
    for(int i=0; i<M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(Edge<int>(v, 1));
        G[v].push_back(Edge<int>(u, 1));
    }

    graphLink<int> gl(G, 0);
    gl.BICC();

    int cmpN = gl.H.size();

    // 縮約後の頂点に含まれる元の頂点数
    vector<int> cmp_vs(cmpN), cmpValue(cmpN);
    for(int i=0; i<N; i++) {
        cmp_vs[ gl.cmp[i] ]++;
        cmpValue[ gl.cmp[i] ] += value[i];
    }

    // 親の情報を求める
    vector<int> par(cmpN, -1), is_leaf(cmpN, true);
    construct(gl.H, gl.cmp[0], par);
    for(int i=0; i<cmpN; i++) {
        if(cmp_vs[i] >= 3) {
            // big vertex
            solve_one(i, par, cmpValue);
        }
        if(par[i] >= 0) is_leaf[ par[i] ] = false;
    }

    /*
    for(int i=0; i<cmpN; i++) {
        printf("vertex %d, par = %d, value = %d\n", i, par[i], cmpValue[i]);
    }
    */

    ans += solve_two(gl.cmp[0], gl.H, cmpValue);
    cout << ans << endl;
    return 0;
}