Hamiltonian Path with Color Constraints

Given an undirected graph with n vertices and m edges, each vertex is painted with one of k colors. Your task is to determine whether there exists a Hamiltonian path (a path containing each vertex exactly once) such that no two consecutive vertices share the same color. Formally, let V = {1, 2, (\ldots), n} be the set of vertices and let each vertex (i) have a color (c_i). A path (v_1, v_2, \ldots, v_n) is valid if for every adjacent pair (v_i, v_{i+1}), there is an edge between them and (c_{v_i} \neq c_{v_{i+1}}).

You are to output "YES" if such a path exists, or "NO" otherwise.

inputFormat

Input is read from stdin. The first line contains three integers (n), (m), and (k) separated by spaces, where (n) is the number of vertices, (m) is the number of edges, and (k) is the number of distinct colors. The second line contains (n) integers representing the color of each vertex (the (i)-th integer corresponds to the color of vertex (i)). The following (m) lines each contain two integers (u) and (v) indicating there is an undirected edge between vertices (u) and (v).

outputFormat

Output a single line to stdout containing either "YES" if a Hamiltonian path meeting the color constraints exists; otherwise, output "NO".## sample

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

YES