/*
 * Copyright (c) 2016, Hisao Tamaki and Hiromu Ohtsuka
 */
package tw.heuristic;

import java.io.BufferedReader;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * This class provides a representation of tree-decompositions of graphs.
 * It is based on the {@code Graph} class for the representation of graphs.
 * Members representing the bags and tree edges are all public.
 * Reading from and writing to files, in the .td format of PACE challeng,
 * are provided.  
 *
 * @author  Hisao Tamaki
 */

public class TreeDecomposition {
	/**
	 * number of bags
	 */
	public int nb;

	/**
	 * intended width of this decomposition
	 */
	public int width;

	/**
	 * the graph decomposed 
	 */
	public Graph g;

	/**
	 * array of bags, each of which is an int array listing vertices.
	 * The length of this array is {@code nb + 1} as the bag number (index)[
	 * starts from 1
	 */
	public int[][] bags;

	/**
	 * array of bags, each of which is an {@code VertexSet} representing
	 * the set of vertices in the bag. 
	 * The length of this array is {@code nb + 1} as the bag number (index)[
	 * starts from 1.
	 */
	public VertexSet[] bagSets;

	/**
	 * array of node degrees. {@code degree[i]} is the number of bags adjacent
	 * to the ith bag.    
	 * The length of this array is {@code nb + 1} as the bag number (index)[
	 * starts from 1.
	 */
	public int degree[];

	/**
	 * array of int arrays representing neighbor lists.
	 * {@code neighbor[i][j]} is the bag index (in {@bags} array) of 
	 * the jth bag adjacent to the ith bag.
	 * The length of this array is {@code nb + 1} as the bag number (index)[
	 * starts from 1.
	 */
	public int neighbor[][];

	private static boolean debug = false;

	/**
	 * Construct a tree decomposition with the specified number of bags,
	 * intended width, and the graph decomposed.
	 * @param nb the number of bags
	 * @param width the intended width
	 * @param g the graph decomposed
	 */
	public TreeDecomposition(int nb, int width, Graph g) {
		this.nb = nb;
		this.width = width;
		this.g = g;
		bags = new int[nb + 1][];
		degree = new int[nb + 1];
		neighbor = new int[nb + 1][];
	}

	/**
	 * Sets the ith bag to the given bag. 
	 * @param i the index of the bag. 1 <= i <= nb must hold
	 * @param bag int array representing the bag
	 */
	public void setBag(int i, int[] bag) {
		bags[i] = bag;
	}

	/**
	 * Adds the given bag. The number of bags {@code nb} is incremented.
	 * @param bag int array representing the bag to be added
	 */
	public int addBag(int[] bag) {
		nb++;
		if (debug) {
			System.out.print(nb + "th bag:");
		}
		for (int i = 0; i < bag.length; i++) {
			if (debug) {
				System.out.print(" " + bag[i]);
			}
		}
		if (debug) {
			System.out.println();
		}
		bags = Arrays.copyOf(bags, nb + 1);
		bags[nb] = bag;
		degree = Arrays.copyOf(degree, nb + 1);
		neighbor = Arrays.copyOf(neighbor, nb + 1);
		if (bagSets != null) {
			bagSets = Arrays.copyOf(bagSets, nb + 1);
			bagSets[nb] = new VertexSet(bag);
		}
		return nb;
	}

	/**
	 * Adds and edge
	 * the neighbor lists of both bags, as well as the degrees, 
	 * are updated  
	 * @param i index of one bag of the edge
	 * @param j index of the other bag of the edge
	 */
	public void addEdge(int i, int j) {
		if (debug) {
			System.out.println("add deomposition edge (" + i + "," + j + ")");
		}
		addHalfEdge(i, j);
		addHalfEdge(j, i);
	}

	/**
	 * Adds a bag to the neibhor list of another bag
	 * @param i index of the bag of which the neighbor list is updated
	 * @param j index of the bag to be added to {@code neighbor[i]}
	 */
	private void addHalfEdge(int i, int j) {
		if (neighbor[i] == null) {
			degree[i] = 1;
			neighbor[i] = new int[]{j};
		}
		else if (indexOf(j, neighbor[i]) < 0){
			degree[i]++;
			neighbor[i] = Arrays.copyOf(neighbor[i], degree[i]);
			neighbor[i][degree[i] - 1] = j;
		}
	}

	/**
	 * Combine the given tree-decomposition into this target tree-decomposition.
	 * The following situation is assumed. Let G be the graph for which this
	 * target tree-decomposition is being constructed. Currently, 
	 * this tree-decomposition contains bags for some subgraph of G.
	 * The tree-decomposition of some other part of G is given by the argument.
	 * The numbering of the vertices in the argument tree-decomposition differs
	 * from that in G and the conversion map is provided by another argument. 
	 * @param td tree-decomposition to be combined
	 * @param conv the conversion map, that maps the vertex number in the graph of
	 * tree-decomposition {@code td} into the vertex number of the graph of this 
	 * target tree-decomposition.
	 */
	public void combineWith(TreeDecomposition td, int conv[]) {
		this.width = Math.max(this.width, td.width);
		int nb0 = nb;
		for (int i = 1; i <= td.nb; i++) {
			addBag(convertBag(td.bags[i], conv));
		}
		for (int i = 1; i <= td.nb; i++) {
			for (int j = 0; j < td.degree[i]; j++) {
				int h = td.neighbor[i][j];
				addHalfEdge(nb0 + i, nb0 + h);
			}
		}
	}
	/**
	 * Combine the given tree-decomposition into this target tree-decomposition.
	 * The assumptions are the same as in the method with two parameters.
	 * The third parameter specifies the way in which the two parts
	 * of the decompositions are connected by a tree edge of the decomposition.
	 * 
	 * @param td tree-decomposition to be combined
	 * @param conv the conversion map, that maps the vertex number in the graph of
	 * tree-decomposition {@code td} into the vertex number of the graph of this 
	 * target tree-decomposition.
	 * @param v int array listing vertices: an existing bag containing all of
	 * these vertices and a bag in the combined part containing all of
	 * these vertices are connected by a tree edge; if {@code v} is null
	 * then first bags of the two parts are connected 
	 */
	public void combineWith(TreeDecomposition td, int conv[], int v[]) {
		this.width = Math.max(this.width, td.width);
		int nb0 = nb;
		for (int i = 1; i <= td.nb; i++) {
			addBag(convertBag(td.bags[i], conv));
		}
		for (int i = 1; i <= td.nb; i++) {
			for (int j = 0; j < td.degree[i]; j++) {
				int h = td.neighbor[i][j];
				addEdge(nb0 + i, nb0 + h);
			}
		}
		if (v == null) {
			addEdge(1, nb0 + 1);
		}
		else {
			int k = findBagWith(v, 1, nb0);
			int h = findBagWith(v, nb0 + 1, nb);
			if (k < 0) {
				System.out.println(Arrays.toString(v) + " not found in the first " + nb0 + " bags");
			}
			if (h < 0) {
				System.out.println(Arrays.toString(v) + " not found in the last " + td.nb + " bags");
			}
			addEdge(k, h);
		}
	}

	/**
	 * Converts the vetex number in the bag
	 * @param bag input bag
	 * @param conv conversion map of the vertices
	 * @return the bag resulting from the conversion,
	 * containing {@code conv[v]} for each v in the original bag
	 */

	private int[] convertBag(int bag[], int conv[]) {
		int[] result = new int[bag.length];
		for (int i = 0; i < bag.length; i++) {
			result[i] = conv[bag[i]];
		}
		return result;
	}

	/**
	 * Find a bag containing all the listed vertices,
	 * with bag index in the specified range
	 * @param v int array listing vertices
	 * @param s the starting bag index
	 * @param t the ending bag index
	 * @return index of the bag containing all the
	 * vertices listed in {@code v}; -1 if none of the
	 * bags {@code bags[i]}, s <= i <= t, satisfies this
	 * condition.
	 */
	private int findBagWith(int v[], int s, int t) {
		for (int i = s; i <= t; i++) {
			boolean all = true;
			for (int j = 0; j < v.length; j++) {
				if (indexOf(v[j], bags[i]) < 0) {
					all = false;
				}
			}
			if (all) return i;
		}
		return -1;
	}

	/**
	 * write this tree decomposition to the given print stream
	 * in the PACE .td format
	 * @param ps print stream
	 */
	public void writeTo(PrintStream ps) {
    StringBuilder sb = new StringBuilder();
		//ps.println("s td " + nb + " " + (width + 1) + " " + g.n);
    sb.append("s td " + nb + " " + (width + 1) + " " + g.n + "\n");
		for (int i = 1; i <= nb; i++) {
			//ps.print("b " + i);
      sb.append("b " + i);
			for (int j = 0; j < bags[i].length; j++) {
				//ps.print(" " + (bags[i][j] + 1));
        sb.append(" " + (bags[i][j] + 1));
			}
      sb.append("\n");
			//ps.println();
		}
		for (int i = 1; i <= nb; i++) {
			for (int j = 0; j < degree[i]; j++) {
				int h = neighbor[i][j];
				if (i < h) {
					//ps.println(i + " " + h);
          sb.append(i + " " + h + "\n");
				}
			}
		}
    ps.print(sb.toString());
    ps.flush();
	}

	/**
	 * validates this target tree-decomposition
	 * checking the three required conditions
	 * The validation result is printed to the
	 * standard output
	 */
	public void validate() {
		System.out.println("validating nb = " + nb + ", ne = " + numberOfEdges());
		boolean error = false;
		if (!isConnected()) {
			System.out.println("is not connected ");
			error = true;
		}
		if (isCyclic()) {
			System.out.println("has a cycle ");
			error = true;
		}
		if (tooLargeBag()) {
			System.out.println("too Large bag ");
			error = true;
		}
		int v = missinVertex();
		if (v >= 0) {
			System.out.println("a vertex " + v + " missing ");
			error = true;
		}
		int edge[] = missingEdge(); 
		if (edge != null) {
			System.out.println("an edge " + Arrays.toString(edge) + " is missing ");
			error = true;
		}
		if (violatesConnectivity()) {
			System.out.println("connectivety property is violated ");
			error = true;
		}
		if (!error) {
			System.out.println("validation ok");
		}
	}

	public boolean isValid(PrintStream ps) {
		ps.println("validating nb = " + nb + ", ne = " + numberOfEdges());
		boolean error = false;
		if (!isConnected()) {
			ps.println("is not connected ");
			error = true;
		}
		if (isCyclic()) {
			ps.println("has a cycle ");
			error = true;
		}
		if (tooLargeBag()) {
			ps.println("too Large bag ");
			error = true;
		}
		int v = missinVertex();
		if (v >= 0) {
			ps.println("a vertex " + v + " missing ");
			error = true;
		}
		int edge[] = missingEdge(); 
		if (edge != null) {
			ps.println("an edge " + Arrays.toString(edge) + " is missing ");
			error = true;
		}
		if (violatesConnectivity()) {
			ps.println("connectivety property is violated ");
			error = true;
		}
		if (!error) {
			ps.println("validation ok");
		}
		return !error;
	}

	/**
	 * Checks if this tree-decomposition is connected as
	 * a graph of bags
	 * @return {@code true} if this tree-decomposition is connected
	 * {@cdoe false} otherwise
	 */

	private boolean isConnected() {
		boolean mark[] = new boolean [nb + 1];
		depthFirst(1, mark);
		for (int i = 1; i <= nb; i++) {
			if (!mark[i]) {
				return false;
			}
		}
		return true;
	}

	private void depthFirst(int i, boolean mark[]) {
		mark[i] = true;
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			if (!mark[j]) {
				depthFirst(j, mark);
			}
		}
	}

	/**
	 * Checks if this tree-decomposition is acyclic as
	 * a graph of bags
	 * @return {@code true} if this tree-decomposition is acyclic
	 * {@cdoe false} otherwise
	 */

	private boolean isCyclic() {
		boolean mark[] = new boolean [nb + 1];
		return isCyclic(1, mark, 0);
	}

	private boolean isCyclic(int i, boolean mark[], 
			int parent) {
		mark[i] = true;
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			if (j == parent) {
				continue;
			}
			if (mark[j]) {
				return true;
			}
			else {
				boolean b = isCyclic(j, mark, i);
				if (b) return true;
			}
		}
		return false;
	}

	/**
	 * Checks if the bag size is within the declared
	 * tree-width plus one
	 * @return {@code true} if there is some violating bag,
	 * {@cdoe false} otherwise
	 */
	private boolean tooLargeBag() {
		for (int i = 1; i <= nb; i++) {
			if (bags[i].length > width + 1) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Finds a vertex of the graph that does not appear
	 * in any of the bags
	 * @return the missing vertex number; -1 if there is no
	 * missing vertex
	 */
	private int missinVertex() {
		for (int i = 0; i < g.n; i++) {
			if (!appears(i)) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * Checks if the given vertex appears in some bag
	 * of this target tree-decomposition
	 * @param v vertex number
	 * @return {@cod true} if vertex {@code v} appears in 
	 * some bag
	 */
	private boolean appears(int v) {
		for (int i = 1; i <= nb; i++) {
			if (indexOf(v, bags[i]) >= 0) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Checks if there is some edge not appearing in any
	 * bag of this target tree-decomposition
	 * @return two element int array representing the
	 * missing edge; null if there is no missing edge
	 */
	private int[] missingEdge() {
		for (int i = 0; i < g.n; i++) {
			for (int j = 0; j < g.degree[i]; j++) {
				int h = g.neighbor[i][j];
				if (!appears(i, h)) {
					return new int[]{i, h};
				}
			}
		}
		return null;
	}

	/** 
	 * Checks if the edge between the two specified vertices
	 * appear in some bag of this target tree-decomposition
	 * @param u one endvertex of the edge
	 * @param v the other endvertex of the edge
	 * @return {@code true} if this edge appears in some bag; 
	 * {@code false} otherwise 
	 */
	private boolean appears(int u, int v) {
		for (int i = 1; i <= nb; i++) {
			if (indexOf(u, bags[i]) >= 0 &&
					indexOf(v, bags[i]) >= 0) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Checks if this target tree-decomposition violates
	 * the connectivity condition for some vertex of the graph
	 * @return {@code true} if the condition is violated
	 * for some vertex; {@code false} otherwise.
	 */
	private boolean violatesConnectivity() {
		for (int v = 1; v <= g.n; v++) {
			if (violatesConnectivity(v)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Checks if this target tree-decomposition violates
	 * the connectivity condition for the given vertex {@code v}
	 * @param v vertex number
	 * @return {@code true} it the connectivity condition is violated
	 * for vertex {@code v}
	 */
	private boolean violatesConnectivity(int v) {
		boolean mark[] = new boolean[nb + 1];

		for (int i = 1; i <= nb; i++) {
			if (indexOf(v, bags[i]) >= 0) {
				markFrom(i, v, mark);
			}
		}

		for (int i = 1; i <= nb; i++) {
			if (!mark[i] && indexOf(v, bags[i]) >= 0) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Mark the tree nodes (bags) containing the given vertex
	 * that are reachable from the bag numbered {@code i}, 
	 * without going through the nodes already marked 
	 * @param i bag number
	 * @param v vertex number
	 * @param mark boolean array recording the marks: 
	 * {@code mark[v]} represents if vertex {@code v} is marked
	 */
	private void markFrom(int i, int v, boolean mark[]) {
		if (mark[i]) {
			return;
		}
		mark[i] = true;

		for (int j = 0; j < degree[i]; j++) {
			int h = neighbor[i][j];
			if (indexOf(v, bags[h]) >= 0) {
				markFrom(h, v, mark);
			}
		}
	}

	/**
	 * Simplify this target tree-decomposition by
	 * forcing the intersection between each pair of
	 * adjacent bags to be a minimal separator
	 */

	public void minimalize() {
		if (bagSets == null) {
			bagSets = new VertexSet[nb + 1];
			for (int i = 1; i <= nb; i++) {
				bagSets[i] = new VertexSet(bags[i]);
			}
		}
		for (int i = 1; i <= nb; i++) {
			for (int a = 0; a < degree[i]; a++) {
				int j = neighbor[i][a];
				VertexSet separator = bagSets[i].intersectWith(bagSets[j]);
				VertexSet iSide = new VertexSet(g.n);
				collectVertices(i, j, iSide);
				iSide.andNot(separator);
				VertexSet neighbors = g.neighborSet(iSide);
				VertexSet delta = separator.subtract(neighbors);
				bagSets[i].andNot(delta);
			}
		}
		for (int i = 1; i <= nb; i++) {
			bags[i] = bagSets[i].toArray();
		}
	}

	/**
	 * Collect vertices in the bags in the specified
	 * subtree of this target tree-decomposition
	 * @param i the bag index of the root of the subtree
	 * @param exclude the index in the adjacency list
	 * the specified bag, to be excluded from the subtree 
	 * @param set the {@VertexSet} in which to collect the 
	 * vertices
	 */
	private void collectVertices(int i, int exclude, VertexSet set) {
		set.or(bagSets[i]);
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			if (j != exclude) {
				collectVertices(j, i, set);
			}
		}
	}

	/**
	 * Canonicalize this target tree-decomposition by
	 * forcing every bag to be a potential maximal clique.
	 * A naive implementation with no efficiency considerations.
	 */

	public void canonicalize() {
		if (bagSets == null) {
			bagSets = new VertexSet[nb + 1];
			for (int i = 1; i <= nb; i++) {
				bagSets[i] = new VertexSet(bags[i]);
			}
		}
		boolean moving = true;
		while (moving) {
			moving = false;
			int i = 1;
			while (i <= nb) {
				if (trySplit(i)) {
					moving = true;
				}
				i++;
			}
		}
	}

	private boolean trySplit(int i) {
		VertexSet neighborSets[] = new VertexSet[g.n];
		VertexSet b = bagSets[i];
		ArrayList<VertexSet> components = g.getComponents(b);
		VertexSet seps[] = new VertexSet[components.size()];
		for (int j = 0; j < seps.length; j++) {
			seps[j] = g.neighborSet(components.get(j)).intersectWith(b);
		}

		for (int v = b.nextSetBit(0); v >= 0; 
				v = b.nextSetBit(v + 1)) {
			VertexSet ns = g.neighborSet[v].intersectWith(b);
			for (VertexSet sep: seps) {
				if (sep.get(v)) {
					ns.or(sep);
				}
			}
			ns.clear(v);
			neighborSets[v] = ns.intersectWith(b);
		}

		for (int v = b.nextSetBit(0); v >= 0;
				v = b.nextSetBit(v + 1)) {
			VertexSet left = neighborSets[v];
			left.set(v);
			VertexSet right = b.subtract(left);
			if (right.isEmpty()) {
				continue;
			}
			VertexSet separator = new VertexSet(g.n);
			for (int w = right.nextSetBit(0); w >= 0;
					w = right.nextSetBit(w + 1)) {
				separator.or(neighborSets[w]);
			}
			right.or(separator);

			int j = addBag(right.toArray());

			bags[i] = left.toArray();
			bagSets[i] = left;

			int ni = 0;
			int nj = 0;
			neighbor[j] = new int[degree[i]];
			for (int k = 0; k < degree[i]; k++) {
				int h = neighbor[i][k];
				if (bagSets[h].intersects(left)) {
					neighbor[i][ni++] = h;
				}
				else {
					neighbor[j][nj++] = h;
				}
			}
			degree[i] = ni;
			degree[j] = nj;
			neighbor[i] = Arrays.copyOf(neighbor[i], ni);
			neighbor[j] = Arrays.copyOf(neighbor[j], nj);

			addEdge(i, j);

			for (int k = 0; k < nj; k++) {
				int h = neighbor[j][k];
				for (int l = 0; l < degree[h]; l++) {
					if (neighbor[h][l] == i) {
						neighbor[h][l] = j;
					}
				}
			}
			return true;
		}
		return false;
	}

	/**
	 * Tests if the target tree-decomposition is canonical,
	 * i.e., consists of potential maximal cliques.
	 */

	public boolean isCanonical() {
		for (int i = 1; i <= nb; i++) {
			if (!isCanonicalBag(new VertexSet(bags[i]))) {
				return false;
			}
		}
		return true;
	}

	private boolean isCanonicalBag(VertexSet b) {
		ArrayList<VertexSet> components = g.getComponents(b);

		for (int v = b.nextSetBit(0); v >= 0; 
				v = b.nextSetBit(v + 1)) {
			for (int w = b.nextSetBit(v + 1); w >= 0; 
					w = b.nextSetBit(w + 1)) {
				if (g.neighborSet[v].get(w)) {
					continue;
				}
				boolean covered = false;
				for (VertexSet compo: components) {
					VertexSet ns = g.neighborSet(compo);
					if (ns.get(v) && ns.get(w)) {
						covered = true;
						break;
					}
				}
				if (!covered) {
					return false;
				}
			}
		}
		return true;
	}

	public void analyze(int rootIndex) {
		if (bagSets == null) {
			bagSets = new VertexSet[nb + 1];
			for (int i = 1; i <= nb; i++) {
				bagSets[i] = new VertexSet(bags[i]);
			}
		}

		analyze(rootIndex, -1);
	}

	private void analyze(int i, int exclude) {
		System.out.println(i + ": " + bagSets[i]);
		VertexSet separator = bagSets[i];
		VertexSet set[] = new VertexSet[degree[i]];

		ArrayList<VertexSet> components = g.getComponents(separator);
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			set[a] = new VertexSet(g.n);
			collectVertices(j, i, set[a]);
		}
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			if (j != exclude) {
				System.out.println("  subtree at " + j);
				for (VertexSet compo: components) {
					if (compo.isSubset(set[a])) {
						System.out.println("    contains " + compo);
					}
					else if (compo.intersects(set[a])) {
						System.out.println("    intersects " + compo);
						System.out.println("    but missing " + 
								compo.subtract(set[a]));
					}
				}
			}
		}
		for (VertexSet compo: components) {
			boolean intersecting = false;
			for (int a = 0; a < degree[i]; a++) {
				if (compo.intersects(set[a])) {
					intersecting = true;
				}
			}
			if (!intersecting) {
				System.out.println("  component totally missing: " +
						compo);
			}
		}
		for (int a = 0; a < degree[i]; a++) {
			int j = neighbor[i][a];
			if (j != exclude) {
				analyze(j, i);
			}
		}
	}

	/**
	 * Computes the number of tree edges of this tree-decomosition,
	 * which is the sum of the node degrees divides by 2
	 * @return the number of edges
	 */
	private int numberOfEdges() {
		int count = 0;
		for (int i = 1; i <= nb; i++) {
			count += degree[i];
		}
		return count / 2;
	}
	/**
	 * Finds the index at which the given element
	 * is found in the given array.
	 * @param x int value to be searched
	 * @param a int array in which to find {@code x}
	 * @return {@code i} such that {@code a[i] == x};
	 * -1 if none such index exists
	 */

	private int indexOf(int x, int a[]) {
		return indexOf(x, a, a.length);
	}

	/**
	 * Finds the index at which the given element
	 * is found in the given array.
	 * @param x int value to be searched
	 * @param a int array in which to find {@code x}
	 * @param n the number of elements to be searched
	 * in the array
	 * @return {@code i} such that {@code a[i] == x} and
	 * 0 <= i <= n; -1 if none such index exists
	 */
	private int indexOf(int x, int a[], int n) {
		for (int i = 0; i < n; i++) {
			if (x == a[i]) {
				return i;
			}
		}
		return -1;
	}

	/**
	 * Reads the tree-decomposition for a given graph from
	 * a file at a given path and with a given name, in the
	 * PACE .gr format; the extension .gr is added to the name.
	 * @param path path at which the file is found
	 * @param name file name, without the extension
	 * @param g graph
	 * @return the tree-decomposition read
	 */
	public static TreeDecomposition readDecomposition(String path, String name, Graph g) {
		File file = new File(path + "/" + name + ".td");
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line = br.readLine();
			while (line.startsWith("c")) {
				line = br.readLine();
			}
			if (line.startsWith("s")) {
				String s[] = line.split(" ");
				if (!s[1].equals("td")) {
					throw new RuntimeException("!!Not treewidth solution " + line);
				}
				int nb = Integer.parseInt(s[2]);
				int width = Integer.parseInt(s[3]) - 1;
				int n = Integer.parseInt(s[4]);

				System.out.println("nb = " + nb + ", width = " + width + ", n = " + n);
				TreeDecomposition td = new TreeDecomposition(0, width, g);

				for (int i = 0; i < nb; i++) {
					line = br.readLine();
					while (line.startsWith("c")) {
						line = br.readLine();
					}
					s = line.split(" ");

					if (!s[0].equals("b")) {
						throw new RuntimeException("!!line starting with 'b' expected");
					}

					if (!s[1].equals(Integer.toString(i + 1))) {
						throw new RuntimeException("!!Bag number " + (i + 1) + " expected");
					}

					int bag[] = new int[s.length - 2];
					for (int j = 0; j < bag.length; j++) {
						bag[j] = Integer.parseInt(s[j + 2]) - 1;
					}
					td.addBag(bag);
				}

				while (true) {
					line = br.readLine();
					while (line != null && line.startsWith("c")) {
						line = br.readLine();
					}
					if (line == null) {
						break;
					}

					s = line.split(" ");

					int j = Integer.parseInt(s[0]);
					int k = Integer.parseInt(s[1]);

					td.addEdge(j, k);
					td.addEdge(k, j);
				}

				return td;
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return null;
	}
}
