K-Edge Cycle Detection

You are given an undirected graph with n vertices and m edges. Your task is to determine whether there exists a simple cycle that uses exactly K distinct edges and returns to the starting vertex.

A simple cycle is defined as a cycle in which each edge is used at most once. In other words, if the cycle is represented as a sequence of vertices v₀, v₁, ..., v_K with v₀ = v_K, then each edge \( (v_i, v_{i+1}) \) (with \(0 \le i < K\)) must be distinct.

Your solution should read the input from stdin and write the result to stdout. If such a cycle exists, output YES; otherwise, output NO.

Note: A cycle with exactly K edges satisfies \( |E(C)| = K \).

inputFormat

The input is given from stdin and follows this format:

n m
u1 v1
u2 v2
...
um vm
K

Here, the first line contains two integers n (the number of vertices) and m (the number of edges). Each of the next m lines contains two integers u and v representing an undirected edge connecting vertices u and v. The last line contains an integer K, representing the required number of edges in the cycle.

outputFormat

Output a single line to stdout with either YES or NO. Output YES if there exists a simple cycle consisting of exactly K distinct edges, and NO otherwise.

5 6
1 2
1 3
2 3
3 4
4 5
5 1
5

YES