Commander's Dilemma

Problem Statement

Commander's Dilemma Problem Description The nation of Eryndor is at war. Its territory consists of N cities connected by M bidirectional roads. The cities are numbered from 1 to N. Each city has a strategic value, and the generals must choose a subset of cities to defend. But there's a catch: Once a city is defended, all cities directly connected to it (via a single road) are automatically considered secured. The enemy is known to avoid secured cities. To maximize resistance, the generals aim to maximize the total strategic value of directly defended cities (i.e., cities chosen for defense, not the ones that become secured as a side effect). Your task is to determine the maximum total strategic value that can be achieved by selecting a subset of cities to defend, such that No two defended cities are directly connected (they must not share a road). All other cities may or may not be defended, depending on the plan. Note: The graph does not contain multiple edges between the same nodes o