uDebug 上的两个样例都通过了，题解也合拍过了...
但是一直 WA ，不清楚是哪里出问题了QAQ 感觉就是一道普通的 IDDFS 啊...

#include <bits/stdc++.h>
#define _for(A, B, C) for(int A = (B);A < (C);A++)
using namespace std;

int n;
//输入的图。输入后就不再改变，只用degree[]代表打开状态
bool G[15][15];
//每个节点的度数，-1表示该节点已被打开
int degree[15];
#define OPENED_DEGREE -1
//最大深度
int maxDepth;


#define NO_SEARCHED 0

//节点的编号，用于计算连通块
int idx[15];

//遍历图，标记连通个数，并在遇到回环时返回false
bool topo(int lastOne, int startNode, int id) {
    idx[startNode] = -id;
    if (degree[startNode] == 0)return true;
    bool ok = true;
    _for(i, 0, n) {
        if (G[startNode][i] && degree[i] > 0) {
            if (idx[i] == -id && i != lastOne)ok = false;
            if (idx[i] == NO_SEARCHED && !topo(startNode, i, id))ok = false;
        }
    }
    idx[startNode] = id;
    return ok;
}

inline bool legal() {
    //已打开的环的数目（包括原先是单个环，但是已经打开的情况）
    int openCnt = 0;
    _for(i, 0, n) {
        if (degree[i] == OPENED_DEGREE)openCnt++;
        if (degree[i] > 2)return false;
    }

    memset(idx, NO_SEARCHED, sizeof(idx));

    //连通块个数
    int cnt = 0;
    _for(i, 0, n) {
        if (idx[i] == NO_SEARCHED) {
            if (!topo(-1, i, ++cnt))return false;
        }
    }

    //满足该条件才能全部连接上
    return (openCnt << 1) + 1 >= cnt;
}

//第cur层，从from开始枚举
bool IDDFS(int from, int cur) {
    if (cur == maxDepth) {
        //判断是否合法
        return legal();
    } else {
        int oriDegree[15];
        _for(i, from, n) {
            if (degree[i] == OPENED_DEGREE)continue;
            //保存之前的degree
            memcpy(oriDegree, degree, sizeof(degree));
            //标记为已打开
            degree[i] = OPENED_DEGREE;
            //更新其他degree
            _for(j, 0, n) {

                if (degree[j] > 0 && G[j][i]) {
                    degree[j]--;
                }
            }

            if (IDDFS(i + 1, cur + 1))return true;
            //还原之前的degree
            memcpy(degree, oriDegree, sizeof(degree));
        }
    }
    return false;
}

int solve() {
    for (maxDepth = 0; maxDepth <= n; ++maxDepth) {
        if (IDDFS(0, 0)) {
            return maxDepth;
        }
    }
    return -1;
}

int main() {
//    freopen("in.txt", "r", stdin);
    int k = 0;
    while (cin >> n && n) {
        memset(G, false, sizeof(G));
        memset(degree, 0, sizeof(degree));
        int a, b;
        while (cin >> a && cin >> b && a > 0 && b > 0) {
            a--, b--;
            if (G[a][b] || G[b][a])continue;
            G[a][b] = G[b][a] = true;
            degree[a]++;
            degree[b]++;
        }
        cout << "Set " << ++k << ": Minimum links to open is " << solve() << endl;
    }
    return 0;
}