Given an 8-pint jug full of water and two empty jugs of 5- and 3- pint capacity, get exactly 4 pints of water in one of the jugs by completely filling up and/or emptying jugs into others. Define a graph that represents this puzzle and then solve the puzzle by using breadth-first search on the graph. Follow the following plan:

Answer each of the following:

1) Let the nodes of the graphs be triples of nonnegative integers representing the volume of water in each jar at all possible configurations. What are the restrictions on these integers for a given node?

2)Connect two nodes if one can be obtained from the other by pouring water from one jar to another until either the second is full or the first is empty. What are the restrictions on the integers of two nodes connected by an edge?

3)Perform BFS on the above graph until a solution is reached. How many layers do you need? Write the nodes each layer contains. For each node in each layer, indicate (in parentheses) its parent in the BFS tree. Describe the steps of the solution.