НКА -> ДКА

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    static int A;
    static Set<String> S;
    static Set<String> F;
    static Map<Pair<String , String> , Set<String>> f;

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc = new Scanner(System.in);
        S = new HashSet();
        F = new HashSet();
        f = new HashMap();
        A = sc.nextInt();
        int s = sc.nextInt();
        ArrayList<String> tmp = new ArrayList();
        for(Integer i = 0 ; i < s ; ++i){
            S.add(i.toString());
            tmp.add(i.toString());
        }
        Integer t_ = sc.nextInt();
        --t_;
        String s0 = ""; s0 += t_;
        int sz_f = sc.nextInt();
        for(int i = 0 ; i < sz_f ; ++i){
            Integer t = sc.nextInt();
            --t;
            F.add(t.toString());
        }
        while(sc.hasNext()){
            Integer u = sc.nextInt();
            String ch = sc.next();
            Integer v = sc.nextInt();
            --u;
            --v;
            if(!f.containsKey(new Pair(u.toString() , ch))){
                f.put(new Pair(u.toString() , ch) , new HashSet<String>());
            }
            f.get(new Pair(u.toString() , ch)).add(v.toString());
        }

        Set<String> new_S = new HashSet();
        Set<String> new_F = new HashSet();

        for(int mask = 1 ; mask < Math.pow(2 , s) ; ++mask){
            String cur = "";
            boolean ck = false;
            for(int j = 0 ; j < s ; ++j){
                if(((mask >> j) & 1) != 0){
                    if(cur.length() > 0){
                        cur += ',';
                    }
                    cur += tmp.get(j);
                    if(F.contains(tmp.get(j))){
                        ck = true;
                    }
                }
            }
            new_S.add(cur);
            if(ck){
                new_F.add(cur);
            }
        }
        String new_s0 = s0;
        Map<Pair<String , String> , String> new_f = new HashMap();
        for(String st : new_S){
            String[] states = st.split(",");
            for(char c = 'a' ; c < 'a' + A ; ++c){
                String temp = ""; temp += c;
                String to = "";
                Map<String , Boolean> used = new HashMap();
                for(int i = 0 ; i < states.length ; ++i){
                    if(!f.containsKey(new Pair<String , String>(states[i] , temp))){
                        continue;
                    }
                    Set<String> vs = f.get(new Pair<String , String>(states[i] , temp));
                    for(String v : vs){
                        if(used.containsKey(v)){
                            continue;
                        }
                        if(to.length() > 0)to += ',';
                        to += v;
                        used.put(v , true);
                    }
                }
                if(to.length() > 0)new_f.put(new Pair<String , String>(st , temp) , to);
            }
        }
        System.out.println(A);
        System.out.println(new_S.size());
        System.out.println(new_S);
        System.out.println(new_s0 + 1);
        System.out.println(new_F.size());
        System.out.println(new_F);
        System.out.println(new_f);
    }
}

class Pair<T1 extends Comparable<T1> , T2  extends Comparable<T2> > implements Comparable<Pair<T1,T2>>{
    T1 x;
    T2 y;
    Pair(T1 _x , T2 _y){
        x = _x;
        y = _y;
    }
    T1 first(){
        return x;
    }
    T2 second(){
        return y;
    }
    public final Comparator<Pair<T1, T2>> KEY_COMPARATOR = new Comparator<Pair<T1, T2>>() {
        public int compare(Pair<T1, T2> first, Pair<T1, T2> second) {
            if(first.first().equals(second.first()))
                return first.second().compareTo(second.second());
            return  first.first().compareTo(second.first());
        }
    };

    @Override
    public int compareTo(Pair<T1,T2> other){
        if(first().equals(other.first()))
            return second().compareTo(other.second());
        return  first().compareTo(other.first());
    }
    public boolean equals(Object other){
        if (other instanceof Pair) {
            Pair otherPair = (Pair) other;
            return
                    ((  this.x == otherPair.x ||
                            ( this.x != null && otherPair.x != null &&
                                    this.x.equals(otherPair.x))) &&
                            (   this.y == otherPair.y ||
                                    ( this.y != null && otherPair.y != null &&
                                            this.y.equals(otherPair.y))) );
        }
        return false;
    }

    public String toString(){
        return "{" + x.toString() + " ; " + y.toString() + "}";
    }

    public int hashCode(){
        int hash = 31;
        int res = 1;
        res = hash * res + x.hashCode();
        res = hash * res + y.hashCode();
        return res;
    }
}