#include <cassert>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
typedef pair<unsigned, unsigned> TEdge;
typedef vector<TEdge> TEdges;
typedef vector<unsigned> TEdgeSubset;
typedef set<unsigned> TVertexSet;
bool next_subset(TEdgeSubset &subset, unsigned n)
{
unsigned overflow = n;
auto it = subset.end();
do
{
--it;
if (++*it < overflow || it == subset.begin())
break;
--overflow;
} while (true);
assert(*it <= overflow);
if (*it == overflow)
return false;
for (++it, ++overflow; it != subset.end(); ++it, ++overflow)
{
*it = *(it - 1) + 1;
assert(*it < overflow);
}
return true;
}
int main()
{
istringstream ss("11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11");
// Read edges
unsigned N, P;
ss >> N >> P;
assert(P <= N);
TEdges edges;
do
{
TEdge e;
if (!(ss >> e.first >> e.second))
break;
assert(e.first > 0 && e.second > 0);
--e.first;
--e.second;
assert(e.first < N && e.second < N);
edges.push_back(e);
} while (true);
if (edges.size() < N - 1)
{
cout << "Invalid input data - disonnected village" << endl;
return EXIT_FAILURE;
}
if (edges.size() > N - 1)
{
cout << "Invalid input data - excessive roads" << endl;
return EXIT_FAILURE;
}
// Iterate
unsigned min_degree = -1;
TVertexSet min_vsubset;
TEdgeSubset esubset(P - 1);
{ // Initial edge subset
unsigned n = 0;
generate(esubset.begin(), esubset.end(), [&n](){ return n++; });
}
do
{
// Generate vertex subset
TVertexSet vsubset;
for (unsigned i : esubset)
{
const TEdge &e = edges[i];
vsubset.insert(e.first);
vsubset.insert(e.second);
}
assert(vsubset.size() >= P);
if (vsubset.size() > P)
// Disconnected edges
continue;
// Calculate external degree
unsigned degree = 0;
for (const TEdge &e : edges)
if ((vsubset.find(e.first) == vsubset.end()) != (vsubset.find(e.second) == vsubset.end()))
++degree;
if (degree < min_degree)
{
min_degree = degree;
min_vsubset = vsubset;
}
} while (next_subset(esubset, edges.size()));
if (min_degree == -1)
cout << "No solution" << endl;
else
{
cout << "Destroy " << min_degree << " road(s)" << endl;
cout << "Isolated houses: ";
for (unsigned i : min_vsubset)
cout << i + 1 << " ";
cout << endl;
}
return 0;
}