// Copyright 2019 SD_Homework_Team
#ifndef SOLVER_H_
#define SOLVER_H_
#include "functions.h"

class solver {
 public:
 	std::string Noduri[MAX];
	std::vector<std::string> Strazi[MAX];
	std::queue<int> Coada;
	int dist[MAX];
	int viz[MAX] = {0};
	int viz2[MAX] = {0};
	int gN, gM;

	/*int find(std::string nod, int N){
		int step,i;
		for (step = 1; step < N; step<<=1);
		for (i = 0; step; step>>=1){
			if (i + step < N && Noduri[i + step] <= nod){
				i += step;
			}
		}
		return i;
	}
	*/

 int find(std::string nod, int N) {
    int left = 0;
    int right = N - 1;
    int mid = 0;

    while (left <= right) {
      mid = (left + right) / 2;

      if (Noduri[mid] == nod) {
        return mid;
      }

      if (Noduri[mid] < nod) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return 0;
  }

  void DFS(std::string current, int stop, int N) {
    int pozCurr = find(current, N);
    viz[pozCurr] = 1;
    if (viz[stop] == 1) return;
    for (unsigned int i = 0; i < Strazi[pozCurr].size(); i++) {
      if (!viz[find(Strazi[pozCurr][i], N)]) {
        DFS(Strazi[pozCurr][i], stop, N);
      }
    }
  }

  void Dijkstra(int node, int N,int stop) {
    for (int i = 0; i < N; i++) {
      dist[i] = INF;
    }
    dist[node] = 0;
    viz[node] = 1;
    if (node == stop) return;
    if (viz[stop] == 1) return;
    Coada.push(node);
    while (!Coada.empty()) {
      int nodCur = Coada.front();
      Coada.pop();
      viz[nodCur] = 1;
      for (unsigned int i = 0; i < Strazi[nodCur].size(); i++) {
        int vecin = find(Strazi[nodCur][i], N);
        if (dist[nodCur] + 1< dist[vecin]) {
          dist[vecin] = dist[nodCur] + 1;
          if (!viz[vecin]) {
            Coada.push(vecin);
            viz[vecin] = 1;
          }
        }
      }
    }
  }

  void task1_solver(std::ifstream& fin, std::ofstream& fout) {
    int N, M;
    std::string a, b;
    fin >> N;
    fin >> M;
    gN = N;
    gM = M;
    for (int i = 0; i < N; i++) {
      fin >> Noduri[i];
    }
    for (int i = 0; i < M; i++) {
      fin >> a >> b;
      int p1 = find(a, N);
      Strazi[p1].push_back(b);
    }

    // citire lista queries
    int Q1 = 0;
    fin >> Q1;

    for (int i = 0; i < Q1; i++) {
      fin >> a >> b;
      memset(viz, 0, sizeof(viz));
      DFS(a, find(b, N), N);

      if (viz[find(b, N)]) {
        fout << 'y' << std::endl;
      } else {
        fout << 'n' << std::endl;
      }
    }
  }

  void task2_solver(std::ifstream& fin, std::ofstream& fout) {
    std::string a, b;
    int N = gN;
    int Q2 = 0;
    fin >> Q2;
    for (int i = 0; i < Q2; i++) {
      fin >> a >> b;
      memset(dist, 0, sizeof(dist));
      memset(viz, 0, sizeof(viz));
      Dijkstra(find(a, N), N,find(b, N));
      if (!viz[find(b, N)]) {
        fout << "-1" << endl;
      } else {
        fout << dist[find(b, N)] << endl;
      }
    }
  }

  void task3_solver(std::ifstream& fin, std::ofstream& fout) {
    char character;
    int decision, Q3 = 0, okAB = 0, okBA = 0, N = gN, ans1, ans2, answer;
    std::string a, b,c;
    fin >> Q3;
    for (int i = 0; i < Q3; i++) {
      fin >> character >> a >> b >> decision;
      if (character == 'c' && decision == 0) {
        // c a b 0
        // pushback in vecinii lui a pe b
        for (unsigned int i = 0; i < Strazi[find(a,N)].size(); i++) {
          Strazi[find(a, N)].push_back(b);
        }
       }

      if (character == 'c' && decision == 1) {
        // c a b 1
        // te duci prin toti vecinii lui a si vezi daca exista b ca si vecin.
        // daca Strazi[find(a)][i] == find(b) atunci faci Strazi.erase(i)
        // te duci prin toti vecinii lui b si vezi daca exista a ca si vecin.
        // daca Strazi[find(b)][i] == find(a) atunci faci Strazi.erase(i)
        for (unsigned int i = 0; i < Strazi[find(a, N)].size();i++) {
          if (Strazi[find(a, N)][i] == b) {
         	Strazi[i].erase(Strazi[i].begin() + i);
         }
        }
        for (unsigned int i = 0; i < Strazi[find(b, N)].size();) {
          if (Strazi[find(b, N)][i] == a) {
            Strazi[i].erase(Strazi[i].begin() + i);
         }
        }
      }
        if (character == 'c' && decision == 2) {
          // c a b 2
          // te uiti prin toti vecinii lui a, daca il are vecin pe b -> iti faci
          // un okAB = 1 daca se intampla asta te uiti prin toti vecinii lui b,
          // daca il are vecin pe a -> iti faci un okBA = 1 daca se intampla asta
          // daca okAB == 1 && okBA == 1 nu faci nimic
          // daca okAB == 1 && okBA == 0 faci muchie intre B si A adica
          // Strazi[find(b)].push_back(find(a))
          for (unsigned int i = 0; i < Strazi[find(a, N)].size(); i++) {
            if (Strazi[find(a, N)][i] == b) {
              okAB = 1;
            } else
              okAB = 0;
          }
          for (unsigned int i = 0; i < Strazi[find(b, N)].size(); i++) {
            if (Strazi[find(b, N)][i] == a) {
              okBA = 1;
            } else
              okBA = 0;
          }
          if (okAB == 1 && okBA == 0) {
            Strazi[find(b, N)].push_back(a);
          }
          if (okAB == 0 && okBA == 1) {
            Strazi[find(a, N)].push_back(b);
          }
          if (okAB == 0 && okBA == 0){
          	Strazi[find(a,N)].push_back(b);
          	Strazi[find(b,N)].push_back(a);
          }
        }
        if (character == 'c' && decision == 3) {
          for (unsigned int i = 0; i < Strazi[find(a, N)].size(); i++) {
            if (Strazi[find(a, N)][i] == b) okAB = 1;
            else okAB = 0;
          }
          for (unsigned int i = 0; i < Strazi[find(b, N)].size(); i++) {
            if (Strazi[find(b, N)][i] == a) okBA = 1;
            else okBA = 0;
          }
          if (okAB == 1 && okBA == 1){}
          if (okAB == 1 && okBA == 0){
          	for (unsigned int i = 0; i < Strazi[find(a,N)].size();i++){
          		Strazi[find(a,N)].erase(Strazi[find(a,N)].begin() + find(b,N));
          		Strazi[find(b,N)].push_back(a);
          	}
          }
          if (okBA == 1 && okAB == 0){
          	for (unsigned int i = 0; i < Strazi[find(b,N)].size();i++){
          		Strazi[find(b,N)].erase(Strazi[find(b,N)].begin() + find(a,N));
          		Strazi[find(a,N)].push_back(b);
          	}
          }
        }
        if (character == 'q' && decision == 0) {
          // q a b 0
          // apelezi verificarea de exista a muchiei cu DFS din task 1
          memset(viz, 0, sizeof(viz));
          DFS(a, find(b, N), N);

          if (viz[find(b, N)]) {
            fout << 'y' << std::endl;
          } else {
            fout << 'n' << std::endl;
          }
        }
        if (character == 'q' && decision == 1) {
          memset(dist, 0, sizeof(dist));
          memset(viz, 0, sizeof(viz));
          Dijkstra(find(a, N), N,find(b, N));
          if (!viz[find(b, N)]) {
            fout << "-1" << endl;
          } else {
            fout << dist[find(b, N)] << endl;
          }
        }
        if (character == 'q' && decision == 2) {
        	fin >> c;
       	  memset(viz,0,sizeof(viz));
          DFS(a,find(c,N),N);
          if (viz[find(c,N)] == 1){
          	DFS(c,find(b,N),N);
          	if (viz[find(b,N)] == 1){
          		Dijkstra(find(a,N),N,find(b, N));
          		ans1 = dist[find(c,N)];
          		Dijkstra(find(c,N),N,find(b, N));
          		ans2 = dist[find(b,N)];
          		answer = ans1 + ans2;
          		fout << answer << std::endl;
          	}
          	else {
          		fout << -1 << std::endl;
          	}
          }
          else {
          	fout << -1 << std::endl;
          }
         }
    }

}

    void task4_solver(std::ifstream & fin, std::ofstream & fout) {}

    void task5_solver(std::ifstream & fin, std::ofstream & fout) {}
  };

#endif  // SOLVER_H_