#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector< int > g[ 10 ] ;
bool odw[ 10 ] ;
int wierzch,kraw;
void dfs( int x) {
cout << x<< " " ;
odw[ x] = true ;
for ( int i= 0 ; i< g[ x] .size ( ) ; i++ )
{
if ( ! odw[ g[ x] [ i] ] )
dfs( g[ x] [ i] ) ;
}
cout << "(" << x<< ") " ;
}
int main( )
{
cin >> wierzch>> kraw;
for ( int i= 1 ; i<= kraw; i++ )
{
int w1,w2;
cin >> w1>> w2;
g[ w1] .push_back ( w2) ;
g[ w2] .push_back ( w1) ;
}
for ( int i= 0 ; i< wierzch; i++ )
{
cout << i<< ": " ;
for ( int j= 0 ; j< g[ i] .size ( ) ; j++ )
{
cout << g[ i] [ j] << " " ;
}
cout << endl;
}
for ( int i= 0 ; i< wierzch; i++ )
{
if ( ! odw[ i] )
dfs( i) ;
}
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdmVjdG9yPGludD5nWzEwXTsKYm9vbCBvZHdbMTBdOwppbnQgd2llcnpjaCxrcmF3Owp2b2lkIGRmcyhpbnQgeCl7CiAgICBjb3V0PDx4PDwiICI7CiAgICBvZHdbeF09dHJ1ZTsKICAgIGZvcihpbnQgaT0wOyBpPGdbeF0uc2l6ZSgpOyBpKyspCiAgICB7CiAgICAgICAgaWYoIW9kd1tnW3hdW2ldXSkKICAgICAgICAgICAgZGZzKGdbeF1baV0pOwogICAgfQogICAgY291dDw8IigiPDx4PDwiKSAiOwp9CmludCBtYWluKCkKewogICAgY2luPj53aWVyemNoPj5rcmF3OwogICAgZm9yKGludCBpPTE7IGk8PWtyYXc7IGkrKykKICAgIHsKICAgICAgICBpbnQgdzEsdzI7CiAgICAgICAgY2luPj53MT4+dzI7CiAgICAgICAgZ1t3MV0ucHVzaF9iYWNrKHcyKTsKICAgICAgICBnW3cyXS5wdXNoX2JhY2sodzEpOwogICAgfQogICAgZm9yKGludCBpPTA7IGk8d2llcnpjaDsgaSsrKQogICAgewogICAgICAgIGNvdXQ8PGk8PCI6ICI7CiAgICAgICAgZm9yKGludCBqPTA7IGo8Z1tpXS5zaXplKCk7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQ8PGdbaV1bal08PCIgIjsKICAgICAgICB9CiAgICAgICAgY291dDw8ZW5kbDsKICAgIH0KICAgIGZvcihpbnQgaT0wOyBpPHdpZXJ6Y2g7IGkrKykKICAgIHsKICAgICAgICBpZighb2R3W2ldKQogICAgICAgICAgICBkZnMoaSk7CiAgICB9CiAKICByZXR1cm4gMDsKfQo=