import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;


public class GraphSearch {

	TreeMap<String, List<String>> myGraph = new TreeMap<String, List<String>>();

	public GraphSearch(String[] dependencies){
		int vertex = 0;
		for(String s : dependencies)
		{
			String sv = "" + vertex;
			vertex++;
			List<String> list = new ArrayList<String>();	
			if (s.equals("")) continue;           // no vertices, don't parse
			String[] a = s.split(" ");

			for (String nextv : a){
				list.add(nextv);
			}

			myGraph.put(sv, list);
		}
	}

	public void dfs(String vertex, int target){
		Set<String> visited = new TreeSet<String>();
		if(dfs(vertex, visited, target)){
			System.out.print("Starting at " + vertex + ", a path that sums to " + target + ": ");
			for(String s: visited)
				System.out.print(s + " ");
			System.out.println();
		}
		else{
			System.out.println("Starting at " + vertex + ", there is no path that sums to " + target);
		}
	}

	private boolean dfs(String vertex, Set<String> visited, int target){
		if(target == 0) return true;
		if(target < 0) return false;
		if(visited.contains(vertex)) return false;
	
		visited.add(vertex);
		target = target - Integer.parseInt(vertex);

		for(String adj: myGraph.get(vertex)){
			if (dfs(adj, visited, target)) return true;
		}
		visited.remove(vertex);
		return false;
	}


	public static void main(String[] args){
		String[] dependencies = {"1 2 3", "0 4 5", "0 6", "0 5", "1", "1 3", "2"};
		GraphSearch g = new GraphSearch(dependencies);
		g.dfs("1", 5);
	}
}