In a unique country with the following characteristics: 1.The country consists of numerous cities, some of which are interconnected by bus services. 2.The citizens are very poor and do not own private vehicles. 3.The cities are situated far apart, making it impractical to commute on foot. 4.Uber is the sole provider of inter-city bus services between major cities. Each city with an Uber service has a support team that manages buses departing from or arriving at their city.

One day, the country faces a viral outbreak. To prevent the virus from spreading between cities, you propose halting the Uber bus services. You suggest calling the Uber support teams in certain cities to cancel all buses departing from and arriving at those cities.

The government seeks your help to determine the minimum number of phone calls needed to disconnect all inter-city bus services. Additionally, if multiple cities provide the same number of bus services, the government prefers calling the city with the lower index.

Input Format: The first line will contain 2 space separated integers N and M, where:- N is the number of cities in that country and M is the number of inter-city bus services. Next M lines follow, each line consists of two integers A and B A and B denote that there is a two-way bus service between city A and city B.

Output Format: Output the minimum number of phone calls needed. Output the list of city indices where the calls will be made in increasing order

Input 1: 4 2 1 2 3 4 o/p -> [2 (1,3)]

Input 2: 4 6 3 2 3 4 3 1 2 4 2 1 4 1 o/p -> [3 (1, 2, 3)]

Input 3: 6 5 1 2 1 3 1 4 1 5 1 6 o/p -> [1 (1)]

-> my intial approach was basically, start exploring the node having maximum degree and min value, and if from that node i am able to reach that node mark it as visited and erase from set, plese find the code below

int main() { int n,m; cin>>n>>m;

vector adj(n+1); vector indegre(n+1,0); for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; indegre[u]++; indegre[v]++; adj[u].push_back(v); adj[v].push_back(u); }

set<pair<int,int>> min_call; for(int i=1;i<=n;i++){ min_call.insert({indegre[i],-i}); } vector vis(n+1,0);

while(min_call.size()){ pair<int,int> current_node = *min_call.rbegin(); int node = -current_node.second; int degree = current_node.first; int flag = 0; min_call.erase(current_node); if(degree==0||vis[node])continue;

for(auto it:adj[node]){ /// try to reach all node if(!vis[it]){

pair<int,int> prev_node = {indegre[it],-it};
min_call.erase(prev_node);
flag = 1;
if(indegre[it]-1>0){
  min_call.insert({indegre[it]-1,-it});
  indegre[it]--;
}

} } if(flag)vis[node]++; } for(int i=1;i<=n;i++)if(vis[i])cout<<i<<" "; return 0; }

this problem translate to min-vertax cover which is np hard problem, if i am wrong some where can anyone please provide me the correct approch , my approch will fail for this graph

1 2 1 3 2 3 2 4 3 4 3 5 4 5

all are edges of the graph, for this test case my approch ( greedy ) will give the ans as, {2,3,4}, but the actual ans is {1,3,4}