Trova la Trasposta di un Grafo

Dato un grafo orientato con v vertici e e archi, ti viene richiesto di trovarne la trasposta.

La trasposta di un grafo orientato è un grafo ottenuto invertendo la direzione di tutti i suoi archi. In altre parole, è un grafo in cui tutti gli archi orientati del grafo originale vengono invertiti.

La trasposta di un grafo è utile per trovare percorsi inversi o relazioni inverse nel grafo. Vedremo alcune applicazioni più avanti nel corso.

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), il che significa che il vertice v1 è collegato al vertice v2.

Output

Il programma deve stampare la lista di adiacenza del grafo complementare. Ogni riga dovrebbe iniziare con l’id di un vertice, seguito da un punto e virgola (:) e poi le sue connessioni. Le connessioni in ciascuna riga vanno separate da uno spazio. L’ordine sia dei vertici sia delle connessioni può essere arbitrario.

Esempi