#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define N 30
#define INF 0x3f3f3f3f
#define _for(i,a,b) for (int i = (a); i < (b); ++i)
int n, cnt;
int vis[N], ma[N][N];
vector<int> G[N];
void init() {
int u, v;
memset(ma, 0, sizeof(ma));
_for (i, 0, N) G[i].clear();
while (scanf("%d%d", &u, &v) != EOF && u != -1) {
if (!ma[u][v]) {
G[u].push_back(v); G[v].push_back(u);
ma[u][v] = 1; ma[v][u] = 1;
}
}
}
int num(int x) {
return x == 0 ? 0 : num(x / 2) + (x & 1);
}
bool dfs(int i, int s, int f) {
if (vis[i]) return true;
vis[i] = 1;
_for (j, 0, G[i].size()) {
int v = G[i][j];
if (v == f) continue;
if ((1 << (v - 1) & s)) continue;
if (dfs(v, s, i)) return true;
}
return false;
}
bool check(int s) {
for (int i = 1; i <= n; ++i) {
int res = 0;
if ((1 << (i - 1)) & s) continue;
_for (j, 0, G[i].size()) {
int v = G[i][j];
if ((1 << (v - 1)) & s) continue;
++res;
}
if (res > 2) return true;
}
cnt = 0;
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; ++i) {
if ((1 << (i - 1)) & s) continue;
if (vis[i]) continue;
++cnt;
if (dfs(i, s, -1)) {
return true;
}
}
return false;
}
int slove() {
int ans = INF;
_for (i, 0, (1 << n)) {
if (!check(i)) {
if (num(i) >= cnt - 1) {
ans = min(ans, num(i));
}
}
}
return ans;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int kase = 0;
while (scanf("%d", &n) == 1 && n) {
init();
printf("Set %d: Minimum links to open is %d\n", ++kase, slove());
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)