public void solve()
	{
		// Pick a root
		this.treeRoot     = this.edges.keySet().iterator().next();
		this.subTreeSizes = new int[this.numVertices];

		Deque<Integer> traversal = new LinkedList<Integer>();
		// The post stack acts both as a way to figure out
		// the parent for our current node as well as a marker for
		// nodes that we've discovered but haven't processed yet
		Deque<Integer> post      = new LinkedList<Integer>();

		// Do a depth first traversal of the tree starting at treeRoot
		traversal.push(this.treeRoot);
		while (!traversal.isEmpty()) {
			Integer current = traversal.peek();
			if (post.peek() == current) {
				post.pop();
				traversal.pop();
				Integer parent = post.peek();
				if (parent == null) {
					continue;
				}
				int subTreeSize = 1 + sumChildNodes(parent, current);
				this.subTreeSizes[current] = subTreeSize;
			} else {
				Integer parent = post.peek();
				post.push(current); // mark node as discovered
				for (Integer child : this.edges.get(current)) {
					if (!child.equals(parent)) {
						traversal.push(child);
					}
				}
			}
		}
		
		// Calculate the number of possible cuts
		int numSubTrees = 0;
		for (int subTreeSize : this.subTreeSizes) {
			if (subTreeSize % 2 == 0 && (this.numVertices - subTreeSize) % 2 == 0) {
				++numSubTrees;
			}
		}
		System.out.println(numSubTrees - 1);
	}