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;
    }
}