Cycle Detection of Exact Length in an Undirected Graph

You are given an undirected graph with \(n\) vertices and \(m\) edges, and an integer \(k\). Your task is to determine whether there exists a simple cycle of exactly length \(k\) in the graph.

A cycle is defined as a sequence of distinct vertices \(v_1, v_2, \dots, v_k\) such that for every \(1 \le i < k\) there is an edge between \(v_i\) and \(v_{i+1}\), and there is also an edge connecting \(v_k\) back to \(v_1\). The cycle must contain exactly \(k\) vertices.

If such a cycle exists, print YES; otherwise, print NO.

inputFormat

The first line contains three space-separated integers \(n\), \(m\), and \(k\) \( (1 \le n, m, k \le 10^? )\) representing the number of vertices, the number of edges, and the required cycle length respectively.

The following \(m\) lines each contain two space-separated integers \(u\) and \(v\) \( (1 \le u, v \le n)\) representing an undirected edge between vertices \(u\) and \(v\).

outputFormat

Print a single line containing YES if there exists a simple cycle of exactly length \(k\) in the graph, and NO otherwise.

5 7 4
1 2
2 3
3 4
4 5
5 1
2 4
1 3

YES