Colorazione dei grafi

Vi viene fornito un grafo con v vertici e e archi, insieme a c colori disponibili. Il vostro compito consiste nel verificare se sia possibile colorare il grafo utilizzando i c colori dati in modo tale che nessun vertice adiacente abbia lo stesso colore.

Input

La prima riga contiene tre interi v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) e c (1 ≤ c ≤ 10), che rappresentano rispettivamente il numero di vertici, il numero di archi e il numero di colori disponibili.

Le successive e righe descrivono gli archi del grafo. Ogni riga contiene due interi a e b (1 ≤ a, b ≤ n, a ≠ b) che indicano un arco tra i vertici a e b.

Output

Stampate YES se è possibile colorare il grafo con i c colori senza che esistano vertici adiacenti che abbiano lo stesso colore. In caso contrario, stampate NO.

Esempi