Solve the Towers of Hanoi game for the following graph G=(V,E) with V={Start, Aux 1, Aux2, Aux3, Aux4, Dest} and E = {(Start,Auxl), (Auxl,Aux2), (Aux2,Aux1), (Aux2,Aux3), (Aux3,Aux2), (Aux3,Dest)}.

Design an algorithm and determine the time and space complexities of moving n disks from Start to Dest.

Implement this algorithm whereby your program prints out each of the moves of every disk. Show the output for n=1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. (If the output is too long, print out only the first 100 and the last 100 moves.)

Disk movement must follow E, using the 5 pegs in V.

Pegs can be moved:

START > peg1 <> peg 2 <> peg3 > END

Desired output, assuming 3 disks are moved:

Move disc 1 from peg 1 to peg 2

Move disc 1 from peg 2 to peg 3

Move disc 1 from peg 3 to peg 4

Move disc 2 from peg 1 to peg 2

Move disc 2 from peg 2 to peg 3

Move disc 1 from peg 4 to peg 3

Move disc 1 from peg 3 to peg 2

Move disc 2 from peg 3 to peg 4

Move disc 1 from peg 2 to peg 3

Move disc 1 from peg 3 to peg 4

Move disc 3 from peg 1 to peg 2

Move disc 3 from peg 2 to peg 3

Move disc 1 from peg 4 to peg 3

Move disc 1 from peg 3 to peg 2

Move disc 2 from peg 4 to peg 3

Move disc 1 from peg 2 to peg 3

Move disc 1 from peg 3 to peg 4

Move disc 2 from peg 3 to peg 2

Move disc 1 from peg 4 to peg 3

Move disc 1 from peg 3 to peg 2

Move disc 3 from peg 3 to peg 4

Move disc 3 from peg 4 to peg 5

Move disc 1 from peg 2 to peg 3

Move disc 1 from peg 3 to peg 4

Move disc 2 from peg 2 to peg 3

Move disc 1 from peg 4 to peg 3

Move disc 1 from peg 3 to peg 2

Move disc 2 from peg 3 to peg 4

Move disc 2 from peg 4 to peg 5

Move disc 1 from peg 2 to peg 3

Move disc 1 from peg 3 to peg 4

Move disc 1 from peg 4 to peg 5

Number of disks moved: 3

Number of moves made: 32

The language can either be C or C++

Thank you! I am struggling with this so much!