You are given an undirected graph G $=($V$,$ E$),$ where V is the set of vertices and E is

the set of edges. Your task is to count the total number of simple cycles of length n in the graph.

A simple cycle of length n is defined as a cycle that contains exactly n vertices and n edges. Each

cycle should only be counted once, regardless of its starting vertex or direction.

Input: an undirected graph G $=($V$,$ E$),$ represented as an adjacency list; an integer n$,$ which

represents the desired length of the cycle.

CMPSC $465,$ Fall $2024,$ HW $41$

Output: return the total number of simple cycles of length n in graph G$.$

Design an algorithm for above problem and analyze its time complexity. $($Hints: consider a DFS$-$

based algorithm; ensure that each cycle is counted only once, despite the undirected nature of the

graph; optimize the DFS to avoid redundant searches and prune unnecessary paths that do not

lead to valid cycles.