Detecting an Odd Length Cycle

Given an undirected graph as an adjacency list, return whether the graph has an odd length cycle.

Constraints

• n, m ≤ 250 where n and m are the number of rows and columns in graph

https://binarysearch.com/problems/Detecting-an-Odd-Length-Cycle

Examples

Example 1

Input

• graph =

[[1],
 [0]]

Output

• answer = False

Explanation

There is an even length cycle, not odd.

Example 2

Input

• graph =

[[list([1, 2, 3]),list([0, 2]),list([0, 1, 3]),list([0, 2])]]

Output

• answer = True

Explanation

One odd length cycle would be 0 -> 2 -> 1 -> 0

Solution