import sys


class DSU:
    """路径压缩 + 按大小合并的并查集"""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x: int) -> int:
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:          # 路径压缩
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a: int, b: int) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    m = int(data[1])
    occupied = [c == 49 for c in data[2]]       # 49 是字符 '1' 的字节值

    edges = []
    pos = 3
    for _ in range(m):
        u = int(data[pos]) - 1
        v = int(data[pos + 1]) - 1
        pos += 2
        edges.append((u, v))

    graph = [[] for _ in range(n)]
    dsu = DSU(n)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
        if occupied[u] and occupied[v]:         # 只有两端都被占领才连通
            dsu.union(u, v)

    # 当前收益：每个已占领连通块贡献 C(s, 2)
    base = 0
    for i in range(n):
        if occupied[i] and dsu.find(i) == i:
            s = dsu.size[i]
            base += s * (s - 1) // 2

    best_city = -1
    best_total = -1
    for u in range(n):
        if occupied[u]:
            continue
        roots = set()
        for v in graph[u]:
            if occupied[v]:
                roots.add(dsu.find(v))
        joined = 1
        lost = 0
        for r in roots:
            s = dsu.size[r]
            joined += s
            lost += s * (s - 1) // 2
        total = base + joined * (joined - 1) // 2 - lost
        if total > best_total:                  # 严格大于，天然保留最小编号
            best_total = total
            best_city = u

    if best_city == -1:                         # 题目保证至少有一个未占领城市
        best_city, best_total = 0, base
    sys.stdout.write(f"{best_city + 1} {best_total}\n")


if __name__ == "__main__":
    solve()

示例推演

输入中 01010 表示只有 2 号、4 号城市已被占领。

当前并查集：2 号、4 号各自成块，大小都是 1，收益

base = \binom{1}{2} + \binom{1}{2} = 0

逐个尝试未占领的城市：

占领	相邻的已占领块	$S$	新增收益	总收益
1	{2}、{4}	$1+1+1=3$	$\binom{3}{2} - 0 - 0 = 3$	3
3	无（只连着 1 号，而 1 号未占领）	1	0	0
5	{4}	$1+1=2$	$\binom{2}{2} - 0 = 1$	1

最大是 3，对应的城市是 1 号。占领后 {1,2,4} 三城两两可经商，
恰好 3 对，与题面说明一致。输出 1 3。

复杂度分析

解法	时间复杂度	空间复杂度	说明
每次枚举新占领城市后重新求连通块	$O(n(n+m))$	$O(n+m)$	$n,m \le 10^5$ ，不可行
并查集 + 枚举	$O((n+m)\,\alpha(n))$	$O(n+m)$	推荐，每个点/边只处理常数次