#importation des modules pythons
import random as r
import tkinter as tki
from math import *
import copy


#crée des noeuds a des positions aléatoires
def coo (n,min):
    res=[]
    for i in range (n):
        x=r.randint (100,900)
        y=r.randint (100,900)
        while espace (x,y,min,res):
            x=r.randint (100,900)
            y=r.randint (100,900)
           # print (i)
        res.append([x,y])
    return (res)


#teste l'espacement entre un point et tous ceux déjà générés
def espace (x,y,min,res):
    bool=False
    for j in range (len (res)):
        if sqrt((x-res[j][0])**2+(y-res[j][1])**2)<4*min:
            bool=True
    return (bool)


#infini est la somme de tous les chemins+1, aucun chemin ne peut depasser cette longueur ce qui suffit à représenter l'infini pour dijkstra
def infini (mat):
    inf=0
    for i in range (len (mat)):
        for j in range (len (mat)):
            inf=inf+mat[i][j]
    return (inf)


#distance entre 2 points a et b
def distance (a,b):
    return (sqrt((a[0]-b[0])**2+(a[1]-b[1])**2))


#matrice des distances
def distances (coos):
    n=len (coos)
    mat=[[0 for i in range (n)]for j in range (n)]
    for i in range (n):
        for j in range (n):
            mat[i][j] = distance (coos[i],coos[j])
    return mat


#trouve les indices de nb points les plus proches
def indi_min (m,nb):
    n=len (m)
    infi=infini (m)
    minis=[[0 for i in range (nb)]for j in range (n)]
    for i in range (n):
        mini=[infi for k in range (nb)]
        for j in range (n):
            k=0
            pasmin=True
            while k<nb and pasmin:
                if mini[k]>m[i][j]:
                    mini[k]=m[i][j]
                    minis[i][k]=j
                    pasmin=False
                k=k+1
    return (minis)


#crée une matrice d'adjacence a partir des coordonnées des noeuds
def init2 (nb,coos):
    n=len(coos)
    dist=distances (coos)
    res=[[0 for i in range (n)]for j in range (n)]
    indimin= indi_min (dist,nb)
    for i in range (n):
        for j in range (n):
            for k in range (nb):
                if indimin[i][k]== j:
                    res[i][j]=dist[i][j]
                    res[j][i]=dist[i][j]
    return res


#affiche le graphe
def affichage (coos,r,nb):
    wdw=tki.Tk ()
    wdw.title ("test")
    wdw.geometry ("1400x1000")
    wdw.config(background="#8CCCFE") #bleu pale
    wdw.maxsize (1400,1000)
    wdw.minsize (1400,1000)
    boite =tki.Frame (wdw,width=400,height=1000,bg="#8CCCFE")
    canvas=tki.Canvas (wdw,width=1000,height=1000,bg="#D0EAFE") #bleu pale clair
    n=len(coos)
    m=init2 (nb,coos)
    for i in range (n):
        for j in range (1+i,n):
            if m[i][j]>0:
                x1=coos[i][0]
                y1=coos[i][1]
                x2=coos[j][0]
                y2=coos[j][1]
                canvas.create_line (x1,y1,x2,y2,width=2)
    for i in range (n):
        x=coos[i][0]
        y=coos[i][1]
        canvas.create_oval (x+r,y+r,x-r,y-r,fill="red")
    #canvas.pack (fill="both",expand=tki.YES)
    canvas.pack (side="left")
    chemins=tki.Label(boite,text= "Générer le trafic",font=("Arial",30),bg="#8CCCFE",fg="white")
    chemins.pack(expand=tki.YES)
    nombr=tki.Entry(boite,font=("Arial",30),fg="#8CCCFE")
    nombr.pack(expand=tki.YES)
    trafftext= "générer"
    traff=tki.Button(boite,text= trafftext,font=("Arial",30),fg="#8CCCFE",command=print(m))
    traff.pack()
    boite.pack (side="right",expand=tki.YES)
    wdw.mainloop ()


#affiche un graphe àléatoire
def affich_rand (n,r,nb):
    return (affichage (coo (n,r),r,nb))


#dijkstra c'est pas moi qui l'ai fait, je l'ai trouvé ici: http://www.alcandre.net/uploads/TD-dijkstra.pdf

#trouve la première ligne du tableau de l'algorithme de dijkstra
def ligneInit(Graphe,depart) :
    L = []
    n = len(Graphe)
    for j in range(n) :
        poids = Graphe[depart][j]
        if poids :
            L.append([ poids, depart ])
        else :
            L.append(False)
    return [L]


#determine le prochain sommet que doit traiter dijkstra
def SommetSuivant(T, S_marques) :
    L = T[-1]
    n = len(L)
    min = False
    for i in range(n) :
        if not(i in S_marques) :
            if L[i]:
                if not(min) or L[i][0] < min :
                    min = L[i][0]
                    marque = i
    return(marque)


def ajout_ligne(T,S_marques,Graphe) :
    # Ajoute une ligne supplémentaire au tableau
    L = T[-1]
    n = len(L)
    # La prochaine ligne est une copie de la précédente,
    # dont on va modifier quelques valeurs.
    Lnew = L.copy()
    # sommet dont on va étudier les voisins
    S = S_marques[-1]
    # la longueur du (plus court) chemin associé
    long = L[S][0]
    for j in range(n) :
        if j not in S_marques:
            poids = Graphe[S][j]
            if poids :
            # si l’arète (S,j) est présente
                if not(L[j]) : # L[j] = False
                    Lnew[j] = [ long + poids, S ]
                else :
                    if long + poids < L[j][0] :
                        Lnew[j] = [ long + poids, S ]
    T.append(Lnew)
    # Calcul du prochain sommet marqué
    S_marques.append(SommetSuivant(T, S_marques))
    return T, S_marques


#calcule le tableau de l'algorithme de Dijkstra
def calcule_tableau(Graphe, depart) :
    n = len(Graphe)
    T=[[False] *n]
    T[0][depart] = [depart, 0]
    S_marques = [ depart ]
    while len(S_marques) < n :
        T, S_marques = ajout_ligne(T, S_marques, Graphe)
    return T


#Calcul du plus court chemin entre 2 noeud
def plus_court_chemin(Graphe, depart, arrivee) :
    n = len(Graphe)
    T = calcule_tableau (Graphe,depart)
    C = [ arrivee ]
    while C[-1] != depart :
        C.append( T[-1][ C[-1] ][1] )
    C.reverse()
    return C


#assigne au chemin une nouvelle longueur d'onde
def assigne_lambda (chemin,lambd):
    for i in range (len(chemin)):
        chemin[i][1].append(lambd)
    return chemin


#fait une liste de k chemin dans un graphe de taille n
def trafic (k,n):
    res=[]
    for i in range (k):
        a=0
        b=0
        while a==b:
            a=r.randint(0,n-1)
            b=r.randint(0,n-1)

        res.append([a,b])
    return res


#découpe un chemin en parcours neud a neud sous forme de liste de couple, example abcd devient ab,bc,cd
def decoupe (chemin):
    res = []
    n=len(chemin)
    for i in range (n-1):
        if chemin[i]<chemin[i+1]:
            res.append([chemin[i],chemin[i+1]])
        else:
            res.append([chemin[i+1],chemin[i]])

    return res


#transforme les liste de liste de liste en liste de liste
def flatten (l):
    res=[]
    n=len (l)
    for i in range (n):
        for j in range (len(l[i])):
            res.append (l[i][j])
    return (res)


#compte le nombre de longueurs d'onde qui passe dans chaque dans chaques fibres
def compte (l):
    res=[]
    n=len(l)
    for i in range (n):
        dejacompte =False
        for j in range (len(res)):
            if l[i]==res[j][1] and not dejacompte:
                res[j][0]=res[j][0]+1
                dejacompte=True
        if not dejacompte:
            res.append([1,l[i]])
    return res


graphetest= [[0.0, 0, 0, 0, 0, 0, 0, 0, 102.39140588936164, 0, 0, 0, 0, 143.8923208513922, 0, 0, 0, 0, 0, 0],[0, 0.0, 0, 116.06894502837527, 0, 0, 0, 0, 0, 0, 0, 187.09623192357455, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0.0, 0, 110.3177229641729, 0, 0, 0, 0, 0, 0, 0, 0, 207.99278833651903, 0, 0, 0, 0, 0, 0], [0, 116.06894502837527, 0, 0.0, 0, 0, 0, 0, 0, 0, 312.8338217009152, 142.00352108310554, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 110.3177229641729, 0, 0.0, 182.21415971323415, 251.03187048659777, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 182.21415971323415, 0.0, 265.75364531836624, 0, 0, 0, 392.3633520093333, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 251.03187048659777, 265.75364531836624, 0.0, 0, 0, 0, 127.09838708654017, 290.5580836941213, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 357.4758733117523, 241.51397475094478, 158.90248582070703, 0, 0, 0, 0, 0, 335.5964838909967, 0], [102.39140588936164, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 125.7179382586272, 0, 0, 139.74262055650738, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 115.52056094046635, 0, 0, 136.85028315644803, 0, 0, 0, 0], [0, 0, 0, 312.8338217009152, 0, 392.3633520093333, 127.09838708654017, 357.4758733117523, 0, 0, 0.0, 182.47739586041882, 0, 0, 0, 0, 0, 0, 0, 0], [0, 187.09623192357455, 0, 142.00352108310554, 0, 0, 290.5580836941213, 241.51397475094478, 0, 0, 182.47739586041882, 0.0, 395.08100435227203, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 158.90248582070703, 0, 115.52056094046635, 0, 395.08100435227203, 0.0, 0, 0, 0, 0, 270.2480342204176, 0, 134.6291201783626], [143.8923208513922, 0, 207.99278833651903, 0, 0, 0, 0, 0, 125.7179382586272, 0, 0, 0, 0, 0.0, 148.92951352905172, 0, 0, 0, 161.40012391568973, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 148.92951352905172, 0.0, 0, 157.20368952413298, 240.6595105122588, 135.83077707206124, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 136.85028315644803, 0, 0, 0, 0, 0, 0.0, 0, 0, 288.36088500349695, 139.84276885130672], [0, 0, 0, 0, 0, 0, 0, 0, 139.74262055650738, 0, 0, 0, 0, 0, 157.20368952413298, 0, 0.0, 0, 286.9233347080715, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 270.2480342204176, 0, 240.6595105122588, 0, 0, 0.0, 211.6341182323871, 283.0282671395209], [0, 0, 0, 0, 0, 0, 0, 335.5964838909967, 0, 0, 0, 0, 0, 161.40012391568973, 135.83077707206124, 288.36088500349695, 286.9233347080715, 211.6341182323871, 0.0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 134.6291201783626, 0, 0, 139.84276885130672, 0, 283.0282671395209, 0, 0.0]]


traftest =[[19, 12], [2, 4], [9, 2], [10, 8], [15, 2], [11, 0], [1, 2], [11, 2], [10, 17], [7, 5], [19, 12], [13, 8], [0, 7], [11, 12], [7, 10], [10, 11], [11, 10], [11, 9], [15, 8], [9, 1], [4, 14], [9, 12], [3, 17], [11, 7], [9, 13], [15, 13], [7, 16], [18, 19], [5, 18], [5, 11], [17, 18], [14, 4], [19, 19], [10, 15], [9, 10], [17, 3], [11, 19], [18, 9], [5, 12], [4, 13], [18, 4], [6, 15], [15, 5], [17, 14], [5, 14], [0, 9], [14, 0], [11, 17], [18, 8], [19, 11], [7, 10], [18, 5], [0, 15], [9, 5], [5, 16], [2, 8], [1, 10], [4, 7], [16, 6], [5, 13]]


#applique la methode de Barony Bayvel
def BaronyBayvel (graphe,limite,traf):
    n=len (traf)
    chemins=[]
    g=copy.deepcopy (graphe)
    for k in range (n):
        chemins.append (decoupe(plus_court_chemin(g,traf[k][0],traf[k][1])))
        densite=compte(flatten(chemins))
        for i in range (len(densite)):
            if densite[i][0]>=limite:
                g[densite[i][1][0]][densite[i][1][1]]=0
                g[densite[i][1][1]][densite[i][1][0]]=0
    return chemins



graphetest2=[[0.0, 0, 0, 0, 0, 0, 0, 0, 102.39140588936164, 0, 0, 0, 0, 143.8923208513922, 0, 0, 0, 0, 0, 0], [0, 0.0, 0, 116.06894502837527, 0, 0, 0, 0, 0, 0, 0, 187.09623192357455, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 116.06894502837527, 0, 0.0, 0, 0, 0, 0, 0, 0, 312.8338217009152, 142.00352108310554, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0.0, 182.21415971323415, 251.03187048659777, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 182.21415971323415, 0.0, 265.75364531836624, 0, 0, 0, 392.3633520093333, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 251.03187048659777, 265.75364531836624, 0.0, 0, 0, 0, 127.09838708654017, 290.5580836941213, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 357.4758733117523, 241.51397475094478, 158.90248582070703, 0, 0, 0, 0, 0, 335.5964838909967, 0], [102.39140588936164, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 125.7179382586272, 0, 0, 139.74262055650738, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 115.52056094046635, 0, 0, 136.85028315644803, 0, 0, 0, 0], [0, 0, 0, 312.8338217009152, 0, 392.3633520093333, 127.09838708654017, 357.4758733117523, 0, 0, 0.0, 182.47739586041882, 0, 0, 0, 0, 0, 0, 0, 0], [0, 187.09623192357455, 0, 142.00352108310554, 0, 0, 290.5580836941213, 241.51397475094478, 0, 0, 182.47739586041882, 0.0, 395.08100435227203, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 158.90248582070703, 0, 115.52056094046635, 0, 395.08100435227203, 0.0, 0, 0, 0, 0, 270.2480342204176, 0, 134.6291201783626], [143.8923208513922, 0, 0, 0, 0, 0, 0, 0, 125.7179382586272, 0, 0, 0, 0, 0.0, 148.92951352905172, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 148.92951352905172, 0.0, 0, 157.20368952413298, 240.6595105122588, 135.83077707206124, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 136.85028315644803, 0, 0, 0, 0, 0, 0.0, 0, 0, 288.36088500349695, 139.84276885130672], [0, 0, 0, 0, 0, 0, 0, 0, 139.74262055650738, 0, 0, 0, 0, 0, 157.20368952413298, 0, 0.0, 0, 286.9233347080715, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 270.2480342204176, 0, 240.6595105122588, 0, 0, 0.0, 211.6341182323871, 283.0282671395209], [0, 0, 0, 0, 0, 0, 0, 335.5964838909967, 0, 0, 0, 0, 0, 0, 135.83077707206124, 288.36088500349695, 286.9233347080715, 211.6341182323871, 0.0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 134.6291201783626, 0, 0, 139.84276885130672, 0, 283.0282671395209, 0, 0.0]]



resultat= [[[12, 19]], [[2, 4]], [[9, 15], [15, 18], [13, 18], [2, 13]], [[6, 10], [4, 6], [2, 4], [2, 13], [8, 13]], [[15, 18], [13, 18], [2, 13]], [[7, 11], [7, 18], [13, 18], [0, 13]], [[1, 11], [6, 11], [4, 6], [2, 4]], [[6, 11], [4, 6], [2, 4]], [[7, 10], [7, 12], [12, 17]], [[7, 10], [5, 10]], [[12, 19]], [[8, 13]], [[0, 13], [13, 18], [7, 18]], [[11, 12]], [[7, 10]], [[10, 11]], [[10, 11]], [[11, 12], [9, 12]], [[15, 18], [13, 18], [8, 13]], [[9, 12], [11, 12], [1, 11]], [[2, 4], [2, 13], [13, 14]], [[9, 12]], [[3, 11], [11, 12], [12, 17]], [[7, 11]], [[9, 15], [15, 18], [13, 18]], [[15, 18], [13, 18]], [[7, 18], [16, 18]], [[15, 18], [15, 19]], [[4, 5], [2, 4], [2, 13], [13, 18]], [[5, 6], [6, 11]], [[17, 18]], [[13, 14], [2, 13], [2, 4]], [], [[7, 10], [7, 12], [9, 12], [9, 15]], [[9, 12], [7, 12], [7, 10]], [[12, 17], [11, 12], [3, 11]], [[11, 12], [12, 19]], [[15, 18], [9, 15]], [[5, 10], [7, 10], [7, 12]], [[2, 4], [2, 13]], [[13, 18], [2, 13], [2, 4]], [[6, 10], [7, 10], [7, 12], [9, 12], [9, 15]], [[15, 18], [13, 18], [2, 13], [2, 4], [4, 5]], [[14, 17]], [[4, 5], [2, 4], [2, 13], [13, 14]], [[0, 13], [13, 18], [15, 18], [9, 15]], [[13, 14], [0, 13]], [[11, 12], [12, 17]], [[13, 18], [8, 13]], [[12, 19], [11, 12]], [[7, 10]], [[13, 18], [2, 13], [2, 4], [4, 5]], [[0, 13], [13, 18], [15, 18]], [[9, 12], [7, 12], [7, 10], [5, 10]], [[4, 5], [2, 4], [2, 13], [8, 13], [8, 16]], [[2, 13], [8, 13]], [[1, 11], [10, 11]], [[4, 6], [6, 10], [7, 10]], [[8, 16], [8, 13], [2, 13], [2, 4], [4, 6]], [[4, 5], [2, 4], [2, 13]]]







#initialise l'assignement de longeur d'onde
def InitAssigneLO (l):
    l=flatten(l)
    res=[]
    n=len(l)
    for i in range (n):
        dejacompte =False
        for j in range (len(res)):
            if l[i]==res[j][1] and not dejacompte:
                dejacompte=True
        if not dejacompte:
            res.append([[],l[i]])
    return res


#verifie si un élément est dans une liste
def estdedans (l,e):
    n=len (l)
    bool=False
    for i in range (n):
        if l[i]==e:
            bool=True
    return bool


#trouve la position d'un élement dans une liste
def indice (l,e):
    for k in range (len (l)):
        if l[k]==e:
            return k


#fonction qui simplifi une liste pour facilité l'assignement de longueurs d'onde
def simplifi (l,i):
    res=[]
    for k in range (len(l)):
        res.append(l[k][i])
    return res


#algorithme d'assignement de longueurs d'ondes
def AssigneLO (l):
    res=[]
    dejaassigne=InitAssigneLO (l)
    indices=simplifi (dejaassigne,1)
    n=len (l)
    for i in range (n):
        m=len(l[i])
        lambd=0
        k=0
        while k<m:
            if estdedans(dejaassigne[indice(indices,l[i][k])][0],lambd):
                lambd=lambd+1
                k=0
            else :
                k=k+1
        for j in range (m):
            dejaassigne[indice(indices,l[i][j])][0].append(lambd)
        res.append([lambd,l[i]])
    return res



#nombres de longueurs d'onde utilisées
def nombreLO (l):
    aux=[]
    n=len(l)
    for i in range (n):
        if not estdedans (aux,l[i]):
            aux.append(l[i])
    res=len(aux)
    return (res)






graphetipe=[[0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 135.79396157414365, 0, 0, 0, 0, 0, 0, 0, 0, 0, 154.20765220960988, 0, 0, 0, 0, 0, 0], [0, 0.0, 0, 0, 134.3726162579266, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 141.98943622678414, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 152.27934856703322, 0, 0, 0, 0, 0, 0, 0, 0, 0, 185.64751546950473, 0, 0, 0, 0], [0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 218.00917411888886, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 129.9576854210631], [0, 134.3726162579266, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 201.1889659002203, 0, 0, 0, 0, 0, 0, 146.102703602637, 0], [0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 130.36103712382777, 0, 141.12760183606892, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 121.8031198286809, 0, 0, 0, 0, 0, 0, 186.59314028120113, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 147.00340132119393, 0, 0, 0, 0, 0, 121.10326172320876, 0, 0, 0, 0, 0, 0, 0, 146.23952953972466, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 148.32734070291963, 0, 0, 0, 0, 168.4339633209407, 0, 0, 0, 0, 263.5773131360133, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 151.38031576133008, 0, 162.8158468945821, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140.80127840328723, 223.0807028857494, 0], [0, 0, 0, 0, 0, 0, 121.8031198286809, 147.00340132119393, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 167.7647161950331, 0, 0, 0, 0, 0, 221.0701246211256, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 244.78970566590417, 0, 140.1606221447379, 0, 0, 0, 0, 0, 0, 187.13097017864254, 0, 0, 0], [135.79396157414365, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 125.80143083447024, 0, 0, 0, 0, 0, 193.8762491900439, 0, 0, 314.6966793596653, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 123.0690862889621, 0, 0, 0, 0, 0, 172.18594600024707, 0, 0, 0, 0, 0, 0], [0, 0, 152.27934856703322, 0, 0, 0, 0, 0, 148.32734070291963, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 138.03260484392808, 0, 0, 0, 0, 305.00491799313664, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 133.3641631023867, 0, 241.3503677229434], [0, 0, 0, 0, 0, 0, 0, 121.10326172320876, 0, 0, 0, 0, 244.78970566590417, 125.80143083447024, 123.0690862889621, 0, 0, 0.0, 0, 0, 0, 0, 0, 269.462427807663, 0, 0, 0, 0, 0, 0], [0, 0, 0, 218.00917411888886, 0, 0, 186.59314028120113, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 181.4717608885746, 0, 0, 0, 0, 219.65882636488797, 0, 0, 196.4001018329675, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 167.7647161950331, 140.1606221447379, 0, 0, 0, 0, 0, 181.4717608885746, 0.0, 0, 0, 0, 0, 0, 0, 0, 0, 278.4690287985362, 0], [0, 0, 0, 0, 0, 0, 0, 0, 168.4339633209407, 0, 0, 0, 0, 0, 0, 138.03260484392808, 0, 0, 0, 0, 0.0, 0, 171.71196813268432, 0, 288.1700886629284, 0, 0, 0, 0, 0], [0, 141.98943622678414, 0, 0, 201.1889659002203, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0, 0, 0, 317.9701243827791, 0], [0, 0, 0, 0, 0, 130.36103712382777, 0, 0, 0, 151.38031576133008, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 171.71196813268432, 0, 0.0, 0, 131.24404748406687, 0, 0, 0, 0, 0], [154.20765220960988, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 193.8762491900439, 172.18594600024707, 0, 0, 269.462427807663, 0, 0, 0, 0, 0, 0.0, 0, 0, 143.42245291445826, 0, 0, 0], [0, 0, 0, 0, 0, 141.12760183606892, 0, 0, 0, 162.8158468945821, 0, 0, 0, 0, 0, 0, 0, 0, 219.65882636488797, 0, 288.1700886629284, 0, 131.24404748406687, 0, 0.0, 0, 0, 0, 0, 143.8923208513922], [0, 0, 185.64751546950473, 0, 0, 0, 0, 146.23952953972466, 263.5773131360133, 0, 0, 221.0701246211256, 0, 0, 0, 305.00491799313664, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 187.13097017864254, 314.6966793596653, 0, 0, 0, 0, 0, 0, 0, 0, 0, 143.42245291445826, 0, 0, 0.0, 0, 153.3101431738944, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 140.80127840328723, 0, 0, 0, 0, 0, 133.3641631023867, 0, 196.4001018329675, 0, 0, 0, 0, 0, 0, 0, 0, 0.0, 0, 0], [0, 0, 0, 0, 146.102703602637, 0, 0, 0, 0, 0, 223.0807028857494, 0, 0, 0, 0, 0, 0, 0, 0, 278.4690287985362, 0, 317.9701243827791, 0, 0, 0, 0, 153.3101431738944, 0, 0.0, 0], [0, 0, 0, 129.9576854210631, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 241.3503677229434, 0, 0, 0, 0, 0, 0, 0, 143.8923208513922, 0, 0, 0, 0, 0.0]]

trafictipe=[[12, 6], [19, 22], [18, 9], [16, 2], [4, 27], [13, 5], [19, 8], [10, 28], [13, 17], [25, 4], [26, 28], [16, 11], [13, 23], [27, 8], [6, 7], [13, 22], [17, 23], [23, 25], [3, 19], [19, 16], [18, 4], [10, 11], [11, 19], [5, 18], [22, 13], [18, 22], [16, 24], [0, 16], [10, 21], [14, 6], [28, 1], [19, 12], [13, 14], [17, 12], [20, 3], [27, 22], [24, 27], [13, 26], [0, 5], [25, 14], [13, 26], [7, 10], [9, 27], [22, 21], [29, 27], [2, 7], [6, 7], [28, 4], [28, 5], [13, 4], [9, 18], [25, 5], [17, 9], [1, 13], [3, 17], [27, 25], [6, 23], [19, 20], [19, 25], [1, 11], [3, 0], [17, 20], [21, 11], [2, 7], [26, 18], [25, 12], [14, 11], [1, 13], [22, 11], [0, 10], [3, 7], [18, 15], [22, 7], [15, 26], [16, 25], [17, 29], [21, 16], [12, 17], [8, 11], [26, 17], [1, 29], [9, 12], [18, 0], [4, 15], [21, 10], [21, 2], [2, 23], [2, 13], [0, 24], [21, 13], [5, 17], [16, 6], [6, 7], [3, 23], [18, 21], [19, 4], [5, 9], [4, 24], [16, 11], [10, 19]]



resultattipe=[[[12, 19], [11, 19], [6, 11]], [[18, 19], [18, 24], [22, 24]], [[18, 24], [9, 24]], [[16, 29], [24, 29], [20, 24], [15, 20], [2, 15]], [[4, 28], [10, 28], [10, 27]], [[13, 17], [12, 17], [12, 19], [18, 19], [18, 24], [5, 24]], [[11, 19], [11, 25], [8, 25]], [[10, 28]], [[13, 17]], [[11, 25], [11, 19], [19, 28], [4, 28]], [[26, 28]], [[16, 27], [18, 27], [6, 18], [6, 11]], [[13, 23]], [[18, 27], [18, 24], [20, 24], [8, 20]], [[6, 11], [7, 11]], [[13, 17], [7, 17], [7, 25], [8, 25], [8, 20], [20, 22]], [[17, 23]], [[17, 23], [7, 17], [7, 25]], [[3, 18], [18, 19]], [[18, 19], [18, 27], [16, 27]], [[18, 19], [19, 28], [4, 28]], [[10, 27], [18, 27], [6, 18], [6, 11]], [[11, 19]], [[5, 24], [18, 24]], [[20, 22], [8, 20], [8, 25], [7, 25], [7, 17], [13, 17]], [[18, 24], [22, 24]], [[16, 29], [24, 29]], [[0, 23], [23, 26], [26, 28], [10, 28], [10, 27], [16, 27]], [[10, 28], [21, 28]], [[14, 17], [7, 17], [7, 11], [6, 11]], [[4, 28], [1, 4]], [[12, 19]], [[13, 17], [14, 17]], [[12, 17]], [[20, 24], [24, 29], [3, 29]], [[18, 27], [18, 24], [22, 24]], [[18, 24], [18, 27]], [[13, 26]], [[0, 23], [23, 26], [12, 26], [12, 19], [18, 19], [18, 24], [5, 24]], [[7, 25], [7, 17], [14, 17]], [[13, 26]], [[7, 11], [6, 11], [6, 18], [18, 27], [10, 27]], [[9, 24], [18, 24], [18, 27]], [[22, 24], [18, 24], [18, 19], [19, 28], [21, 28]], [[16, 29], [16, 27]], [[2, 25], [7, 25]], [[6, 11], [7, 11]], [[4, 28]], [[19, 28], [18, 19], [18, 24], [5, 24]], [[13, 26], [26, 28], [4, 28]], [[9, 24], [18, 24]], [[8, 25], [8, 20], [20, 22], [5, 22]], [[12, 17], [12, 19], [18, 19], [18, 24], [9, 24]], [[1, 4], [4, 28], [26, 28], [13, 26]], [[3, 18], [18, 19], [12, 19], [12, 17]], [[18, 27], [6, 18], [6, 11], [11, 25]], [[6, 11], [7, 11], [7, 17], [17, 23]], [[11, 19], [11, 25], [8, 25], [8, 20]], [[11, 19], [11, 25]], [[1, 4], [4, 28], [19, 28], [11, 19]], [[3, 18], [18, 19], [12, 19], [12, 26], [23, 26], [0, 23]], [[7, 17], [7, 25], [8, 25], [8, 20]], [[21, 28], [19, 28], [11, 19]], [[2, 25], [7, 25]], [[12, 26], [12, 19], [18, 19]], [[7, 25], [7, 17], [12, 17]], [[14, 17], [7, 17], [7, 11]], [[1, 4], [4, 28], [26, 28], [13, 26]], [[20, 22], [8, 20], [8, 25], [11, 25]], [[0, 23], [23, 26], [26, 28], [10, 28]], [[3, 18], [6, 18], [6, 11], [7, 11]], [[6, 18], [6, 11], [11, 25], [15, 25]], [[20, 22], [8, 20], [8, 25], [7, 25]], [[15, 25], [7, 25], [7, 17], [17, 23], [23, 26]], [[16, 27], [18, 27], [6, 18], [6, 11], [11, 25]], [[12, 17], [12, 19], [18, 19], [3, 18], [3, 29]], [[21, 28], [10, 28], [10, 27], [16, 27]], [[12, 17]], [[8, 25], [11, 25]], [[23, 26], [17, 23]], [[1, 4], [4, 28], [10, 28], [10, 27], [16, 27], [16, 29]], [[9, 24], [24, 29], [3, 29], [3, 18], [18, 19], [12, 19]], [[6, 18], [6, 11], [7, 11], [7, 17], [13, 17], [0, 13]], [[4, 28], [19, 28], [11, 19], [11, 25], [15, 25]], [[21, 28], [10, 28]], [[21, 28], [19, 28], [11, 19], [11, 25], [2, 25]], [[2, 25], [7, 25], [7, 17], [17, 23]], [[2, 25], [7, 25], [7, 17], [13, 17]], [[0, 13], [13, 17], [7, 17], [7, 25], [8, 25], [8, 20], [20, 24]], [[21, 28], [26, 28], [13, 26]], [[5, 24], [24, 29], [3, 29], [3, 18], [6, 18], [6, 11], [11, 19], [12, 19], [12, 17]], [[16, 27], [18, 27], [6, 18]], [[6, 18], [18, 27], [10, 27], [10, 28], [19, 28], [11, 19], [7, 11]], [[3, 18], [18, 27], [10, 27], [10, 28], [26, 28], [23, 26]], [[18, 27], [10, 27], [10, 28], [21, 28]], [[19, 28], [4, 28]], [[5, 22], [9, 22]], [[4, 28], [10, 28], [10, 27], [16, 27], [16, 29], [24, 29]], [[16, 27], [10, 27], [10, 28], [19, 28], [11, 19]], [[10, 28], [19, 28]]]