Verificare se il Grafo è Bipartito

Un grafo si definisce bipartito quando è possibile colorarlo con due colori in modo che nessun paio di vertici adiacenti condivida lo stesso colore.

Stabilire se un grafo è bipartito può aiutare a identificare strutture e proprietà particolari, consentendo di risolvere in modo efficiente problemi in ambiti come la pianificazione, l’allocazione delle risorse e la risoluzione di conflitti. Inoltre, i grafi bipartiti permettono di sfruttare algoritmi più semplici e ottimizzazioni in attività come il matching massimo (maximum matching) e la colorazione dei grafi (graph coloring).

Vi viene fornito un grafo non orientato con v vertici e e spigoli. È richiesto di verificare se il grafo è bipartito oppure no.

Input

La prima riga dell’input contiene due interi v (1 ≤ v ≤ 100 000) ed e (1 ≤ e ≤ 100 000).

Le successive e righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v). Ciò significa che il vertice v1 è connesso al vertice v2 e viceversa.

Output

Il programma deve stampare Yes se il grafo in questione è bipartito, altrimenti deve stampare No.

Esempi