Algorithmen und Datenstrukturen

Überprüfen, ob ein Graph ausgeglichen (balanced) ist

Ein gerichteter Graph ist ausgeglichen (balanced), wenn für alle Knoten die Anzahl der eingehenden Kanten mit der Anzahl der ausgehenden Kanten übereinstimmt. Gegeben ist ein Graph mit v Knoten und e Kanten; Ihre Aufgabe ist es, zu überprüfen, ob er ausgeglichen ist.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).
In den darauffolgenden e Zeilen stehen Zahlenpaare v1, v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.

Ausgabe

Das Programm soll Yes ausgeben, wenn der Graph ausgeglichen ist, andernfalls No.

Beispiele

Eingabe
Ausgabe
3 2 1 2 2 3
No
3 3 1 2 2 3 3 1
Yes

Erläuterung

Beispiel 1: Knoten 1 hat keine eingehenden Kanten, besitzt aber eine ausgehende Kante ⇒ Der Graph ist nicht ausgeglichen.
Beispiel 1: Knoten 1 hat keine eingehenden Kanten, besitzt aber eine ausgehende Kante ⇒ Der Graph ist nicht ausgeglichen.
Beispiel 2: Alle Knoten haben je eine eingehende und eine ausgehende Kante ⇒ Der Graph ist ausgeglichen.
Beispiel 2: Alle Knoten haben je eine eingehende und eine ausgehende Kante ⇒ Der Graph ist ausgeglichen.
 

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