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 "bits/stdc++.h"
using namespace std;


using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/*-----------------------------------------------
 二辺連結成分分解 成分だけ unverified
 -----------------------------------------------*/
struct UnionFind {
    vector<int> data;
    UnionFind(int n) { data.assign(n, -1); }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
};

struct Lowlink {
    UnionFind uf;
    vector<int> low, ord, used, parent;
    int root, k;
    Lowlink(int V, int Root) :uf(V), low(V), ord(V), used(V), parent(V), root(Root), k(0) {}
    
    void lowlink(int v, int p, int &k, vector<vector<int>>& G) {
        used[v] = true; //visited
        low[v] = ord[v] = k; k++;
        for (int i = 0; i < (int)G[v].size(); i++) {
            int u = G[v][i];
            if (used[u] == 0) {
                parent[u] = v;
                lowlink(u, v, k, G);
                low[v] = min(low[v], low[u]);
                if (ord[v] >= low[u])uf.unionSet(v, u);
            }
            else if (u != p) {
                low[v] = min(low[v], ord[u]);
            }
        }
    }
};

struct TwoEdgeConnectedComponent{
    UnionFind uf;
    vector<vector<int>> g;
    vector<pair<int, int>> edges;
    vector<int> used, ord, low, comp;
    int v;
    TwoEdgeConnectedComponent(int v) : uf(v), g(v), used(v, 0), comp(v), ord(v), low(v),v(v) {}
    
    void add_edge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
        edges.push_back(minmax(x, y));
    }
    
    void dfs(int idx, int& k, int par = -1) {
        used[idx] = true;
        ord[idx] = k++;
        low[idx] = ord[idx];
        
        for (auto &to : g[idx]) {
            if (!used[to]) {
                dfs(to, k, idx);
                low[idx] = min(low[idx], low[to]);
                if (ord[idx] >= low[to]) uf.unionSet(idx, to);
            }
            else if (to != par) {
                low[idx] = min(low[idx], ord[to]);
            }
        }
    }
    
    // return origin color
    int operator[](int k) {
        return (comp[k]);
    }
    
    int size() {
        return (g.size());
    }
    
    // build, renew resG(empty -> tree), return color
    vector<int> get_graph(vector<vector<int>>& resG, int root = 0) {
        int kk = 0;
//        dfs(root, kk);
        Lowlink Low(v,0);
        Low.lowlink(root, -1, kk, g);
        auto uf = Low.uf;
        int ptr = 0;
        vector<int> color(g.size());
        for (int i = 0; i < g.size(); i++) {
            if (i == uf.root(i)) color[i] = ptr++;
        }
        
        resG.resize(ptr);
        for (int i = 0; i < g.size(); i++) {
            comp[i] = color[uf.root(i)];
        }
        for (auto &e : edges) {
            int x = comp[e.first], y = comp[e.second];
            if (x == y) continue;
            resG[x].push_back(y);
            resG[y].push_back(x);
        }
        return comp;
    }
};

int N, M, W[100000];
vector<vector<int>> resG;
vector<int> weightSum, sz;
int dp1[100000], dp3[100000];

int rec(int idx, int par = -1)
{
    int ret = 0;
    for (auto &to : resG[idx]) {
        if (to == par) continue;
        ret = max(ret, rec(to, idx));
        dp1[idx] += dp1[to];
    }
    ret += weightSum[idx];
    if (sz[idx] >= 3 || dp1[idx] > 0) dp1[idx] += weightSum[idx];
    for (auto &to : resG[idx]) {
        if (to == par) continue;
        else ret = max(ret, dp1[idx] - dp1[to] + dp3[to]);
    }
    return (dp3[idx] = ret);
}

// 三点以上集まった頂点ならば、ここを起点にもどることができる。
// dp1[v]:vから葉まで進むときの最大値
// dp3[v]:vに戻ってくるときの最大値
void f(int v, int p = -1) {
    for (int nx : resG[v]) {
        if (nx == p)continue;
        f(nx, v);
        dp1[v] += dp1[nx];
    }
    int ret = dp1[v];
    if (dp1[v] || sz[v] > 1)dp1[v] += weightSum[v];
    for (int nx : resG[v]) {
        if (nx == p)continue;
        dp3[v] = max(dp3[v], ret - dp1[nx] + dp3[nx]);
    }
    dp3[v] += weightSum[v];
}

int main() {
    int N, M; cin >> N >> M;
    FOR(i, 0, N) {
        cin >> W[i];
    }
    TwoEdgeConnectedComponent gx(N);
    
    FOR(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        gx.add_edge(a, b);
    }
    VI vc = gx.get_graph(resG);
    
    weightSum.assign(resG.size(), 0);
    sz.assign(resG.size(), 0);
    for (int i = 0; i < N; i++) {
        weightSum[vc[i]] += W[i];
        sz[vc[i]]++;
    }
    f(vc[0]);
    LL ans = dp3[vc[0]];
    cout << ans << endl;
    
    return 0;
}