Hamiltonian Cycle in a Cave System

You are given a cave system with (N) caves and (M) bidirectional tunnels. Each tunnel connects two different caves. Your task is to determine whether there exists a Hamiltonian cycle that starts and ends at a specified cave (S) and visits every other cave exactly once. In other words, you need to check if there exists a path (v_1, v_2, \dots, v_N, v_1) (with (v_1 = S)) such that for each consecutive pair ((v_i, v_{i+1})) (including the pair ((v_N, v_1))), there is a direct tunnel between the caves. This is a classic NP-complete problem, but you may assume that the input size is small enough to allow solutions using exhaustive search or backtracking.

inputFormat

The input is read from standard input (stdin) and consists of a single line of space-separated integers. The first two integers are (N) (the number of caves) and (M) (the number of tunnels). This is followed by (2M) integers, each pair representing a bidirectional tunnel between two caves. The final integer is (S), the starting cave.

For example, the input:

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

represents a cave system of 4 caves with 5 tunnels (between caves 1-2, 2-3, 3-4, 4-1, and 1-3) and a starting cave 1.

outputFormat

Output a single line to standard output (stdout) containing either the string (YES) if a Hamiltonian cycle starting from cave (S) exists, or (NO) if it does not.## sample

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

YES