#include <algorithm>
#include <iostream>
#include <sstream>
#include <list>
#include <set>
using namespace std;
string str( unsigned n)
{
stringstream ss;
ss<< n;
return ss.str ( ) ;
}
class graph
{
public :
class node;
class edge
{
private :
string name;
node & src,& dst;
public :
edge( const string & name,node & src,node & dst) : name( name) ,src( src) ,dst( dst) { }
string Name( ) const { return name; }
node & Src( ) const { return src; }
node & Dst( ) const { return dst; }
friend class node;
friend class graph;
} ;
class node
{
public :
typedef list< edge* > :: iterator srciterator;
typedef list< edge* > :: iterator dstiterator;
private :
string name;
list< edge* > src,dst;
public :
srciterator srcbegin( ) { return src.begin ( ) ; }
srciterator srcend( ) { return src.end ( ) ; }
dstiterator dstbegin( ) { return dst.begin ( ) ; }
dstiterator dstend( ) { return dst.end ( ) ; }
unsigned srcid,dstid;
node( const string & name) : name( name) ,srcid( 0 ) ,dstid( 0 ) { }
string Name( ) const { return name; }
friend class graph;
} ;
typedef list< node> :: iterator nodeiterator;
typedef list< edge> :: iterator edgeiterator;
private :
list< node> nodes;
list< edge> edges;
graph( const graph & ) { } // not implemented
void operator= ( const graph & ) { } // not implemented
public :
graph( ) { }
nodeiterator nodebegin( ) { return nodes.begin ( ) ; }
nodeiterator nodeend( ) { return nodes.end ( ) ; }
edgeiterator edgebegin( ) { return edges.begin ( ) ; }
edgeiterator edgeend( ) { return edges.end ( ) ; }
node * find( const string & name)
{
for ( list< node> :: iterator i= nodes.begin ( ) ; i! = nodes.end ( ) ; ++ i) if ( i- > name== name) return & * i;
return 0 ;
}
node & make( const string & name)
{
node * tmp= find( name) ;
if ( ! tmp)
{
nodes.push_back ( node( name) ) ;
tmp= & nodes.back ( ) ;
}
return * tmp;
}
void connect( const string & what,node & src,node & dst)
{
edges.push_back ( edge( what,src,dst) ) ;
src.dst .push_back ( & edges.back ( ) ) ;
dst.src .push_back ( & edges.back ( ) ) ;
}
void connect( const string & what,const string & src,const string & dst)
{
connect( what,make( src) ,make( dst) ) ;
}
bool convertable( )
{
unsigned nr= 0 ;
for ( nodeiterator i= nodebegin( ) ; i! = nodeend( ) ; ++ i)
{
i- > dstid= 0 ;
i- > srcid= i- > src.size ( ) ? 0 : ++ nr;
}
for ( edgeiterator i= edgebegin( ) ; i! = edgeend( ) ; ++ i)
{
unsigned srcid= i- > src.dstid ,dstid= i- > dst.srcid ;
if ( srcid)
{
if ( dstid) return false ;
i- > dst.srcid = srcid;
}
else if ( dstid)
{
i- > src.dstid = dstid;
}
else
{
i- > src.dstid = i- > dst.srcid = ++ nr;
}
}
return true ;
}
bool orig( graph & g)
{
if ( convertable( ) )
{
for ( nodeiterator i= nodebegin( ) ; i! = nodeend( ) ; ++ i)
{
g.connect ( i- > name,str( i- > srcid) ,str( i- > dstid) ) ;
}
return true ;
}
return false ;
}
} ;
int main( )
{
graph g;
g.connect ( "1" ,"A" ,"B" ) ;
g.connect ( "2" ,"B" ,"C" ) ;
g.connect ( "3" ,"C" ,"E" ) ;
g.connect ( "4" ,"E" ,"F" ) ;
g.connect ( "5" ,"F" ,"B" ) ;
g.connect ( "6" ,"B" ,"D" ) ;
g.connect ( "7" ,"D" ,"F" ) ;
for ( graph:: nodeiterator i= g.nodebegin ( ) ; i! = g.nodeend ( ) ; ++ i)
{
for ( graph:: node :: dstiterator d= i- > dstbegin( ) ; d! = i- > dstend( ) ; ++ d)
{
cout << i- > Name( ) << " -> " << ( * d) - > Name( ) << " -> " << ( * d) - > Dst( ) .Name ( ) << endl;
}
}
cout << endl;
graph G;
g.orig ( G) ;
for ( graph:: nodeiterator i= G.nodebegin ( ) ; i! = G.nodeend ( ) ; ++ i)
{
for ( graph:: node :: dstiterator d= i- > dstbegin( ) ; d! = i- > dstend( ) ; ++ d)
{
cout << i- > Name( ) << " -> " << ( * d) - > Name( ) << " -> " << ( * d) - > Dst( ) .Name ( ) << endl;
}
}
return 0 ;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxzZXQ+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJpbmcgc3RyKHVuc2lnbmVkIG4pCiAgewogICBzdHJpbmdzdHJlYW0gc3M7CiAgIHNzPDxuOwogICByZXR1cm4gc3Muc3RyKCk7CiAgfQoKY2xhc3MgZ3JhcGgKICB7CiAgIHB1YmxpYzoKICAgY2xhc3Mgbm9kZTsKICAgY2xhc3MgZWRnZQogICAgIHsKICAgICAgcHJpdmF0ZToKICAgICAgc3RyaW5nIG5hbWU7CiAgICAgIG5vZGUgJnNyYywmZHN0OwogICAgICBwdWJsaWM6CiAgICAgIGVkZ2UoY29uc3Qgc3RyaW5nICZuYW1lLG5vZGUgJnNyYyxub2RlICZkc3QpOm5hbWUobmFtZSksc3JjKHNyYyksZHN0KGRzdCkge30KICAgICAgc3RyaW5nIE5hbWUoKWNvbnN0IHsgcmV0dXJuIG5hbWU7IH0KICAgICAgbm9kZSAmU3JjKCljb25zdCB7IHJldHVybiBzcmM7IH0KICAgICAgbm9kZSAmRHN0KCljb25zdCB7IHJldHVybiBkc3Q7IH0KICAgICAgZnJpZW5kIGNsYXNzIG5vZGU7CiAgICAgIGZyaWVuZCBjbGFzcyBncmFwaDsKICAgICB9OwogICBjbGFzcyBub2RlCiAgICAgewogICAgICBwdWJsaWM6CiAgICAgIHR5cGVkZWYgbGlzdDxlZGdlKj46Oml0ZXJhdG9yIHNyY2l0ZXJhdG9yOwogICAgICB0eXBlZGVmIGxpc3Q8ZWRnZSo+OjppdGVyYXRvciBkc3RpdGVyYXRvcjsKICAgICAgcHJpdmF0ZToKICAgICAgc3RyaW5nIG5hbWU7CiAgICAgIGxpc3Q8ZWRnZSo+IHNyYyxkc3Q7CiAgICAgIHB1YmxpYzoKICAgICAgc3JjaXRlcmF0b3Igc3JjYmVnaW4oKSB7IHJldHVybiBzcmMuYmVnaW4oKTsgfQogICAgICBzcmNpdGVyYXRvciBzcmNlbmQoKSB7IHJldHVybiBzcmMuZW5kKCk7IH0KICAgICAgZHN0aXRlcmF0b3IgZHN0YmVnaW4oKSB7IHJldHVybiBkc3QuYmVnaW4oKTsgfQogICAgICBkc3RpdGVyYXRvciBkc3RlbmQoKSB7IHJldHVybiBkc3QuZW5kKCk7IH0KICAgICAgdW5zaWduZWQgc3JjaWQsZHN0aWQ7CiAgICAgIG5vZGUoY29uc3Qgc3RyaW5nICZuYW1lKTpuYW1lKG5hbWUpLHNyY2lkKDApLGRzdGlkKDApIHt9CiAgICAgIHN0cmluZyBOYW1lKCljb25zdCB7IHJldHVybiBuYW1lOyB9CiAgICAgIGZyaWVuZCBjbGFzcyBncmFwaDsKICAgICB9OwogICB0eXBlZGVmIGxpc3Q8bm9kZT46Oml0ZXJhdG9yIG5vZGVpdGVyYXRvcjsKICAgdHlwZWRlZiBsaXN0PGVkZ2U+OjppdGVyYXRvciBlZGdlaXRlcmF0b3I7CiAgIHByaXZhdGU6CiAgIGxpc3Q8bm9kZT4gbm9kZXM7CiAgIGxpc3Q8ZWRnZT4gZWRnZXM7CiAgIGdyYXBoKGNvbnN0IGdyYXBoICYpIHt9IC8vIG5vdCBpbXBsZW1lbnRlZAogICB2b2lkIG9wZXJhdG9yPShjb25zdCBncmFwaCAmKSB7fSAvLyBub3QgaW1wbGVtZW50ZWQKICAgcHVibGljOgogICBncmFwaCgpIHt9ICAgCiAgIG5vZGVpdGVyYXRvciBub2RlYmVnaW4oKSB7IHJldHVybiBub2Rlcy5iZWdpbigpOyB9CiAgIG5vZGVpdGVyYXRvciBub2RlZW5kKCkgeyByZXR1cm4gbm9kZXMuZW5kKCk7IH0KICAgZWRnZWl0ZXJhdG9yIGVkZ2ViZWdpbigpIHsgcmV0dXJuIGVkZ2VzLmJlZ2luKCk7IH0KICAgZWRnZWl0ZXJhdG9yIGVkZ2VlbmQoKSB7IHJldHVybiBlZGdlcy5lbmQoKTsgfQogICBub2RlICpmaW5kKGNvbnN0IHN0cmluZyAmbmFtZSkKICAgICB7CiAgICAgIGZvcihsaXN0PG5vZGU+OjppdGVyYXRvciBpPW5vZGVzLmJlZ2luKCk7aSE9bm9kZXMuZW5kKCk7KytpKSBpZihpLT5uYW1lPT1uYW1lKSByZXR1cm4gJippOwogICAgICByZXR1cm4gMDsKICAgICB9CiAgIG5vZGUgJm1ha2UoY29uc3Qgc3RyaW5nICZuYW1lKQogICAgIHsKICAgICAgbm9kZSAqdG1wPWZpbmQobmFtZSk7CiAgICAgIGlmKCF0bXApCiAgICAgICAgewogICAgICAgICBub2Rlcy5wdXNoX2JhY2sobm9kZShuYW1lKSk7CiAgICAgICAgIHRtcD0mbm9kZXMuYmFjaygpOwogICAgICAgIH0KICAgICAgcmV0dXJuICp0bXA7CiAgICAgfQogICB2b2lkIGNvbm5lY3QoY29uc3Qgc3RyaW5nICZ3aGF0LG5vZGUgJnNyYyxub2RlICZkc3QpCiAgICAgewogICAgICBlZGdlcy5wdXNoX2JhY2soZWRnZSh3aGF0LHNyYyxkc3QpKTsKICAgICAgc3JjLmRzdC5wdXNoX2JhY2soJmVkZ2VzLmJhY2soKSk7CiAgICAgIGRzdC5zcmMucHVzaF9iYWNrKCZlZGdlcy5iYWNrKCkpOwogICAgIH0KICAgdm9pZCBjb25uZWN0KGNvbnN0IHN0cmluZyAmd2hhdCxjb25zdCBzdHJpbmcgJnNyYyxjb25zdCBzdHJpbmcgJmRzdCkKICAgICB7CiAgICAgIGNvbm5lY3Qod2hhdCxtYWtlKHNyYyksbWFrZShkc3QpKTsKICAgICB9CiAgIGJvb2wgY29udmVydGFibGUoKQogICAgIHsKCSAgdW5zaWduZWQgbnI9MDsKICAgICAgZm9yKG5vZGVpdGVyYXRvciBpPW5vZGViZWdpbigpO2khPW5vZGVlbmQoKTsrK2kpCgkgICAgewogICAgICAgICBpLT5kc3RpZD0wOwogICAgICAgICBpLT5zcmNpZD1pLT5zcmMuc2l6ZSgpPzA6KytucjsKCSAgICB9CiAgICAgIGZvcihlZGdlaXRlcmF0b3IgaT1lZGdlYmVnaW4oKTtpIT1lZGdlZW5kKCk7KytpKQogICAgICAgIHsKICAgICAgICAgdW5zaWduZWQgc3JjaWQ9aS0+c3JjLmRzdGlkLGRzdGlkPWktPmRzdC5zcmNpZDsKICAgICAgICAgaWYoc3JjaWQpCiAgICAgICAgICAgewogICAgICAgICAgICBpZihkc3RpZCkgcmV0dXJuIGZhbHNlOwogICAgICAgICAgICBpLT5kc3Quc3JjaWQ9c3JjaWQ7CiAgICAgICAgICAgfQogICAgICAgICBlbHNlIGlmKGRzdGlkKQogICAgICAgICAgIHsKICAgICAgICAgICAJaS0+c3JjLmRzdGlkPWRzdGlkOwogICAgICAgICAgIH0KICAgICAgICAgZWxzZQogICAgICAgICAgIHsKICAgICAgICAgICAJaS0+c3JjLmRzdGlkPWktPmRzdC5zcmNpZD0rK25yOwogICAgICAgICAgIH0KICAgICAgICB9CiAgICAgIHJldHVybiB0cnVlOwogICAgIH0KICAgYm9vbCBvcmlnKGdyYXBoICZnKQogICAgIHsKICAgICAgaWYoY29udmVydGFibGUoKSkKICAgICAgICB7CiAgICAgICAgIGZvcihub2RlaXRlcmF0b3IgaT1ub2RlYmVnaW4oKTtpIT1ub2RlZW5kKCk7KytpKQoJCSAgIHsKCQkgICAJZy5jb25uZWN0KGktPm5hbWUsc3RyKGktPnNyY2lkKSxzdHIoaS0+ZHN0aWQpKTsKCQkgICB9CgkJIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgcmV0dXJuIGZhbHNlOwogICAgIH0KICB9OwoKaW50IG1haW4oKSAKICB7CiAgIGdyYXBoIGc7CiAgIGcuY29ubmVjdCgiMSIsIkEiLCJCIik7CiAgIGcuY29ubmVjdCgiMiIsIkIiLCJDIik7CiAgIGcuY29ubmVjdCgiMyIsIkMiLCJFIik7CiAgIGcuY29ubmVjdCgiNCIsIkUiLCJGIik7CiAgIGcuY29ubmVjdCgiNSIsIkYiLCJCIik7CiAgIGcuY29ubmVjdCgiNiIsIkIiLCJEIik7CiAgIGcuY29ubmVjdCgiNyIsIkQiLCJGIik7CiAgIGZvcihncmFwaDo6bm9kZWl0ZXJhdG9yIGk9Zy5ub2RlYmVnaW4oKTtpIT1nLm5vZGVlbmQoKTsrK2kpCiAgICAgewogICAgICBmb3IoZ3JhcGg6Om5vZGU6OmRzdGl0ZXJhdG9yIGQ9aS0+ZHN0YmVnaW4oKTtkIT1pLT5kc3RlbmQoKTsrK2QpCiAgICAgICAgewogICAgICAgICBjb3V0PDxpLT5OYW1lKCk8PCIgLT4gIjw8KCpkKS0+TmFtZSgpPDwiIC0+ICI8PCgqZCktPkRzdCgpLk5hbWUoKTw8ZW5kbDsKICAgICAgICB9CiAgICAgfQogICBjb3V0PDxlbmRsOwogICBncmFwaCBHOwogICBnLm9yaWcoRyk7CiAgIGZvcihncmFwaDo6bm9kZWl0ZXJhdG9yIGk9Ry5ub2RlYmVnaW4oKTtpIT1HLm5vZGVlbmQoKTsrK2kpCiAgICAgewogICAgICBmb3IoZ3JhcGg6Om5vZGU6OmRzdGl0ZXJhdG9yIGQ9aS0+ZHN0YmVnaW4oKTtkIT1pLT5kc3RlbmQoKTsrK2QpCiAgICAgICAgewogICAgICAgICBjb3V0PDxpLT5OYW1lKCk8PCIgLT4gIjw8KCpkKS0+TmFtZSgpPDwiIC0+ICI8PCgqZCktPkRzdCgpLk5hbWUoKTw8ZW5kbDsKICAgICAgICB9CiAgICAgfQogICByZXR1cm4gMDsKICB9