1 #include
     
       2  #include
      
        3  const int E = 2020; 4  const int N = 55; 5  struct edge { 6      int t, next; 7  }e[E]; 8  int head[E], tot, root[N], map[N], degree[N], n, left[E], right[E], top; 9  bool v[E];10  void init() {11      top = tot = 0;12      memset(degree, 0, sizeof(degree));13      memset(v, 0, sizeof(v));14      memset(head, -1, sizeof(head));15      for(int i = 1; i <= 50; ++i) {16          root[i] = i;17      }18  }19  int find(int a) {20      return a == root[a] ? a : (root[a] = find(root[a]));21  }22  void merge(int a, int b) {23      int aa = find(a);24      int bb = find(b);25      if(aa != bb) {26          if(aa < bb)27              root[bb] = aa;28          else29              root[aa] = bb;30      }31  }32 33  void addedge(int f, int t) {34      e[tot].t = t;35      e[tot].next = head[f];36      head[f] = tot++;37  }38  void dfs(int f) {39      for(int i = head[f]; i != -1; i = e[i].next) {40          if(!v[i]) {41              v[i] = 1;42              v[i ^ 1] = 1;43              dfs(e[i].t);44              left[top] = f;45              right[top++] = e[i].t;46          }47      }48  }49  void pri() {50      for(int i = n - 1; i >= 0; --i) {51          printf("%d %d\n", left[i], right[i]);52      }53  }54  int main() {55      int t, minnum, flag, ca;56      scanf("%d", &t);57      for(int ca = 1; ca <=t; ++ca) {58          init();59          minnum = 100;60          flag = 1;61          scanf("%d", &n);62          for(int i = 0; i < n; ++i) {63              int a, b;64              scanf("%d%d", &a, &b);65              addedge(a, b); addedge(b, a);66              degree[a]++; degree[b]++;67              merge(a,b);68              if(a < minnum) minnum = a;69              if(b < minnum) minnum = b;70          }71          for(int i = 1; i <= 50; ++i) {72              if(degree[i]) {73                  if(degree[i] % 2 != 0 || find(i) != minnum) {74                      flag = 0;75                      break;76                  }77              }78          }79          if(ca != 1)80              printf("\n");81          printf("Case #%d\n", ca);82          if(!flag)83              printf("some beads may be lost\n");84          else {85              dfs(minnum);86              pri();87          }88      }89      return 0;90  }