Algoritmos e Estruturas de Dados

Verificar se um Grafo é Equilibrado

Um grafo dirigido é considerado equilibrado se todos os vértices tiverem o mesmo número de arestas de entrada e de saída. Dado um grafo com v vértices e e arestas, a tarefa é determinar se ele é equilibrado.

Entrada

A primeira linha da entrada contém dois inteiros v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).

As seguintes e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.

Saída

O programa deve imprimir Yes se o grafo for equilibrado e No caso contrário.

Exemplos

Entrada

Saída

3 2
1 2
2 3

No

3 3
1 2
2 3
3 1

Yes

Explicação

profound.academy-graphs-2.drawio.png
Exemplo 1: O vértice 1 não tem arestas de entrada, mas tem 1 aresta de saída ⇒ o grafo não está equilibrado.
profound.academy-graphs-2.drawio (1).png
Exemplo 2: Todos os vértices têm 1 aresta de entrada e 1 aresta de saída ⇒ o grafo está equilibrado.

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