Encontre a Transposta de um Grafo

Dado um grafo dirigido com v vértices e e arestas, você deve encontrar sua transposta.

A transposta de um grafo dirigido é um grafo obtido ao inverter a direção de todas as arestas do original. Em outras palavras, é um grafo em que todas as arestas dirigidas do grafo inicial são invertidas.

profound.academy-graph-transpose.drawio.png

A transposta de um grafo é útil para descobrir caminhos ou relacionamentos inversos no grafo. Veremos algumas aplicações mais adiante no curso.

Entrada

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

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

Saída

O programa deve exibir a lista de adjacência do grafo complementar. Cada linha deve começar com o id de um vértice seguido de dois pontos (:) e, em seguida, suas conexões. As conexões em cada linha devem ser separadas por um espaço. A ordem tanto dos vértices quanto das conexões pode ser arbitrária.

Exemplos

Entrada

Saída

4 4
1 2
1 4
2 4
3 4

1:
2: 1
3:
4: 1 2 3

Constraints

Time limit: 3.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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