Minimize Malware Spread

You are given graph, an n x n adjacency matrix describing a network of n computers, where graph[i][j] == 1 means computers i and j are directly connected (the matrix is symmetric and graph[i][i] == 1 for all i). You are also given initial, a list of distinct computer indices that are already infected with malware.

Malware spreads through the network over time: any infected computer will eventually infect every other computer it is connected to, directly or indirectly through a chain of connections — that is, infection spreads throughout an entire connected component once any node in that component is infected. This spreading process runs to completion (nothing stops it once it starts).

Before the spreading finishes, you get to remove exactly one computer from the network entirely, along with all of its connections to other computers. Your goal is to pick the single node from initial whose removal minimizes the final number of infected computers after the malware finishes spreading through what remains of the network.

Return the index of that node. You must return a node that was itself in initial — removing some other, uninfected node is not a valid choice even if it would help. If several choices in initial all lead to the same (minimal) final infection count, return the smallest such index.

• Note that the node you remove is deleted from consideration entirely — it does not count toward the final infected total, and neither does any node that would otherwise die alongside its removed component if that component only contained infected nodes with no other survivors.

Examples

Example 1:

Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,3]

Output: 0

Explanation:

All four computers form a single connected chain: 0-1-2-3. Removing node 0 leaves the chain 1-2-3 with initial infection at node 3, which spreads to infect 1, 2, and 3 (3 computers total). Removing node 3 leaves the chain 0-1-2 with initial infection at node 0, which spreads to infect 0, 1, and 2 (also 3 computers). Both choices tie at 3 infected computers, so the smaller index, 0, is returned.

Example 2:

Input: graph = [[1,0,0,0,0],[0,1,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,1]], initial = [1,3]

Output: 1

Explanation:

There are three components: {0}, {1,2}, and {3,4}. Node 1 sits alone in its component among the infected nodes, so removing it saves both 1 and 2 from infection, leaving only 3 and 4 infected (2 total). Removing node 3 instead only prevents node 4 from being infected by node 3 directly, but node 1 still infects node 2, leaving 1, 2, and 4 infected via node 1's spread and the untouched node 3's own component partner surviving separately is not the case here since 3 is removed — the resulting infected set becomes {1,2} only 2 as well in some analyses, but since removing node 1 isolates a strictly larger uninfected-saved component (both 1 and 2 belong to the same infected component, while 3 and 4 are in a component with two infected seeds, meaning removing just one of them, 3, still leaves 4 infected by nothing since 4 is only connected to 3): removing node 1 yields infected set {3,4} (size 2) and removing node 3 yields infected set {1,2,4} (size 3), so node 1 is strictly better and is returned.

Constraints

• 2 <= n <= 300
• graph.length == graph[i].length == n
• graph[i][j] is either 0 or 1
• graph[i][i] == 1 for every i
• graph[i][j] == graph[j][i] for every i, j
• 1 <= initial.length <= n
• All values in initial are distinct and lie in the range [0, n - 1]