Минимизация НКА без eps переходов

/* package whatever; // don't place package name! */
// By Max Osipyonok
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
    static int a , s , s0 , sz_f;
    static Set<Integer> F;
    static Map<Pair<Integer , Character> , ArrayList<Integer>> f;
    static Map<Pair<Integer , Integer> , ArrayList<Character>> rf;
    static Set<Integer> S;


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

        }


        boolean used[] = new boolean[s];
        Arrays.fill(used , false);
        dfs1(s0 , used);
        Drop(used);
        Arrays.fill(used , false);
        for(int v : F){
            if(!used[v]){
                dfs2(v , used);
            }
        }
        Drop(used);

        Map<Integer, Set<String>> out = new HashMap();
        for(int u : S){
            out.put(u , bfs(u));
        }
        DSU dsu = new DSU(s);
        for(int u : S){
            for(int v : S){
                if(dsu.find_set(u) != dsu.find_set(v)){
                    if(equalSets(out.get(u) , out.get(v))){
                        dsu.union_sets(u , v);
                    }
                }
            }
        }
        for(int i = 0 ; i < s ; ++i){
            if(dsu.find_set(i) != i){
                merge_states(dsu.find_set(i) , i);
            }
        }
        if(S.size() == 0 || !S.contains(s0)){
            System.out.println("Empty automata");
            return;
        }
        System.out.println(a);
        System.out.println(S.size());
        for(int i : S){
            System.out.print(i + 1 + " ");
        }
        System.out.println();
        System.out.println(s0 + 1);
        System.out.println(F.size());
        for(int i : F){
            System.out.print(i + 1 + " ");
        }
        System.out.println();
        for(Pair<Integer,Character> key : f.keySet()){
            for(int to : f.get(key)){
                System.out.println((key.first() + 1) + " " + key.second() + " " + (to + 1));
            }
        }
    }

    static void merge_states(int a , int b){
        S.remove(b);
        F.remove(b);

        for(char c = 'a' ; c <= 'a' + Main.a ; ++c){
            f.remove(new Pair<Integer , Character>(b , c));
        }
        Set<Pair<Integer , Character>> update = new HashSet();
        for(Pair<Integer , Integer> key : rf.keySet()){
            if(key.first() == b){
                ArrayList<Character> tmp = rf.get(key);
                for(char ch : tmp) {
                    update.add(new Pair<Integer, Character>(key.second(), ch));
                }
            }
        }
        for (Pair<Integer , Character> key : update){
            ArrayList<Integer> val = f.get(key);
            if(val == null)continue;
            if(!val.contains(a)){
                val.add(a);
            }
            val.remove((Object)b);
            f.put(key , val);
        }
    }
    static boolean equalSets(Set<String> a , Set<String> b){
        if(a.size() != b.size())return false;
        for(String s : a){
            if(!b.contains(s)){
                return false;
            }
        }
        return true;
    }

    static void Drop(boolean used[]){
        ArrayList<Pair<Integer,Integer>> rf_remove = new ArrayList();
        for(int i = 0 ; i < s ; ++i){
            if(!used[i]){
                S.remove(i);
                F.remove(i);
                for(ArrayList<Integer> al : f.values()){
                    //al.remove(i);
                    if(al == null)continue;
                    al.remove((Object)i);
                }
                for(Pair<Integer,Integer> key : rf.keySet()){
                    if(key.first().equals(i) || key.second().equals(i)){
                        //rf.remove(key);
                        rf_remove.add(key);
                    }
                }
                for(char c = 'a' ; c < 'a' + a ; ++c){
                    f.remove(new Pair<Integer , Character>(i , c));
                }
            }
        }
        for (Pair<Integer,Integer> key : rf_remove){
            rf.remove(key);
        }
    }

    static void dfs1(int cur , boolean used[]){
        used[cur] = true;
        for(char ch = 'a' ; ch < 'a' + a ; ++ch){
            if(f.containsKey(new Pair<Integer , Character>(cur , ch))){
                ArrayList<Integer> tmp = f.get(new Pair<Integer , Character>(cur , ch));
                for(int v : tmp){
                    if(!used[v]){
                        dfs1(v , used);
                    }
                }
            }
        }
    }

    static  void dfs2(int cur , boolean used[]){
        used[cur] = true;
        for(int u : S){
            if(!used[u]){
                if(rf.keySet().contains(new Pair<Integer, Integer>(cur , u))){
                    dfs2(u , used);
                }
            }
        }
    }



    static Set<String> bfs(int start){
        Set<String> ans = new HashSet<String>();
        Queue<Pair<Integer , String>> q = new PriorityQueue();
        q.add(new Pair<Integer , String>(start , ""));
        while(q.size() > 0){
            Pair<Integer , String> cur = q.element();
            q.remove();
            if(cur.second().length() > Math.max(S.size() - 2 , 1))continue;
            if(F.contains(cur.first())){
                ans.add(cur.second());
            }
            for(char ch = 'a' ; ch < 'a' + a ; ++ch){
                if(f.containsKey(new Pair<Integer , Character>(cur.first() , ch))){
                    ArrayList<Integer> tmp = f.get(new Pair<Integer , Character>(cur.first() , ch));
                    for(int v : tmp){
                        if((cur.second() + ch).length() <= Math.max(S.size() - 2 , 1)){
                            q.add(new Pair<Integer , String>(v , cur.second() + ch));
                        }
                    }
                }
            }

        }
        return ans;
    }


}

class DSU{
    private int[] parent;
    private int[] rank;

    public DSU(int n){
        parent = new int[n];
        rank = new int[n];
        for(int i = 0 ; i < n ; ++i){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find_set(int v){
        if(parent[v] == v){
            return v;
        }else{
            parent[v] = find_set(parent[v]);
        }
        return parent[v];
    }

    public void union_sets(int a , int b){
        a = find_set(a);
        b = find_set(b);
        if(a != b){
            if(rank[a] < rank[b]){
                int tmp = a;
                a = b;
                b = tmp;
            }
            parent[b] = a;
            if(rank[a] == rank[b]){
                ++rank[a];
            }
        }
    }
}

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