//I. 325.
//Kovács Balázs Marcell 11. évf.
//Budapest, ELTE Radnóti Miklós Gyakorló Iskola
//alkalmazott fordító: gcc 4.6.3 (Ubuntu/Linaro 4.6.3-4ubuntu5)

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <utility>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

typedef struct {
	unsigned char felado; //feladó id-ja
	unsigned short parent; //mire reagál
	list<unsigned short> childs; //erre válaszként érkező levelek id-ainak listája
} level_t;


bool rendezo(pair<unsigned char,unsigned short> a, pair<unsigned char,unsigned short> b){
	return (a.second>b.second);
}

ofstream outputf;

void zarojelek(unsigned short i, vector<level_t> level){
	list<unsigned short>::iterator itl; //iterator a child listák bejárásához
	outputf << i;
	if(!level[i].childs.empty()){
		outputf << " ( ";
		for(itl=level[i].childs.begin(); itl!=level[i].childs.end(); ++itl){
			zarojelek((*itl), level);
		}
		outputf << ")";
	}
	if(level[i].parent==0){
		outputf << "\n";
	}else{
		outputf << " ";
	}
}



int main (int argc, char* argv[]) {
	
	ifstream inputf((argc >= 2) ? argv[1] : "naplo.txt");
	if (!inputf.is_open()){
		cout << "Nem sikerült megnyitni a megadott input file-t!\n";
		return 1;
	}
	
	vector<level_t> level; //leveleket tároló dinamikus tömb
	list<unsigned short>::iterator itl; //iterator a child listák bejárásához
	level.push_back({101, 0}); //level[0] létrehozása
	
	vector<pair<unsigned char,unsigned short> > feladok(101, {0,0}); //Az 5. feladathoz szükséges, ebben tároljuk, hogy ki hány levelet küldött (feladó id, levelek száma)
	
	unsigned short felado;
	unsigned short parent;
	unsigned short i=0;
	while(inputf >> felado){
		i++;
		inputf >> parent;
		level.push_back({(unsigned char)felado, parent}); //új levél felvétele
		level[parent].childs.push_back(i); //parent levélnél felvevés, mint válasz
		
		feladok[felado].first = felado; //5. feladat. Később majd rendezzük, ezért van szükség a feladó id-t is eltárolni
		feladok[felado].second++; //5. feladat
	}
	
	//2. feladat (a leveleket már a beolvasásnál összeszámoltuk, ez a szám megegyezik a level.size()-1 -gyel is)
	cout << "2. feladat\nLevelek száma:\n" << i << "\n\n";
	
	//3. feladat
	cout << "3. feladat\nNyitólevelek sorszámai:\n";
	i=0;
	for(itl=level[0].childs.begin(); itl!=level[0].childs.end(); ++itl){ //a nyitólevelek parent-je a 0-ás levél
    	cout << *itl << " "; //sorszám kiírása
    	if(level[*itl].childs.empty()){i++;}//4. feladat; azért szerepel itt, hogy ne kelljen mégegyszer végigpörgetni a listát
    }
    cout << "\n\n";
    
    //4. feladat
    cout << "4. feladat\nElőzmény és válasz nélküli levelek száma:\n" << i << "\n\n";
    
    //5. feladat
    sort(feladok.begin(), feladok.end(), rendezo); //csökkenő sorrendbe rendezés
    cout << "5. feladat\nAz 5 legszorgalmasabb levelező:\n";
    for(i=0; i<5 && feladok[i].second!=0; i++){ //ha az aktív levelezők száma kisebb, mint 5, nem írunk ki értelmetlen sorokat
    	cout << (int)feladok[i].first << "\t" << feladok[i].second << endl;
    }
    cout << "\n";
	
	//6. feladat
	cout << "6. feladat\nAdd meg annak a levélnek a sorszámát, aminek kiváncsi vagy az előzményeire:\n> ";
	i=0;
	cin >> i;
	if(i>=level.size() || i==0){//input ellenőrzés
		cout << "Nincs ilyen sorszámú levél!\n\n";
	}else{
		while(i>0){
			cout << i << " ";
			i = level[i].parent; //ugrás a szülő elemre
		}
	}
	cout << "\n\n";
	
	//7. feladat
	cout << "7. feladat\nAdd meg az offtopic levél sorszámát:\n> ";
	i=0;
	cin >> i;
	if(i>=level.size() || i==0){//input ellenőrzés
		cout << "Nincs ilyen sorszámú levél!\n\n";
	}else{
		set<unsigned char> resztvevok; //ha valaki szerepel a levelezésben, felvesszük a halmazba
		set<unsigned char>::iterator its; //bejáráshoz szükséges iterator
		queue<unsigned short> megnezendo; //megnézendő levelek listája. Rekurzió elkerülése végett
		megnezendo.push(i); //a bekért levél feladójának is rá kell kerülnie a kiírandó listára

		while(!megnezendo.empty()){
			i = megnezendo.front(); megnezendo.pop(); //ugrás egy megnézendő levlére, majd leszedése a megnézendő listáról
			resztvevok.insert(level[i].felado); //résztvevő felvétele. Ha már szerepelt, nem lesz újra beszúrva
			//az adott levél gyerekeinek felvétele a megnézendő listára
			if(!level[i].childs.empty()){
				for(itl=level[i].childs.begin(); itl!=level[i].childs.end(); ++itl){
					megnezendo.push(*itl);
				}
			}
		}

		//Az eredmény kiírása
		for(its=resztvevok.begin(); its!=resztvevok.end(); ++its){
			cout << (int)*its << " ";
		}
		cout << "\n\n";
	}
	
	
	//8. feladat
	outputf.open((argc >= 3) ? argv[2] : "rend.txt");
	if (!inputf.is_open()){
		cout << "Nem sikerült megnyitni a megadott output file-t!\n";
		inputf.close();
		return 1;
	}
	for(itl=level[0].childs.begin(); itl!=level[0].childs.end(); ++itl){
		zarojelek((*itl), level);
	}
	
	inputf.close();
	outputf.close();


	return 0;
}