code: /*
   * Copyright (c) 2017, Hisao Tamaki
   */
  
  package tw.exact;
  
  import java.io.File;
  
  
  
  import java.io.FileNotFoundException;
  import java.io.FileOutputStream;
  import java.io.PrintStream;
  import java.lang.management.GarbageCollectorMXBean;
  import java.lang.management.ManagementFactory;
  import java.lang.management.ThreadMXBean;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Random;
  
  public class MainDecomposer {
    private static boolean VERBOSE = false;
  //  private static boolean VERBOSE = true;
    private static boolean DEBUG = false;
  //private static boolean debug = true;
  
    private static long time0;
  
    public static TreeDecomposition decompose(Graph g) {
      log("decompose n = " + g.n);
      if (g.n == 0) {
        TreeDecomposition td = new TreeDecomposition(0, -1, g);
        return td;
      }
  
      ArrayList<XBitSet> components = g.getComponents(new XBitSet());
      
      int nc = components.size();
      if (nc == 1) {
        return decomposeConnected(g);      
      }
      
      int invs[][] = new int[nc][];
      Graph graphs[] = new Graph[nc];
      
      for (int i = 0; i < nc; i++) {
        XBitSet compo = components.get(i);
        int nv = compo.cardinality();
        graphs[i] = new Graph(nv);
        invs[i] = new int[nv];
        int conv[] = new int[g.n];
        int k = 0;
        for (int v = 0; v < g.n; v++) {
          if (compo.get(v)) {
            conv[v] = k;
            invs[i][k] = v;
            k++;
          }
          else {
            conv[v] = -1;
          }
        }
        graphs[i].inheritEdges(g, conv, invs[i]);
      }
  
      TreeDecomposition td = new TreeDecomposition(0, 0, g);
      
      for (int i = 0; i < nc; i++) {
        TreeDecomposition td1 = decomposeConnected(graphs[i]);
        if (td1 == null) {
          return null;
        }
        td.combineWith(td1, invs[i], null);
      }
      return td;
    }
    
    public static TreeDecomposition decomposeConnected(Graph g) {
      log("decomposeConnected: n = " + g.n);
  
      if (g.n <= 2) {
        TreeDecomposition td = new TreeDecomposition(0, g.n - 1, g);
        td.addBag(g.all.toArray());
        return td;
      }
      
      Bag best = null;
      
      GreedyDecomposer.Mode[] modes = 
          new GreedyDecomposer.Mode[]{
              GreedyDecomposer.Mode.fill,
              GreedyDecomposer.Mode.defect,
              GreedyDecomposer.Mode.degree
              };
      
      for (GreedyDecomposer.Mode mode: modes) { 
        Bag whole = new Bag(g); 
  
        GreedyDecomposer mfd = new GreedyDecomposer(whole, mode);
  //      GreedyDecomposer mfd = new GreedyDecomposer(whole);
  
        mfd.decompose();
  
        log("greedy decomposition (" + mode + ") obtained with " +
              whole.nestedBags.size() + " bags and width " + 
              whole.width);
  
        whole.detectSafeSeparators();
  
        log(whole.countSafeSeparators() + " safe separators found ");
  
        whole.validate();
        
        whole.pack();
        
        whole.validate();
  
        log("the decomposition packed into " +
              whole.nestedBags.size() + " bags, separatorWidth = " + 
              whole.separatorWidth + ", max bag size = " + 
              whole.maxNestedBagSize());
  
        if (best == null ||
            whole.maxNestedBagSize() < best.maxNestedBagSize()) {
          best = whole;
        }
      }
  //    best = whole;
     
      //    whole.dump();
  
      int lowestPossible = best.separatorWidth;
      
      for (Bag bag: best.nestedBags) {
        if (bag.getWidth() > lowestPossible) {
          bag.makeRefinable();
          IODecomposer mtd = new IODecomposer(bag, g.minDegree(), g.n - 1);
          mtd.decompose();
          int w = bag.getWidth();
          if (w > lowestPossible) {
            lowestPossible = w;
          }
        }
      }
      
      log("flattening");
      
      best.flatten();
  
      log("the decomposition flattened into " +
            best.nestedBags.size() + " bags");
      
  //    whole.dump();
      
      return best.toTreeDecomposition();
    }
    
    static void log(String message) {
      if (VERBOSE) {
        System.out.println(message);
      }
    }
  
    public static void main(String[] args) {
      Graph g = Graph.readGraph(System.in);
      TreeDecomposition td = decompose(g);
      td.writeTo(System.out);
    }
  }
  