import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.text.SimpleDateFormat;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Date;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Preprocessor {

    private final static boolean TIMESTAMP = true;
    private final static boolean SANITYCHECK = false;

    public static void main(String[] args) throws FileNotFoundException, IOException {
        int n = Integer.parseInt(args[0]); // number of channels
        Scanner sc = new Scanner(System.in); // read from standard input
        Hint hint = new Hint(n,sc);
        Set<SortingNetwork> R = new LinkedHashSet<SortingNetwork>(1);
        R.add(new SortingNetwork(n,0));
        while (!R.isEmpty()) {
            Set<SortingNetwork> N = generate(n,R,hint);
            System.err.println("N = "+N.size());
            R = prune(N,hint);
            System.err.println("R = "+R.size());
        }
        sc.close();
        System.err.println("SUCCESS");
    }

    private static Set<SortingNetwork> generate(int n, Set<SortingNetwork> R, Hint hint) {
        Set<SortingNetwork> N = new LinkedHashSet<SortingNetwork>(R.size()*n*(n-1)/2);
        System.err.println("Extending by one comparator");
        for (SortingNetwork S : R)
            for (int i = 1; i < n; i++) // extend with all possible comparators
                for (int j = 0; j < i; j++)
                    N.add(S.extend(j,i));
        System.err.println("Keeping only admissible networks");
        timeStamp();
        SortingNetwork subsumed = hint.getInadmissable(R);
        while (subsumed != null) {
            N.remove(subsumed);
            subsumed = hint.getInadmissable(R);
        }
        return N;
    }

    private static Set<SortingNetwork> prune(Set<SortingNetwork> N, Hint hint) throws FileNotFoundException, IOException {
        Map<SortingNetwork,SortingNetwork> R = new LinkedHashMap<SortingNetwork,SortingNetwork>(N.size());
        for (SortingNetwork S : N)
            R.put(S,S);
        Set<SortingNetwork> keys = R.keySet();
        if (keys.isEmpty())
            return keys;
        System.err.println("Marking subsumed networks");
        timeStamp();
        SortingNetwork subsumed = hint.getPruned(keys);
        while (subsumed != null) {
            R.get(subsumed).subsumedBy = R.get(hint.subsuming); 
            R.get(subsumed).subsumingPermutation = hint.permutation;
            subsumed = hint.getPruned(keys);
        }
        int n = N.iterator().next().numChannels;
        int k = N.iterator().next().numComparators;
        System.err.println("Extracting top level subsumptions");
        timeStamp();
        Writer log = new BufferedWriter(new FileWriter(new File("oracle_"+n+"_"+k)));
        for (SortingNetwork S : keys) {
            if (S.subsumedBy == null)
                continue;
            SortingNetwork T = S;
            int[] permutation = new int[n];
            for (int i = 0; i < n; i++) {
                permutation[i] = i;
            }
            int[] result = new int[n];
            while (T.subsumedBy != null) {
                for (int i = 0; i < permutation.length; i++)
                    result[i] = permutation[T.subsumingPermutation[i]];
                int[] tmp = result;
                result = permutation;
                permutation = tmp;
                T = T.subsumedBy;
            }
            if (SANITYCHECK && !S.isSubsumed(T.permute(permutation))) {
                System.out.println("FAILED - contraction unsuccesful");
                System.exit(-1);
            }
            S.write(log);
            log.write('\n');
            T.write(log);
            log.write('\n');
            for (int i = 0; i < permutation.length; i++) {
                log.write(Integer.toString(permutation[i]));
                log.write(' ');
            }
            log.write('\n');
        }
        log.close();
        System.err.println("Pruning marked networks");
        timeStamp();
        for (Iterator<SortingNetwork> i = keys.iterator(); i.hasNext();) {
            SortingNetwork S = i.next();
            if (S.subsumedBy != null)
                i.remove();
        }
        return keys;
    }

    private static void timeStamp() {
        if (!TIMESTAMP)
            return;
        Date date = new Date();
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd h:mm:ss a");
        String formattedDate = sdf.format(date);
        System.err.println(formattedDate);
    }

    private static class Hint {
        int n;
        Iterator<String> hints;
        String line;
        SortingNetwork subsumed, subsuming;
        int[] permutation;
        private Hint(int n, Iterator<String> hints) {
            this.n = n;
            this.hints = hints;
        }
        SortingNetwork getInadmissable(Set<SortingNetwork> keys) {
            SortingNetwork res = null;
            if (subsumed == null) {
                next(keys);
            }
            if (subsumed != null && subsumed.numComparators > subsuming.numComparators) {
                if (SANITYCHECK && !keys.contains(subsuming)) { // fail if subsuming network does not occur in set
                    System.out.println("FAILED - subsuming network not generated: "+line);
                    System.exit(-1);
                }
                res = subsumed;
                subsumed = null;
            }
            return res;
        }
        SortingNetwork getPruned(Set<SortingNetwork> keys) {
            SortingNetwork res = null;
            if (subsumed == null) {
                next(keys);
            }
            if (subsumed != null && subsumed.numComparators == subsuming.numComparators) {
                if (SANITYCHECK && !keys.contains(subsuming)) { // fail if subsuming network does not occur in set
                    System.err.println("FAILED - subsuming network not generated: "+line);
                    System.exit(-1);
                }
                res = subsumed;
                subsumed = null;
            }
            return res;
        }
        void next(Set<SortingNetwork> keys) {
            if (hints.hasNext()) {
                line = hints.next();
                String[] xyp = line.substring(8,line.length()-3).split("\\],\\[");
                subsumed = SortingNetwork.parse(n,xyp[0]);
                subsuming = SortingNetwork.parse(n,xyp[1]);
                permutation = parsePermutation(xyp[2]);
                if (SANITYCHECK && !subsumed.isSubsumed(subsuming.permute(permutation))) { // fail if network is not subsumed
                    System.err.println("FAILED - error in subsumption: "+line);
                    System.exit(-1);
                }
            }
        }
    }

    private static int[] parsePermutation(String string) {
        String[] parts = string.split(",");
        int[] a = new int[parts.length];
        for (int i = 0; i < a.length; i++)
            a[i] = Integer.parseInt(parts[i]);
        return a;
    }

    private static class SortingNetwork {

        private int[][] comps; // list of pairs of channel ids
        private int numChannels, numComparators;
        private SortingNetwork subsumedBy = null;
        private int[] subsumingPermutation = null;

        public SortingNetwork(int numChannels, int numComparators) {
            this.numChannels = numChannels;
            this.numComparators = numComparators;
            this.comps = new int[numComparators][2];
        }

        public void write(Writer log) throws IOException {
            for (int k = 0; k < this.numComparators; k++) {
                log.write(Integer.toString(this.comps[k][0]));
                log.write(' ');
                log.write(Integer.toString(this.comps[k][1]));
                log.write(' ');
            }
        }

	private static SortingNetwork parse(int numChannels, String compList) {
            String[] comps = compList.substring(1).split(",c");
            int numComparators = comps.length;
            SortingNetwork sn = new SortingNetwork(numChannels, numComparators);
            for (int k = 0; k < numComparators; k++) {
                String comp = comps[k];
                String[] tb = comp.substring(1,comp.length()-1).split(",");
                sn.comps[k][0] = Integer.parseInt(tb[0]);
                sn.comps[k][1] = Integer.parseInt(tb[1]);
            }
            return sn;
        }

        public int hashCode() {
            int code = 0;
            for (int k = 0; k < this.numComparators; k++) {
                code = 101*code + this.comps[k][0] + 11 * this.comps[k][1];
            }
            return code;
        }

        public boolean equals(Object o) {
            if (o == null || !(o instanceof SortingNetwork)) return false;
            SortingNetwork other = (SortingNetwork)o;
            if (this.numChannels != other.numChannels || this.numComparators != other.numComparators) return false;
            for (int k = 0; k < this.numComparators; k++)
                if (this.comps[k][0] != other.comps[k][0] || this.comps[k][1] != other.comps[k][1]) return false;
            return true;
        }

        private int[] run() {
            int input = 1 << this.numChannels; // 2^n inputs
            int[] outputs = new int[input];
            while (input > 0) {
                input--;
                outputs[runInput(input)] = 1;
            }
            return outputs;
        }

        private int runInput(int input) {
            for (int k = 0; k < this.numComparators; k++) {
                int i = this.comps[k][0];
                int j = this.comps[k][1];
                if (((input >> i) & 1) > ((input >> j) & 1)) // if x_i > x_j then swap
                    input += (1 << j) - (1 << i);
            }
            return input;
        }

        private boolean isSubsumed(SortingNetwork that) {
            int[] thisOut = this.run();
            int[] thatOut = that.run();
            for (int i = 0; i < thisOut.length; i++)
                if (thisOut[i] < thatOut[i])
                    return false;
            return true;
        }
        
        private SortingNetwork permute(int[] permutation) {
            SortingNetwork per = new SortingNetwork(this.numChannels,this.numComparators);
            for (int k = 0; k < this.numComparators; k++) {
                per.comps[k][0] = permutation[this.comps[k][0]];
                per.comps[k][1] = permutation[this.comps[k][1]];
            }
            return per;
        }

        public SortingNetwork extend(int i, int j) {
            SortingNetwork ext = new SortingNetwork(this.numChannels,this.numComparators+1);
            for (int k = 0; k < this.numComparators; k++)
                ext.comps[k] = this.comps[k];
            ext.comps[this.numComparators][0] = i;
            ext.comps[this.numComparators][1] = j;
            return ext;
        }
    }

}