A Hamiltonian path on a directed graph is a path that visits every node exactly once. This algorithm finds Hamiltonian paths on arbitrary graphs by converting the problem to an instance of SAT and invoking an efficient SAT solver.

Input

This algorithm accepts a first argument (the graph) and an optional boolean second argument. If the second argument is true, a Hamiltonian cycle is returned. By default (or if the second argument is false), a Hamiltonian path is returned.

The graph is specified as an adjacency list---that is, a map where keys are vertex names (strings) and values are lists of neighbor vertices (strings). For example, the map { "a": ["b", "c"] } represents a graph with three vertices (a, b, and c) and two edges (a->b and a->c).

Note that the input graph is directed. To represent an undirected graph, just include both directions for every edge. Also note that self-edges and multi-edges are allowed, but for obvious reasons are never used in a Hamiltonian path.

Output

The output is a list of vertex names forming a path. If a Hamiltonian cycle was requested, the first vertex is repeated at the end of the list. If a Hamiltonian path/cycle does not exist on the graph, null is returned.