#n = 10 # liczba wierzchołków w grafie n e C

#graf = #zadany w dowolnie wybrany sposób graf

#color = [True, True, True, True, True, False, False, False, False, False]

#matching = [0 for i in enumerate(range(len(color)))]


from collections import defaultdict


class Graph:

    def __init__(self, vertices):
        self.V = vertices  # liczba wierzchołków
        self.graph = defaultdict(list)  # słownik do przechowywania wykresu
        self.gender = [None for i in enumerate(range(self.V))] #tablica zawierajaca informację o płci, Tru-mężczyzna, Fal - Kobieta, Domyślnie - none

        self.matching = [-1 for i in enumerate(range(self.V))]

        self.Q = []
        self.visited = [None for i in enumerate(range(self.V))] #tablica zawierajaca informację o płci, Tru-mężczyzna, Fal - Kobieta, Domyślnie - none
        self.augment = [0 for i in enumerate(range(self.V))] #tablica zawierajaca informację o płci, Tru-mężczyzna, Fal - Kobieta, Domyślnie - none
        self.v = int
        self.x = int
        self.y = int

    def add_edge(self, u, v): #funkcja dodawania krawędzi
        self.graph[u].append(v)
        self.graph[v].append(u)

    def rmv_edge(self, u, v): # funkcja usuwa krwedź u-v z wykresu
        for index, key in enumerate(self.graph[u]):
            if key == v:
                self.graph[u].pop(index)
        for index, key in enumerate(self.graph[v]):
            if key == u:
                self.graph[v].pop(index)

    def insert_gender(self, u, g):
        self.gender[u] = g

    #def matching_test(self):
        #asd = 1

    def matching_AHA(self):
        for i in range(self.V): #k05
            #print("HURA")
            if self.matching[i] == -1 and self.gender[i] is False: #k05
                #print("ELO")

                self.visited = [False for vertex in enumerate(range(self.V))]
                self.Q.clear()

                self.visited[i] = True
                self.augment[i] = -1
                self.Q.append(i)
                print(self.Q)

                while not len(self.Q) == 0 : #k09


                        self.x = self.Q.pop() #k10
                        print(self.x)
                        print("elo")
                        print(self.gender[5])
                        print("przebieg whilenot")
                        if self.gender[self.x] is True: #K11

                            if self.matching[self.x] == -1: #K12

                                while self.augment[self.x] > -1: #K13

                                    if self.gender[self.x] is True:  #K14

                                        self.matching[self.x] = self.augment[self.x] #K15
                                        self.matching[self.augment[self.x]] = self.x

                                    self.x = self.augment[self.x]   #K16
                                break
                            else:
                                self.augment[self.matching[self.x]] = self.x
                                self.visited[self.matching[self.x]] = True
                                self.Q.append(self.matching[self.x])

                        else:
                            self.p = self.graph

                            self.y = self.p[self.x]
                            print(self.p)
                            print(self.y)
                            print("FASFAS")
                            print(self.visited)
                            #print(self.visited[self.y])
                            for blablazmienna in range(len(self.y)):
                                print(blablazmienna)
                                print(self.visited)
                                print("stop1")
                                print(self.y)
                                print(self.visited[self.y[blablazmienna]])
                                if not self.visited[self.y[blablazmienna]]:
                                    self.visited[self.y[blablazmienna]] = True
                                    self.augment[self.y[blablazmienna]] = self.x
                                    self.Q.append(self.y[blablazmienna])
        print("DZIALA?")
        print(self.matching)









"""
    # funkcja oparta na dfs do liczenia osiągalnych wierzchołków od v (zwraca liczbę)
    def DFSCount(self, v, visited):
        count = 1
        visited[v] = True
        for i in self.graph[v]:
            if visited[i] == False:
                count = count + self.DFSCount(i, visited)
        return count

    # funkcja sprawdzający czy krwaędź u-v można uznać za następną krawędź
    # Euler Tour
    def isValidNextEdge(self, u, v):
        # krawedź u-v jest dostęna w jednym z dwóch przypadków

        #  1) Jeżeli v jest jedynym sąsiadującem wierzchołkiem u
        if len(self.graph[u]) == 1:
            return True
        else:

            # 2) Jeżeli jest więcej sąsiadów, sprawdza się ilość połączeń które zostaną po usunięciu krawędzi u-v

            #2.a) liczymy wierzchołki osiągalne z u
            visited = [False] * (self.V)
            count1 = self.DFSCount(u, visited)

            #2.b) usuwamy krawędź (u, b), po usunięciu krawędzi sprawdzamy wierzchołki osiągalne z u
            self.rmvEdge(u, v)
            visited = [False] * (self.V)
            count2 = self.DFSCount(u, visited)

            # 2.c) dodajemy krawędź spowrotem do grafu
            self.addEdge(u, v)

            # 2.d) Jeżeli wartość count1 jest większa, to krawędź (u, v) jest mostem (zwracamy fałsz, o ile oczywiście wcześniej nie zostało uznane, że jest to ostatnia krawędź)
            #print(count1)
            #print(count2)
            #print(" ")
            return False if count1 > count2 else True

    # pokaz trase eulera zaczynajac od wierzchołka u
    def printEulerUtil(self, u):
        # powtóz dla wszystkich wierzchołków sąsiadujących z tym wierzchołkiem
        for v in self.graph[u]:
            # If edge u-v is not removed and it's a a valid next edge
            if self.isValidNextEdge(u, v):
                print("%d-%d " % (u, v)),
                self.rmvEdge(u, v)
                self.printEulerUtil(v)

    def printEulerTour(self):
        # Find a vertex with odd degree
        u = 0
        for i in range(self.V):
            #print(i)
            if len(self.graph[i]) % 2 != 0:
                u = i
                break
        # Print tour starting from odd vertex
        #print(u)
        self.printEulerUtil(u)
"""

#print("Graf")
g1 = Graph(10)

g1.insert_gender(0, True)
g1.insert_gender(1, True)
g1.insert_gender(2, True)
g1.insert_gender(3, True)
g1.insert_gender(4, True)
g1.insert_gender(5, False)
g1.insert_gender(6, False)
g1.insert_gender(7, False)
g1.insert_gender(8, False)
g1.insert_gender(9, False)


g1.add_edge(0, 7)
g1.add_edge(0, 8)

g1.add_edge(1, 5)
g1.add_edge(1, 6)
g1.add_edge(1, 8)

g1.add_edge(2, 5)

g1.add_edge(3, 6)
g1.add_edge(3, 8)
g1.add_edge(3, 9)

g1.add_edge(4, 7)
g1.add_edge(4, 8)

#g1.matching_test()
g1.matching_AHA()


#g1.printEulerTour()

#print("Graf 2 (tablica)")

#g2 = Graph(5)
#g2.addEdge(0, 1)
#g2.addEdge(0, 2)
#g2.addEdge(1, 2)
#g2.addEdge(1, 4)
#g2.addEdge(1, 3)
#g2.addEdge(3, 4)

#g2.printEulerTour()