#include <iostream>
# include <bits/stdc++.h>
using namespace std;

class  Node {
public:
vector <string > arr;
int final_state=0;
char name;
void inti(){
arr.clear();
final_state=0;
  name ='-';
}
};

class  table_elem {
public:
vector <string > arr;
char name;
void inti(){
arr.clear();
 // name;
}
};


int find_index(vector<vector<Node> > arr_2D,string str)
{
    int index;
    for(int i = 0;i < arr_2D.size();i++)
    {
        if(str == arr_2D[i][0].arr[0])
        {
                index = i;
                break;
        }
    }
    return index;
}

int vector_compare(vector<string> v1 ,vector<string> v2)
{
    if(v1.size() != v2.size())
        return 0;
    sort(v1.begin(), v1.begin()+v1.size());
    sort(v2.begin(), v2.begin()+v2.size());
    for(int i =0; i <v1.size();i++)
    {
        if(v1[i] != v2[i]){
            return 0;
        }
    }
    return 1;
}

int find_complex_index(vector<vector<Node> > arr_2D, vector<string> arr)
{
    for(int j =0; j < arr_2D.size();j++)
    {   cout << vector_compare(arr_2D[j][0].arr,arr)<<endl;
        if(vector_compare(arr_2D[j][0].arr,arr))
            return j;
    }
}


vector<vector<Node> > NFA_DFA(vector<vector<Node> > arr_2D, vector<string> transtion){
    stack <Node> st;
    vector <table_elem> table_equivalence;
    vector<vector<Node> > DFA_array;
    vector <Node>row;
    int current_char = 65;
    Node elem;
    table_elem tab_elem;
    elem.arr.push_back(arr_2D[0][0].arr[0]);
    elem.name=(char)current_char;
    current_char++;
    elem.final_state=arr_2D[0][0].final_state;
   // row.push_back(elem);
    st.push(elem);
    elem.inti();

    while(!st.empty())
    {
        //cout << "yes"<<endl;
        int row_index;
        Node top =  st.top();
        st.pop();
        row.push_back(top);

        if(top.arr.size() == 1)
          row_index = find_index(arr_2D,top.arr[0]);
        else
        {
            vector<int> indexes;
            for(int k = 0; k < top.arr.size();k++)
            {
                indexes.push_back(find_index(arr_2D,top.arr[k]));
            }
        vector<Node> rowrow;
        rowrow.push_back(top);
        for(int o = 1; o < transtion.size(); o++)
        {
            rowrow.push_back(arr_2D[indexes[0]][o]);
        }
        for(int l = 1; l < indexes.size(); l++)
        {
            for(int o = 1; o < transtion.size(); o++)
            {
                for(int v = 0; v < arr_2D[indexes[l]][o].arr.size(); v++)
                {
                    int matched = 0;
                    for(int h = 0;h < rowrow[o].arr.size(); h++)
                    {
                        if(rowrow[o].arr[h] == arr_2D[indexes[l]][o].arr[v])
                            matched = 1;
                    }
                    if(!matched)
                    rowrow[o].arr.push_back(arr_2D[indexes[l]][o].arr[v]);
                }
            }
        }

        arr_2D.push_back(rowrow);
        /*for(int g = 0;g < transtion.size(); g++)
        {
            for(int f = 0;f < arr_2D[arr_2D.size() - 1][g].arr.size();f++)
                    cout << "hello    " <<arr_2D[arr_2D.size() - 1][g].arr[f] <<'\t';
        cout<< endl;
        }*/
        for(int s = 0; s < arr_2D.size(); s++)
        {
            for(int r = 0; r < arr_2D[s][0].arr.size();r++)
            {
                    cout<< arr_2D[s][0].arr[r] << '\t';
            }
            cout << endl;
        }
        row_index = find_complex_index(arr_2D,top.arr);
        for(int y = 0; y < top.arr.size(); y++)
        {
            cout << top.arr[y] << '\t';
        }
        cout << endl;
        }

        for(int i = 1; i < transtion.size();i++)
        {
            int counter = 0;
            int flag = 0;
            for(int j= 0;j < table_equivalence.size();j++)
            {
                if( arr_2D[row_index][i].arr.size() != 0){

                if(vector_compare(arr_2D[row_index][i].arr,table_equivalence[j].arr))
                {
                    flag = 1;
                    counter = j;
                    break;
                }else
                {
                    flag = 0;
                }
                }else           //if the node is empty
                {
                    flag = 2;
                }
            }
            if(flag == 0)
            {
                tab_elem.arr = arr_2D[row_index][i].arr;
                tab_elem.name = (char)current_char;
                table_equivalence.push_back(tab_elem);
                tab_elem.inti();
                elem.name = (char) current_char;
                elem.arr = arr_2D[row_index][i].arr;
                row.push_back(elem);
                st.push(elem);
                elem.inti();
                current_char++;
            }else if(flag == 1)
            {
                elem.name = table_equivalence[counter].name ;
                elem.arr = table_equivalence[counter].arr ;
                row.push_back(elem);
                elem.inti();
            }else
            {
                elem.inti();
                row.push_back(elem);
            }
        }
                DFA_array.push_back(row);
                row.clear();
    }

cout << DFA_array.size() << endl;

for (int x=0;x < DFA_array.size();x++){
    for(int y =0;y < 3; y++)
    {
        cout << DFA_array[x][y].name<<'\t';
    }
    cout<<endl;
}
return DFA_array;
}

int main()
{
   /*
    vector<string> transition;
    transition.push_back("a");
    transition.push_back("a");
    transition.push_back("a");
    Node n1;
    n1.arr.push_back("s1");
    Node n2;
    n2.arr.push_back("s2");
    Node n3;
    n3.arr.push_back("s3");
    Node n4;
    n4.arr.push_back("s2");
    n4.arr.push_back("s3");
    vector<vector <Node> > Nfa;
    vector <Node> row;
    row.push_back(n1);
    row.push_back(n4);
    row.push_back(n2);
    Nfa.push_back(row);
    row.clear();
    row.push_back(n2);
    row.push_back(n2);
    row.push_back(n3);
    Nfa.push_back(row);
    row.clear();
    row.push_back(n3);
    row.push_back(n3);
    row.push_back(n3);
    Nfa.push_back(row);
    NFA_DFA(Nfa,transition);*/

    vector<string> transition;
    transition.push_back("a");
    transition.push_back("a");
    transition.push_back("a");
    Node n1;
    n1.arr.push_back("s1");
    Node n2;
    n2.arr.push_back("s2");
    Node n3;
    n3.arr.push_back("s3");
    Node n4;
    n4.arr.push_back("s4");
    Node n5;
    n5.arr.push_back("s2");
    n5.arr.push_back("s3");
    Node n6;
    n6.arr.push_back("s1");
    n6.arr.push_back("s3");
    Node n7;
    vector<vector <Node> > Nfa;
    vector <Node> row;
    row.push_back(n1);
    row.push_back(n5);
    row.push_back(n7);
    Nfa.push_back(row);
    row.clear();
    row.push_back(n2);
    row.push_back(n7);
    row.push_back(n6);
    Nfa.push_back(row);
    row.clear();
    row.push_back(n3);
    row.push_back(n4);
    row.push_back(n4);
    Nfa.push_back(row);
    row.clear();
    row.push_back(n4);
    row.push_back(n2);
    row.push_back(n4);
    Nfa.push_back(row);
    NFA_DFA(Nfa,transition);
    return 0;
}