#!/usr/bin/python3

# Vstup
strom = [None, 0, 1, 2, 3, 3, 5, 0, 7, 7, 15, 15, 15, 1, 1, 0]

# Hashovacia tabuľka, aby sme v konštantnom čase vedeli zistiť, či sa v nej prvok nachádza
dolezite = {2, 4, 6, 7, 10, 12}

# Vlastná výnimka pre prípad neexistujúceho riešenia
class NemaRiesenie(Exception):
	pass

# Funkcia, ktorá nám vráti číslo dôležitého ešte nespárovaného vrcholu
# podstromu s koreňom vo "vrchol"
def vrat_doleziteho(vrchol):
	global synovia, sparovanie

    # Zistíme si dôležité vrcholy u každého syna
	zoznam_dolezitych = [ vrat_doleziteho(syn) for syn in synovia[vrchol] ]
    # Vynecháme tie, ktoré pod sebou nemali žiaden dôležitý vrchol
    zoznam_dolezitych = [ v for v in zoznam_dolezitych if v is not None ]

    # Ak je aktuálny vrchol tiež dôležitý, tak ho do zoznamu pridáme
	if vrchol in dolezite:
		zoznam_dolezitych.append(vrchol)
    # Zistíme si celkový počet dôležitých vrcholov
	pocet_dolezitych = len(zoznam_dolezitych)
	
    # Ak v podstrome s koreňom "vrchol" nie je žiadny dôležitý vrchol tak
    # vrátime "None"
	if pocet_dolezitych == 0:
		return None

    # Ak je práve jeden dôležitý, tak ten posunieme do otca vrcholu "vrchol"
	if pocet_dolezitych == 1:
		return zoznam_dolezitych[0]

    # Ak sú dôležité práve dva, tak ich spárujeme a do vyššej úrovne nám už
    # nepôjde žiadny nespárovaný dôležitý vrchol
	if pocet_dolezitych == 2:
		sparovanie.append(tuple(zoznam_dolezitych))
		return None

    # Ak by malo "vrcholom" prechádzať viac spojení, tak riešenie neexistuje
	raise NemaRiesenie


# Zatiaľ sme nenašli žiadne párovania
sparovanie = []

# Vytvoríme si zoznam synov pre každý vrchol
synovia = [ [] for _ in strom ]
for syn, otec in enumerate(strom):
	if otec is not None:
		synovia[otec].append(syn)

try:
    # Ak ani koreň celého stromu nevrátil nespárovaný vrchol, tak sme našli
    # riešenie
    if vrat_doleziteho(strom.index(None)) is None:
		print(sparovanie)
	else:
		raise NemaRiesenie
except NemaRiesenie:
	print("Sparovanie neexistuje.")