import java.io.FileNotFoundException;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Verifier2 {

    public static void main(String[] args) throws FileNotFoundException {
        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.out.println("N = "+N.size());
            R = prune(N,hint);
            System.out.println("R = "+R.size());
        }
        sc.close();
        System.out.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.out.println("Extending by one comparator");
        for (SortingNetwork S : R)
            for (int i = 0; i < n; i++) // extend with all possible comparators
                for (int j = i+1; j < n; j++)
                    N.add(S.extend(i,j));
        System.out.println("Keeping only admissible networks");
        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) {
        Map<SortingNetwork,SortingNetwork> R = new LinkedHashMap<SortingNetwork,SortingNetwork>(N.size());
        for (SortingNetwork S : N)
            R.put(S,S);
        Set<SortingNetwork> keys = R.keySet();
        System.out.println("Marking subsumed networks");
        SortingNetwork subsumed = hint.getPruned(keys);
        while (subsumed != null) {
            R.get(subsumed).subsumedBy = R.get(hint.subsuming); 
            subsumed = hint.getPruned(keys);
        }
        System.out.println("Checking for cyclic reasoning");
        for (SortingNetwork S : R.keySet()) {
            while (S != null) {
                S = S.subsumedBy;
            }
        }
        System.out.println("Pruning marked networks");
        for (Iterator<SortingNetwork> i = R.keySet().iterator(); i.hasNext();) {
            SortingNetwork S = i.next();
            if (S.subsumedBy != null)
                i.remove();
        }
        return R.keySet();
    }
    
    private static class Hint {
        int n;
        Iterator<String> hints;
        String line;
        SortingNetwork subsumed, subsuming;
        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 (!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 (!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;
        }
        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]);
                SortingNetwork subsumingPermuted = subsuming.permute(parsePermutation(xyp[2]));
                if (!subsumed.isSubsumed(subsumingPermuted)) { // fail if network is not subsumed
                    System.out.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;

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

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

}