#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<string> tokenizer(string line)
{
    vector <string> tokens;
    stringstream check1(line);
    string intermediate;
    // Tokenizing w.r.t. space ' '
    while(getline(check1, intermediate, ' '))
    {
        tokens.push_back(intermediate);
    }
    return tokens;
}

bool check_duplicate (string str , vector<string> temp)
{
    for(int i=0; i < temp.size(); i++)
    {
        if(temp[i] == str)
        {
            return true;
        }
    }
    return false;
}

vector<int> find_match(string str,vector<string> tokens)
{
    vector<int> indexes;
    for(int i = 0; i < tokens.size(); i++)
    {
        if(str == tokens[i])
        {
            indexes.push_back(i);
        }
    }
    return indexes;
}

int get_index(string poped,vector<vector <string> > input)
{
    for(int i = 0; i < input.size();i++)
    {
        if(poped == input[i][0])
            return i ;
    }
    return -1;
}

string get_first_token(string str)
{
    stringstream check1(str);
    string intermediate;
    if(getline(check1, intermediate, ' '))              // Tokenizing w.r.t. space ' '
        return intermediate;
}

bool is_non_terminal(string str)
{
    string first_token = get_first_token(str);
    if(first_token[0] == '\'')
        return false;
    return true;
}

string remove_quotes(string str)
{
    return str.substr(1, str.size()-2);
}

vector<vector <string> > find_first(vector<vector<string> > input)
{
    stack<string> st;
    vector<vector <string> > first;
    vector<string> temp;
    for(int i = input.size() - 1; i >= 0; i--)
    {
        temp.push_back(input[i][0]);
        for(int j = 1; j < input[i].size(); j++)
        {
            if(is_non_terminal(input[i][j]))
            {
                string first_token = get_first_token(input[i][j]);
                int first_index = get_index(first_token,first);
                if(first_index == -1)
                    st.push(get_first_token(input[i][j])); //split on space and push non terminal on the stack .
                else
                {
                    for(int k = 1; k < first[first_index].size(); k++)
                    {
                        temp.push_back(first[first_index][k]);
                    }
                }
            }
            else
            {
                string terminal = get_first_token(input[i][j]);
                if(!check_duplicate(terminal,temp))
                    temp.push_back(remove_quotes(terminal));    //push terminal
                //before pushing in the vector check duplicates
            }
        }

        while(!st.empty())
        {
            string poped;
            poped = st.top();
            st.pop();
            int input_index = get_index(poped,input);
            for(int j = 1; j < input[input_index].size(); j++)
            {
                if(is_non_terminal(input[input_index][j]))
                {
                    string first_token = get_first_token(input[input_index][j]);
                    int first_index = get_index(first_token,first);
                    if(first_index == -1)
                        st.push(get_first_token(input[input_index][j])); //split on space and push non terminal on the stack .
                    else
                    {
                        for(int k = 1; k < first[first_index].size(); k++)
                        {
                            temp.push_back(first[first_index][k]);
                        }
                    }

                    // st.push(get_first_token(input[index][j])); //split on space and push non terminal on the stack .
                }
                else
                {
                    string terminal = get_first_token(input[input_index][j]);
                    if(!check_duplicate(terminal,temp))
                        temp.push_back(remove_quotes(terminal));    //push terminal
                    //before pushing in the vector check duplicates
                }
            }
        }

        first.push_back(temp);
        temp.clear();
    }
    reverse(first.begin(),first.end());

    return first;
}

vector <vector<string> > find_follow(vector <vector<string> > input)
{
    vector <vector<string> > first = find_first(input);
    cout <<first.size()<<endl;
    vector <vector<string> > follow;
    vector <string> temp;
    vector <string> tokens;
    for(int i =0; i < 4; i++)
    {
        //cout <<"hello" <<endl;
        string search_follow = input[i][0];
        temp.push_back(search_follow);
        if(i == 0)
            temp.push_back("$");
        for(int j =0; j < input.size(); j++)
        {
            for(int k = 1; k < input[j].size(); k++)
            {
                tokens = tokenizer(input[j][k]);
                vector<int> indexes = find_match(search_follow,tokens);
                for(int l =0; l < indexes.size(); l++)
                {
                    if(tokens.size() > indexes[l] + 1 && !is_non_terminal(tokens[indexes[l]+ 1]))    //after the matched string check if terminal
                    {
                        temp.push_back(remove_quotes(tokens[indexes[l]+ 1]));
                    }
                    else if(indexes[l] == tokens.size() - 1 && input[j][0] != tokens[indexes[l]])
                    {

                        int follow_index = get_index(input[j][0],follow);
                        for(int m = 1; m < follow[follow_index].size();m++)
                        {
                            temp.push_back(follow[follow_index][m]);
                            cout << follow[follow_index][m]<<endl;
                        }

                    }else if(tokens.size() > indexes[l] + 1 && input[j][0] != tokens[indexes[l]+1])
                    {
                        int first_index = get_index(tokens[indexes[l]+1],first);
                        for(int m = 1; m < first[first_index].size();m++)
                            temp.push_back(first[first_index][m]);
                    }
                }
            }
        }
        /* for(int j=0; j <temp.size(); j++)
         {
             cout << temp[j] << '\t';
         }
         cout <<endl;*/
        follow.push_back(temp);
        temp.clear();
    }
    for(int i = 0; i < follow.size(); i++)
    {
        for(int j=0; j <follow[i].size(); j++)
        {
            cout << follow[i][j] << '\t';
        }
        cout <<endl;
    }
    return follow;
}

int main()
{
    vector <vector <string> > input;
    vector<string> temp;
    temp.push_back("METHOD_BODY");
    temp.push_back("STATEMENT_LIST");
    input.push_back(temp);
    temp.clear();
    temp.push_back("STATEMENT_LIST");
    temp.push_back("STATEMENT STATEMENT_LIST'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("STATEMENT_LIST'");
    temp.push_back("STATEMENT STATEMENT_LIST'");
    temp.push_back("'\\L'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("STATEMENT");
    temp.push_back("DECLARATION");
    temp.push_back("IF");
    temp.push_back("WHILE");
    temp.push_back("ASSIGNMENT");
    input.push_back(temp);
    temp.clear();
    temp.push_back("DECLARATION");
    temp.push_back("PRIMITIVE_TYPE 'id';'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("PRIMITIVE_TYPE");
    temp.push_back("'int'");
    temp.push_back("'float'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("IF");
    temp.push_back("'if' '(' EXPRESSION ')' '{' STATEMENT '}' 'else' '{' STATEMENT '}'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("WHILE");
    temp.push_back("'while' '(' EXPRESSION ')' '{' STATEMENT '}'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("ASSIGNMENT");
    temp.push_back("'id' '=' EXPRESSION ';'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("EXPRESSION");
    temp.push_back("SIMPLE_EXPRESSION ACTION'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("ACTION'");
    temp.push_back("'relop' SIMPLE_EXPRESSION");
    temp.push_back("'\\L'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("SIMPLE_EXPRESSION");
    temp.push_back("TERM SIMPLE_EXPRESSION'");
    temp.push_back("SIGN TERM SIMPLE_EXPRESSION'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("SIMPLE_EXPRESSION'");
    temp.push_back("'addop' TERM SIMPLE_EXPRESSION'");
    temp.push_back("'\\L'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("TERM");
    temp.push_back("FACTOR TERM'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("TERM'");
    temp.push_back("'mulop' FACTOR TERM'");
    temp.push_back("'\\L'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("FACTOR");
    temp.push_back("'id'");
    temp.push_back("'num'");
    temp.push_back("'(' EXPRESSION ')'");
    input.push_back(temp);
    temp.clear();
    temp.push_back("SIGN");
    temp.push_back("'+'");
    temp.push_back("'-'");
    input.push_back(temp);
    find_follow(input);
    return 0;
}