Algoritmi e Strutture Dati

Verificare se un grafo è uno Star Graph

Dato un grafo non orientato con v vertici e e spigoli, devi stabilire se si tratta di uno star graph. Uno star graph è un grafo che presenta un vertice centrale connesso a tutti gli altri vertici, mentre tutti gli altri vertici sono collegati esclusivamente al vertice centrale e non tra di loro.

profound.academy-graphs-star-graph.drawio.png

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), che indicano che il vertice v1 è connesso al vertice v2 e viceversa.

Output

Il programma deve stampare Yes se il grafo è uno star graph, altrimenti deve stampare No.

Esempi

Input

Output

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

Yes

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

No

1 0

Yes

2 1
1 2

Yes

2 0

No

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue