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:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

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

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

// 移動元と行先と辺のコストを記録する構造体
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> > >;

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));
            }
        }
    }
};

int rec[100010], w[100010], nw[100010];
int p[100010], depth[100010], checked[100010], sz[100010];
void dfs(Graph<int> &G, int cur, int par=-1) {
    if(par >= 0) rec[cur] += nw[cur];
    for(auto e : G[cur]) {
        int to = e.to;
        if(to == par) continue;
        depth[to] = depth[cur] + 1;
        p[to] = cur;
        rec[to] += rec[cur];
        dfs(G, to, cur);
    }
}

signed main() {
    int N, M; cin >> N >> M;
    for(int i=0; i<N; i++) {
        cin >> w[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);
    gl.BICC();
    int K = gl.H.size();
    for(int i=0; i<N; i++) {
        int id = gl.cmp[i];
        nw[id] += w[i];
        sz[id]++;
    }

    int root = gl.cmp[0];
    p[root] = -1;
    dfs(gl.H, root, -1);

    vector< tuple<int, int> > info1;
    for(int i=0; i<K; i++) {
        if(sz[i] >= 3) {
            info1.emplace_back(rec[i], i);
        }
    }
    sort(info1.rbegin(), info1.rend());

    int ans = nw[root];
    for(auto e : info1) {
        int val, idx; tie(val, idx) = e;
        if(checked[idx]) continue;
        ans += val;
        for(; idx>=0; idx=p[idx]) {
            checked[idx] = true;
            nw[idx] = 0;
        }
    }

    fill(checked, checked + N, false);
    queue< pair<int, int> > que;
    que.emplace(root, 0);
    checked[root] = true;
    int ma = 0;
    while(que.size()) {
        int idx, val; tie(idx, val) = que.front(); que.pop();
        for(auto e : gl.H[idx]) {
            if(checked[e.to]) continue;
            checked[e.to] = true;
            ma = max(ma, val + nw[e.to]);
            que.emplace(e.to, val + nw[e.to]);
        }
    }
    ans += ma;
    cout << ans << endl;
    return 0;
}