#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct Subject {
  int score, year, semester;
  string name;
  vector<int> to;
  int prof, id;
  Subject(int _score = -1, int _year = -1, int _semester = -1,
    string _name = "", vector<int> _to = {-1}){
      score = _score;
      year = _year;
      semester = _semester;
      name = _name;
      to = _to;
  }
};

Subject T[35];
vector<int> need[35];

int dfs(int v){
  int prof = 0;
  for(unsigned j = 0; j < T[v].to.size(); j++){
    int w = T[v].to[j];
    prof = max(prof, dfs(w) + 1);
  }
  return prof;
}

bool by_prof(Subject a, Subject b){
  if(a.prof == b.prof){
    if(a.year == b.year){
      return a.semester > b.semester;
    }
    return a.year > b.year;
  }
  return a.prof > b.prof;
}

bool by_year(Subject a, Subject b){
  if(a.year == b.year){
    return a.semester < b.semester;
  }
  return a.year < b.year;
}

void getCorrelativities(){
  vector<Subject> S[35];
  for(int i = 1; i <= 32; i++){
    for(unsigned int j = 0; j < T[i].to.size(); j++){
      S[ T[i].to[j] ].push_back( T[i] );
    }
  }
  sort(T + 1, T + 33, by_year);
  int last = 0;
  int sem = 0;
  for(int i = 1; i <= 32; i++){
    int id = T[i].id;
    if(T[i].year > last){
      last = T[i].year;
      sem = 0;
      printf("Year: %d\n", last);
    }
    if(T[i].semester > sem){
      sem = T[i].semester;
      printf("    Semester: %d\n", sem);
    }
    printf("        %s:\n", T[i].name.c_str());
    for(unsigned int j = 0; j < S[id].size(); j++){
      printf("            -> %s\n", S[id][j].name.c_str());
    }
  }
}

void getOrderBlock(){

}

int main(){
  /* DATA */

  T[1]  = Subject(9,  1, 1, "Algebra y Geometria Analitica I", {4});
  T[2]  = Subject(9,  1, 1, "Analisis Matematico I", {5});
  T[3]  = Subject(10, 1, 1, "Programacion I", {6});
  T[4]  = Subject(8,  1, 2, "Algebra y Geometria Analitica II", {7});
  T[5]  = Subject(9,  1, 2, "Analisis Matematico II", {13, 14, 26});
  T[6]  = Subject(9,  1, 2, "Programacion II", {8, 9, 12});

  T[7]  = Subject(-1, 2, 1, "Algebra Lineal", {10, 13, 26});
  T[8]  = Subject(10, 2, 1, "Estructura de Datos y Algoritmos I", {10, 11, 15});
  T[9]  = Subject(-1, 2, 1, "Lenguajes Formales y Computabilidad", {25});
  T[10] = Subject(-1, 2, 2, "Complementos de Matematica I", {15});
  T[11] = Subject(-1, 2, 2, "Arquitectura del Computador", {18, 19});
  T[12] = Subject(-1, 2, 2, "Logica", {16, 20, 21, 23, 26});
  T[13] = Subject(-1, 2, 2, "Metodos Numericos", {29, 30});

  T[14] = Subject(-1, 3, 1, "Probabilidad y Estadistica", {17});
  T[15] = Subject(-1, 3, 1, "Estructuras de Datos y Algoritmos II", {16, 20, 21, 23, 25});
  T[16] = Subject(-1, 3, 2, "Analisis de Lenguajes de Programacion", {25});
  T[17] = Subject(-1, 3, 2, "Modelos Fisicos", {29, 30});
  T[18] = Subject(-1, 3, 1, "Sistemas Operativos I", {22});
  T[19] = Subject(-1, 3, 2, "Comunicaciones", {29, 30});
  T[20] = Subject(-1, 3, 2, "Teoria de Bases de Datos", {23});
  T[31] = Subject(8,  3, 2, "Ingles", {21, 22, 23, 25, 26, 29, 30});

  T[21] = Subject(-1, 4, 1, "Ingenieria del Software I", {24, 27});
  T[22] = Subject(-1, 4, 1, "Sistemas Operativos II", {29, 30});
  T[23] = Subject(-1, 4, 2, "Introduccion a la Inteligencia Artificial", {29, 30});
  T[24] = Subject(-1, 4, 2, "Ingenieria del Software II", {32});
  T[25] = Subject(-1, 4, 2, "Compiladores", {32});
  T[26] = Subject(-1, 4, 2, "Complementos de Matematica II", {32});

  T[27] = Subject(-1, 5, 1, "Seguridad Informatica", {32});
  T[28] = Subject(-1, 5, 2, "Optativa", {32});
  T[29] = Subject(-1, 5, 1, "Practica Profesional", {32});
  T[30] = Subject(-1, 5, 2, "Taller de Tesina", {32});
  T[32] = Subject(-1, 5, 2, "Tesina", {});

  /* END OF DATA */

  for(int i = 1; i <= 32; i++){
    T[i].id = i;
    for(unsigned int j = 0; j < T[i].to.size(); j++){
      need[ T[i].to[j] ].push_back(i);
    }
  }

  getCorrelativities();
  getOrderBlock();

  printf("Aprobar una materia de grado i, significa que al menos faltan \
unos i semestres para terminar\n\n");

  for(int i = 1; i <= 32; i++){
    int d = dfs(i);
    T[i].prof = d;
    //~ printf("%2d: %50s: %d [%c]\n", i, T[i].name.c_str(), d, T[i].score >= 6 ? 'x' : ' ');
  }

  sort(T + 1, T + 33, by_prof);
  for(int i = 1; i <= 32; i++){
    printf("%2d: %50s: %d [%c] : [", T[i].id, T[i].name.c_str(), T[i].prof, T[i].score >= 6 ? 'x' : ' ');
    const vector<int> &V = need[ T[i].id ];
    for(unsigned j = 0; j < V.size(); j++){
      printf("%d", V[j]);
      if(j + 1 < V.size()) printf(", ");
    }
    puts("]");
  }

  return 0;
}