Need help with this graph problem

Problem: In an imaginary world, there are N cities governed by K countries. Some of the cities have direct connection between each other and some do not. Moreover, territorial integrity is not an important issue for the countries.
A person named Luke, who lives in one of the cities, is not happy with any of these regimes in the whole world.
He/She plans to organize a group of people in arbitrary M cities (each of the pairs in these cities can be reached by only using the paths between these M many cities, so it has territorial integrity), to start a riot and to found his/her own kingdom with these M cities included. The problem is that the more number of distinct neighbors (number if countries that are connected to the M many cities) that the new kingdom have, the more threats are present for the new country. Thus, Luke wants the number of distinct neighbors as small as possible.
(a) Given the cities, their direct connections (if there are any), their country information, and the number M can you find the optimal set of cities that this new kingdom should be founded? How many number of distinct neighbors does this city have?

Input Format: The first line includes number of cities N and the second line indicates total number of connections E between these cities. The third line contains the number M. The next V lines have 2 numbers indicating the city id and the kingdom id which rules the city. The format is: ”city id kingdom id”. The next E lines indicate the cities that are connected with each other directly. The format is: ”city 1 id city 2 id”.

1 <= N, M, K <= 1000000

(Note: The graph is undirected & unweighted)

I’m not able to think of even a sub-optimal solution. Can someone please help?

Can you share the problem link? Looks like you are asking problem from some contest which might be on-going.

No, it isn’t from any live contest. It was asked in my friend’s college OJ. You can crosscheck from the live contests here: If you still remain concerned about it being from live contest, you can come back after for few days or weeks for that matter. I’ll ping this post several weeks later if it doesn’t get an answer by then, so no worries. cheers

It’s been more than a month now. Care to help? (As a sidenote, please refrain from unnecessary judgements if not sure)

Can you give some sample test case so it becomes easy to understand the problem .

Directly connected to M cities or indirectly connected ?