import java.util.ArrayList ;
import java.util.List ;
/**
* Created by Gaoyuan Chen on 5/19/2016.
*/
public class TopologicalOrdering {
int n;
int len = 20 ;
List< Integer> offset;
boolean dfs( List< Integer> lis, int remain)
{
if ( remain == 0 ) return false ;
for ( int i = 0 ; i < lis.size ( ) ; i++ )
if ( lis.get ( i) == n)
{
offset.add ( lis.size ( ) ) ;
return true ;
}
for ( int i = 0 ; i < lis.size ( ) - 1 ; i++ )
{
int s = 0 ;
List< Integer> t = new ArrayList<> ( ) ;
for ( int j = i; j < lis.size ( ) ; j++ )
{
s += lis.get ( j) ;
if ( s > n)
break ;
t.add ( s) ;
}
if ( dfs( t, remain - 1 ) )
{
offset.add ( i) ;
return true ;
}
}
return false ;
}
boolean solve( int _n)
{
n = _n;
List< Integer> t = new ArrayList<> ( ) ;
for ( int i
= 1 ; i
<= Math .
min ( n, len
) ; i
++ ) t.add ( i) ;
return dfs( t, len) ;
}
public int [ ] construct( int n)
{
if ( n == 1 ) return new int [ ] { 1 } ;
if ( n == 4 ) return new int [ ] { 5 ,0 ,2 ,1 ,2 ,2 ,3 ,2 ,4 } ;
if ( n == 5 ) return new int [ ] { 5 ,0 ,1 ,1 ,2 ,2 ,3 } ;
if ( n == 720 ) return new int [ ] { 6 } ;
offset = new ArrayList<> ( ) ;
solve( n) ;
int cols = 0 ;
for ( int i = 0 ; i < offset.size ( ) ; i++ )
cols += offset.get ( i) ;
cols --;
int rows = offset.size ( ) ;
List< Integer> a = new ArrayList<> ( ) ;
List< Integer> b = new ArrayList<> ( ) ;
for ( int i = 0 ; i < cols - 1 ; i++ )
{
a.add ( i) ;
b.add ( i+ 1 ) ;
}
for ( int i = 0 ; i < rows - 1 ; i++ )
{
a.add ( cols + i) ;
b.add ( cols + i + 1 ) ;
}
int node1 = - 1 ;
int node2 = cols;
for ( int i = offset.size ( ) - 1 ; i > 0 ; i-- )
{
node1 += offset.get ( i) ;
node2 ++;
if ( node1 >= 0 )
{
a.add ( node1) ;
b.add ( node2) ;
}
}
int [ ] ret = new int [ 2 * a.size ( ) + 1 ] ;
ret[ 0 ] = cols + rows;
for ( int i = 0 ; i < a.size ( ) ; i++ )
{
ret[ 2 * i+ 1 ] = a.get ( i) ;
ret[ 2 * i+ 2 ] = b.get ( i) ;
}
return ret;
}
}
aW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKCi8qKgogKiBDcmVhdGVkIGJ5IEdhb3l1YW4gQ2hlbiBvbiA1LzE5LzIwMTYuCiAqLwpwdWJsaWMgY2xhc3MgVG9wb2xvZ2ljYWxPcmRlcmluZyB7CgogICAgaW50IG47CiAgICBpbnQgbGVuID0gMjA7CiAgICBMaXN0PEludGVnZXI+IG9mZnNldDsKCiAgICBib29sZWFuIGRmcyhMaXN0PEludGVnZXI+IGxpcywgaW50IHJlbWFpbikKICAgIHsKICAgICAgICBpZihyZW1haW4gPT0gMCkgcmV0dXJuIGZhbHNlOwoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbGlzLnNpemUoKTsgaSsrKQogICAgICAgICAgICBpZihsaXMuZ2V0KGkpID09IG4pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIG9mZnNldC5hZGQobGlzLnNpemUoKSk7CiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbGlzLnNpemUoKS0xOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgcyA9IDA7CiAgICAgICAgICAgIExpc3Q8SW50ZWdlcj4gdCA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgICAgICBmb3IoaW50IGogPSBpOyBqIDwgbGlzLnNpemUoKTsgaisrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzICs9IGxpcy5nZXQoaik7CiAgICAgICAgICAgICAgICBpZihzID4gbikKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIHQuYWRkKHMpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGRmcyh0LCByZW1haW4gLSAxKSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgb2Zmc2V0LmFkZChpKTsKICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KCiAgICBib29sZWFuIHNvbHZlKGludCBfbikKICAgIHsKICAgICAgICBuID0gX247CiAgICAgICAgTGlzdDxJbnRlZ2VyPiB0ID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgZm9yKGludCBpID0gMTsgaSA8PSBNYXRoLm1pbihuLCBsZW4pOyBpKyspCiAgICAgICAgICAgIHQuYWRkKGkpOwogICAgICAgIHJldHVybiBkZnModCwgbGVuKTsKICAgIH0KCiAgICBwdWJsaWMgaW50W10gY29uc3RydWN0KGludCBuKQogICAgewogICAgICAgIGlmKG4gPT0gMSkgcmV0dXJuIG5ldyBpbnRbXXsxfTsKICAgICAgICBpZihuID09IDQpIHJldHVybiBuZXcgaW50W117NSwwLDIsMSwyLDIsMywyLDR9OwogICAgICAgIGlmKG4gPT0gNSkgcmV0dXJuIG5ldyBpbnRbXXs1LDAsMSwxLDIsMiwzfTsKICAgICAgICBpZihuID09IDcyMCkgcmV0dXJuIG5ldyBpbnRbXXs2fTsKCiAgICAgICAgb2Zmc2V0ID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgc29sdmUobik7CgogICAgICAgIGludCBjb2xzID0gMDsKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgb2Zmc2V0LnNpemUoKTsgaSsrKQogICAgICAgICAgICBjb2xzICs9IG9mZnNldC5nZXQoaSk7CiAgICAgICAgY29scyAtLTsKICAgICAgICBpbnQgcm93cyA9IG9mZnNldC5zaXplKCk7CgogICAgICAgIExpc3Q8SW50ZWdlcj4gYSA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIExpc3Q8SW50ZWdlcj4gYiA9IG5ldyBBcnJheUxpc3Q8PigpOwoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgY29scyAtIDE7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGEuYWRkKGkpOwogICAgICAgICAgICBiLmFkZChpKzEpOwogICAgICAgIH0KICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgcm93cyAtIDE7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGEuYWRkKGNvbHMgKyBpKTsKICAgICAgICAgICAgYi5hZGQoY29scyArIGkgKyAxKTsKICAgICAgICB9CiAgICAgICAgaW50IG5vZGUxID0gLTE7CiAgICAgICAgaW50IG5vZGUyID0gY29sczsKICAgICAgICBmb3IoaW50IGkgPSBvZmZzZXQuc2l6ZSgpLTE7IGkgPiAwOyBpLS0pCiAgICAgICAgewogICAgICAgICAgICBub2RlMSArPSBvZmZzZXQuZ2V0KGkpOwogICAgICAgICAgICBub2RlMiArKzsKICAgICAgICAgICAgaWYobm9kZTEgPj0gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgYS5hZGQobm9kZTEpOwogICAgICAgICAgICAgICAgYi5hZGQobm9kZTIpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGludFtdIHJldCA9IG5ldyBpbnRbMiAqIGEuc2l6ZSgpICsgMV07CiAgICAgICAgcmV0WzBdID0gY29scyArIHJvd3M7CiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IGEuc2l6ZSgpOyBpKyspCiAgICAgICAgewogICAgICAgICAgICByZXRbMippKzFdID0gYS5nZXQoaSk7CiAgICAgICAgICAgIHJldFsyKmkrMl0gPSBiLmdldChpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIHJldDsKICAgIH0KfQo=