题解 | #小欧皇#

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-8;

vector<int>g[N];
ll n, m, fa[N], siz[N];
bool vis[N];

int find(int x) {
    if (x == fa[x])return x;

    return fa[x] = find(fa[x]);
}

void me(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)return ;

    fa[x] = y;
    siz[y] += siz[x];
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        siz[i] = 1;
    }
    string a;
    cin >> a;
    a = "Q" + a;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        if (a[u] == a[v] && a[u] == '1') {
            me(u, v);
        }
    }

    ll sum = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] == '1') {
            int k = find(i);
            if (!vis[k]) {
                vis[k] = true;
                sum += siz[k] * (siz[k] - 1) / 2;
            }
        }
    }

    ll ans = 0, pos = 0;

    for (int i = 1; i <= n; i++) {
        if (a[i] == '0') {
            set<int>st;
            for (auto k : g[i]) {
                if (a[k] == '1') {
                    st.insert(find(k));
                }
            }

            ll w = sum, t = 1;
            for (auto x : st) {
                w -= siz[x] * (siz[x] - 1) / 2;
                t += siz[x];
            }

            w += t * (t - 1) / 2;
            
            if (ans < w) {
                ans = w;
                pos = i;
            }
        }
    }
    cout << pos << " " << ans;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}