# Une implémentation des files de priorité
def file_prio():
    return []

def est_vide(f):
    return f == file_prio()

def enfiler_ou_maj(f, x, nouvelle_prio):
    for i in range(len(f)):
        (y, autre_prio) = f[i]
        if x == y:
            if nouvelle_prio < autre_prio:
                f[i] = (x, nouvelle_prio)
            return
    # Si x n'était pas dans la file, on le rajoute
    f.append((x, nouvelle_prio))

def defiler(f):
    x_candidat = None
    prio_candidat = None
    for (x, p) in f:
        if prio_candidat == None or p < prio_candidat:
            x_candidat = x
            prio_candidat = p
    f.remove((x_candidat, prio_candidat))
    return (x_candidat, prio_candidat)

# Données du métro de Paris (en fin de fichier)

# Deux variables très longues sont définies en fin de fichier:
# + La variable graphe contient le dictionnaire de
#   listes d'adajacence des sommets du métro de Paris
# + La variable noms contient un dictionnaire
#   des noms des différents sommets

# Exercice 1
def dijkstra(depart, arrivee):
    pass # TODO

# Exercice 2
def stations_intermediaires(depart, arrivee):
    pass # TODO

# Données du métro de paris
graphe ={
    0: [(238, 41.0), (159, 46.0)],
    1: [(12, 36.0), (235, 44.0)],
    2: [(110, 69.0), (139, 50.0)],
    3: [(262, 33.0), (210, 41.0)],
    4: [(171, 43.0), (251, 35.0)],
    5: [(13, 67.0), (239, 54.0)],
    6: [(55, 56.0), (258, 46.0)],
    7: [(290, 39.0), (311, 79.0), (8, 120.0)],
    8: [(350, 38.0), (309, 58.0), (7, 120.0)],
    9: [(338, 28.0), (78, 62.0)],
    10: [(277, 42.0), (108, 36.0)],
    11: [(154, 32.0), (54, 41.0)],
    12: [(213, 42.0), (1, 36.0)],
    13: [(151, 57.0), (5, 67.0), (14, 120.0)],
    14: [(124, 46.0), (64, 28.0), (13, 120.0)],
    15: [(318, 37.0), (319, 73.0)],
    16: [(119, 98.0), (331, 62.0), (18, 120.0), (17, 120.0)],
    17: [(288, 89.0), (40, 41.0), (18, 120.0), (16, 120.0)],
    18: [(163, 32.0), (61, 56.0), (16, 120.0), (17, 120.0)],
    19: [(236, 31.0), (93, 33.0)],
    20: [(129, 48.0), (283, 38.0), (21, 120.0)],
    21: [(86, 46.0), (75, 51.0), (20, 120.0)],
    22: [(84, 39.0), (120, 81.0), (23, 120.0)],
    23: [(97, 35.0), (287, 57.0), (22, 120.0)],
    24: [(84, 51.0)],
    25: [(193, 42.0), (253, 35.0)],
    26: [(98, 31.0), (230, 64.0)],
    27: [(239, 64.0), (246, 59.0)],
    28: [(29, 79.0)],
    29: [(374, 46.0), (28, 79.0)],
    374: [(29, 46.0), (134, 53.0)],
    30: [(354, 24.0), (150, 44.0)],
    31: [(41, 28.0), (144, 36.0)],
    32: [(343, 54.0), (303, 41.0), (33, 120.0)],
    33: [(344, 52.0), (304, 41.0), (32, 120.0)],
    34: [(248, 36.0), (41, 57.0)],
    35: [(111, 34.0), (172, 40.0)],
    36: [(198, 105.0), (37, 39.0)],
    37: [(36, 39.0)],
    38: [(336, 35.0), (289, 38.0)],
    39: [(153, 38.0), (267, 46.0)],
    40: [(17, 41.0), (297, 37.0)],
    41: [(34, 57.0), (31, 28.0)],
    42: [(190, 42.0), (215, 35.0)],
    43: [(66, 41.0), (328, 57.0)],
    44: [(162, 54.0), (250, 64.0)],
    45: [(348, 43.0), (155, 35.0)],
    46: [(242, 63.0), (329, 46.0)],
    47: [(148, 46.0), (195, 41.0)],
    48: [(182, 66.0), (318, 60.0)],
    49: [(164, 42.0), (241, 40.0)],
    50: [(77, 54.0), (109, 62.0), (51, 120.0)],
    51: [(137, 62.0), (202, 69.0), (50, 120.0)],
    52: [(201, 20.0)],
    53: [(372, 47.0), (167, 33.0)],
    54: [(11, 41.0), (145, 51.0)],
    55: [(127, 60.0), (6, 56.0), (57, 120.0), (56, 120.0)],
    56: [(351, 59.0), (362, 75.0), (57, 120.0), (55, 120.0)],
    57: [(150, 35.0), (55, 120.0), (56, 120.0)],
    58: [(307, 31.0), (369, 31.0)],
    59: [(224, 72.0), (162, 53.0), (60, 120.0)],
    60: [(299, 63.0), (133, 45.0), (59, 120.0)],
    61: [(18, 56.0), (335, 28.0)],
    62: [(287, 53.0), (216, 48.0)],
    63: [(123, 44.0), (169, 57.0)],
    64: [(14, 28.0), (192, 57.0)],
    65: [(342, 41.0), (121, 57.0)],
    66: [(43, 41.0)],
    67: [(135, 87.0), (173, 51.0), (69, 120.0), (68, 120.0),
         (70, 120.0), (71, 120.0)],
    68: [(136, 85.0), (69, 120.0), (70, 120.0), (71, 120.0),
         (67, 120.0)],
    69: [(120, 287.0), (281, 131.0), (67, 120.0), (70, 120.0),
         (71, 120.0), (68, 120.0)],
    70: [(73, 45.0), (165, 66.0), (71, 120.0), (69, 120.0),
         (68, 120.0), (67, 120.0)],
    71: [(254, 73.0), (255, 37.0), (70, 120.0), (69, 120.0),
         (68, 120.0), (67, 120.0)],
    72: [(188, 52.0)],
    73: [(330, 46.0), (70, 45.0)],
    74: [(195, 44.0), (221, 52.0)],
    75: [(21, 51.0), (142, 93.0)],
    76: [(156, 59.0), (111, 30.0)],
    77: [(356, 57.0), (50, 54.0), (79, 120.0), (78, 120.0)],
    78: [(9, 62.0), (175, 41.0), (79, 120.0), (77, 120.0)],
    79: [(177, 41.0), (138, 71.0), (77, 120.0), (78, 120.0)],
    80: [(274, 41.0), (360, 49.0)],
    81: [(178, 43.0), (274, 43.0)],
    82: [(87, 32.0), (277, 47.0)],
    83: [(243, 36.0), (128, 49.0)],
    84: [(24, 51.0), (22, 39.0)],
    85: [(204, 47.0), (351, 46.0)],
    86: [(211, 37.0), (21, 46.0)],
    87: [(300, 43.0), (82, 32.0)],
    88: [(181, 44.0), (301, 47.0)],
    89: [(90, 29.0)],
    90: [(89, 29.0), (91, 26.0)],
    91: [(90, 26.0), (185, 27.0)],
    92: [(34, 37.0)],
    93: [(19, 33.0), (97, 45.0), (94, 120.0)],
    94: [(200, 27.0), (205, 39.0), (93, 120.0)],
    95: [(210, 48.0), (292, 37.0), (96, 120.0)],
    96: [(324, 52.0), (293, 42.0), (95, 120.0)],
    97: [(93, 45.0), (23, 35.0)],
    98: [(155, 69.0), (26, 31.0)],
    99: [(358, 31.0), (349, 54.0), (100, 120.0)],
    100: [(207, 113.0), (321, 59.0), (99, 120.0)],
    101: [(293, 43.0), (209, 36.0)],
    102: [(252, 35.0), (130, 37.0)],
    103: [(327, 44.0), (367, 30.0)],
    104: [(199, 62.0), (271, 40.0)],
    105: [(296, 42.0), (163, 47.0)],
    106: [(231, 29.0), (206, 36.0)],
    107: [(335, 49.0), (314, 49.0)],
    108: [(10, 36.0), (152, 29.0)],
    109: [(50, 62.0), (127, 59.0), (110, 120.0)],
    110: [(332, 37.0), (2, 69.0), (109, 120.0)],
    111: [(76, 30.0), (35, 34.0)],
    112: [(180, 71.0)],
    113: [(234, 36.0), (207, 47.0)],
    114: [(263, 72.0)],
    115: [(263, 39.0), (285, 70.0), (116, 120.0)],
    116: [(233, 50.0), (115, 120.0)],
    117: [(148, 59.0), (118, 120.0)],
    118: [(329, 60.0), (288, 30.0), (117, 120.0)],
    119: [(295, 41.0), (16, 98.0), (120, 120.0)],
    120: [(22, 81.0), (69, 287.0), (119, 120.0)],
    121: [(65, 57.0), (124, 67.0), (123, 120.0), (122, 120.0)],
    122: [(140, 103.0), (125, 59.0), (123, 120.0), (121, 120.0)],
    123: [(250, 51.0), (63, 44.0), (121, 120.0), (122, 120.0)],
    124: [(121, 67.0), (14, 46.0), (125, 120.0)],
    125: [(122, 59.0), (340, 107.0), (124, 120.0)],
    126: [(272, 37.0), (182, 42.0)],
    127: [(109, 59.0), (55, 60.0)],
    128: [(83, 49.0), (324, 42.0)],
    129: [(311, 49.0), (20, 48.0)],
    130: [(102, 37.0)],
    131: [(153, 72.0), (272, 63.0)],
    132: [(223, 68.0), (327, 40.0), (133, 120.0)],
    133: [(60, 45.0), (317, 49.0), (132, 120.0)],
    134: [(270, 47.0), (374, 53.0)],
    135: [(331, 65.0), (67, 87.0), (136, 120.0)],
    136: [(68, 85.0), (290, 73.0), (135, 120.0)],
    137: [(359, 54.0), (51, 62.0), (138, 120.0)],
    138: [(79, 71.0), (158, 57.0), (137, 120.0)],
    139: [(2, 50.0), (355, 46.0)],
    140: [(313, 47.0), (122, 103.0)],
    141: [(291, 37.0), (197, 49.0)],
    142: [(75, 93.0), (339, 27.0), (144, 120.0), (143, 120.0)],
    143: [(340, 29.0), (160, 44.0), (144, 120.0), (142, 120.0)],
    144: [(31, 36.0), (170, 46.0), (142, 120.0), (143, 120.0)],
    145: [(54, 51.0), (373, 55.0)],
    146: [(283, 33.0), (247, 50.0)],
    147: [(159, 44.0), (191, 49.0)],
    148: [(117, 59.0), (47, 46.0), (149, 120.0)],
    149: [(241, 57.0), (345, 79.0), (148, 120.0)],
    150: [(30, 44.0), (57, 35.0)],
    151: [(339, 93.0), (13, 57.0)],
    152: [(108, 29.0)],
    153: [(245, 64.0), (131, 72.0), (39, 38.0)],
    154: [(349, 33.0), (11, 32.0), (156, 120.0), (155, 120.0)],
    155: [(45, 35.0), (98, 69.0), (156, 120.0), (154, 120.0)],
    156: [(371, 46.0), (76, 59.0), (154, 120.0), (155, 120.0)],
    157: [(306, 36.0), (291, 49.0)],
    158: [(138, 57.0), (371, 66.0)],
    159: [(0, 46.0), (147, 44.0)],
    160: [(143, 44.0), (226, 40.0)],
    161: [(364, 28.0), (184, 39.0)],
    162: [(59, 53.0), (44, 54.0)],
    163: [(105, 47.0), (18, 32.0)],
    164: [(244, 60.0), (49, 42.0)],
    165: [(70, 66.0), (375, 33.0)],
    166: [(258, 38.0), (252, 37.0)],
    167: [(53, 33.0), (265, 31.0)],
    168: [(326, 49.0), (245, 28.0)],
    169: [(63, 57.0), (341, 54.0), (170, 120.0)],
    170: [(144, 46.0), (169, 120.0)],
    171: [(264, 49.0), (4, 43.0)],
    172: [(35, 40.0), (240, 35.0)],
    173: [(67, 51.0), (227, 34.0)],
    174: [(221, 31.0), (346, 72.0)],
    175: [(78, 41.0), (325, 144.0), (177, 120.0), (176, 120.0)],
    176: [(281, 71.0), (177, 120.0), (175, 120.0)],
    177: [(225, 88.0), (79, 41.0), (175, 120.0), (176, 120.0)],
    178: [(81, 43.0)],
    179: [(237, 37.0)],
    180: [(267, 91.0), (112, 71.0)],
    181: [(88, 44.0)],
    182: [(126, 42.0), (48, 66.0)],
    183: [(278, 51.0)],
    184: [(260, 31.0), (161, 39.0), (352, 36.0)],
    185: [(91, 27.0), (186, 26.0)],
    186: [(185, 26.0), (372, 33.0)],
    187: [(188, 34.0), (273, 46.0)],
    188: [(72, 52.0), (187, 34.0)],
    189: [(367, 49.0), (370, 35.0)],
    190: [(269, 27.0), (42, 42.0)],
    191: [(147, 49.0), (194, 67.0), (192, 120.0)],
    192: [(64, 57.0), (337, 36.0), (191, 120.0)],
    193: [(271, 38.0), (25, 42.0)],
    194: [(191, 67.0), (276, 67.0)],
    195: [(47, 41.0), (74, 44.0)],
    196: [(259, 47.0), (197, 120.0)],
    197: [(141, 49.0), (199, 28.0), (196, 120.0)],
    198: [(52, 42.0), (199, 120.0)],
    199: [(197, 28.0), (104, 62.0), (198, 120.0)],
    200: [(257, 51.0), (94, 27.0)],
    201: [(145, 46.0)],
    202: [(51, 69.0), (326, 112.0), (203, 120.0)],
    203: [(317, 53.0), (332, 40.0), (202, 120.0)],
    204: [(366, 51.0), (85, 47.0)],
    205: [(94, 39.0), (296, 38.0)],
    206: [(106, 36.0), (218, 45.0), (208, 120.0), (207, 120.0),
          (209, 120.0)],
    207: [(113, 47.0), (100, 113.0), (208, 120.0), (209, 120.0),
          (206, 120.0)],
    208: [(361, 42.0), (333, 48.0), (206, 120.0), (209, 120.0),
          (207, 120.0)],
    209: [(101, 36.0), (232, 54.0), (208, 120.0), (207, 120.0),
          (206, 120.0)],
    210: [(3, 41.0), (95, 48.0)],
    211: [(284, 49.0), (86, 37.0)],
    212: [(275, 86.0), (295, 64.0), (214, 120.0), (213, 120.0),
          (215, 120.0)],
    213: [(12, 42.0), (214, 120.0), (215, 120.0), (212, 120.0)],
    214: [(236, 42.0), (212, 120.0), (215, 120.0), (213, 120.0)],
    215: [(42, 35.0), (307, 60.0), (214, 120.0),
          (213, 120.0), (212, 120.0)],
    216: [(62, 48.0), (243, 55.0)],
    217: [(353, 29.0), (322, 37.0)],
    218: [(206, 45.0), (294, 38.0)],
    219: [(297, 50.0), (313, 81.0), (220, 120.0)],
    220: [(316, 35.0), (315, 80.0), (219, 120.0)],
    221: [(74, 52.0), (174, 31.0), (222, 120.0)],
    222: [(323, 42.0), (330, 31.0), (221, 120.0)],
    223: [(289, 43.0), (132, 68.0), (225, 120.0), (224, 120.0)],
    224: [(282, 80.0), (59, 72.0), (225, 120.0), (223, 120.0)],
    225: [(298, 75.0), (177, 88.0), (223, 120.0), (224, 120.0)],
    226: [(160, 40.0), (270, 39.0)],
    227: [(173, 34.0), (356, 38.0), (228, 120.0)],
    228: [(255, 53.0), (282, 49.0), (227, 120.0)],
    229: [(305, 43.0), (312, 64.0)],
    230: [(26, 64.0), (354, 62.0)],
    231: [(368, 40.0), (106, 29.0), (232, 120.0)],
    232: [(209, 54.0), (348, 46.0), (231, 120.0)],
    233: [(320, 33.0), (116, 50.0)],
    234: [(249, 38.0), (113, 36.0)],
    235: [(1, 44.0), (284, 44.0)],
    236: [(214, 42.0), (19, 31.0)],
    237: [(179, 37.0), (261, 37.0)],
    238: [(322, 27.0), (0, 41.0), (239, 120.0)],
    239: [(5, 54.0), (27, 64.0), (238, 120.0)],
    240: [(172, 35.0)],
    241: [(49, 40.0), (149, 57.0)],
    242: [(46, 63.0), (244, 120.0), (243, 120.0)],
    243: [(216, 55.0), (83, 36.0), (244, 120.0), (242, 120.0)],
    244: [(352, 37.0), (164, 60.0), (242, 120.0), (243, 120.0)],
    245: [(168, 28.0), (153, 64.0), (246, 120.0)],
    246: [(27, 59.0), (302, 37.0), (245, 120.0)],
    247: [(146, 50.0), (357, 23.0), (248, 120.0)],
    248: [(280, 57.0), (247, 120.0)],
    249: [(273, 35.0), (234, 38.0)],
    250: [(44, 64.0), (123, 51.0)],
    251: [(4, 35.0)],
    252: [(166, 37.0), (102, 35.0)],
    253: [(25, 35.0)],
    254: [(345, 75.0), (71, 73.0)],
    255: [(71, 37.0), (228, 53.0)],
    256: [(362, 37.0)],
    257: [(265, 26.0), (200, 51.0)],
    258: [(6, 46.0), (166, 38.0)],
    259: [(198, 47.0), (36, 84.0)],
    260: [(266, 37.0), (184, 31.0)],
    261: [(237, 37.0), (266, 46.0)],
    262: [(3, 33.0)],
    263: [(114, 72.0), (115, 39.0)],
    264: [(286, 41.0), (171, 49.0)],
    265: [(167, 31.0), (257, 26.0)],
    266: [(261, 46.0), (260, 37.0)],
    267: [(39, 46.0), (180, 91.0)],
    268: [(337, 39.0)],
    269: [(301, 35.0), (190, 27.0)],
    270: [(226, 39.0), (134, 47.0)],
    271: [(104, 40.0), (193, 38.0)],
    272: [(131, 63.0), (126, 37.0)],
    273: [(187, 46.0), (249, 35.0)],
    274: [(81, 43.0), (80, 41.0)],
    275: [(328, 41.0), (212, 86.0)],
    276: [(194, 67.0)],
    277: [(82, 47.0), (10, 42.0)],
    278: [(357, 59.0), (183, 51.0), (279, 120.0)],
    279: [(320, 37.0), (278, 120.0)],
    280: [(92, 43.0)],
    281: [(69, 131.0), (176, 71.0), (282, 120.0)],
    282: [(228, 49.0), (224, 80.0), (281, 120.0)],
    283: [(20, 38.0), (146, 33.0)],
    284: [(235, 44.0), (211, 49.0), (285, 120.0)],
    285: [(115, 70.0), (305, 61.0), (284, 120.0)],
    286: [(370, 35.0), (264, 41.0)],
    287: [(23, 57.0), (62, 53.0)],
    288: [(118, 30.0), (17, 89.0)],
    289: [(38, 38.0), (223, 43.0)],
    290: [(136, 73.0), (7, 39.0)],
    291: [(157, 49.0), (141, 37.0)],
    292: [(95, 37.0), (361, 38.0), (293, 120.0)],
    293: [(96, 42.0), (101, 43.0), (292, 120.0)],
    294: [(218, 38.0), (347, 46.0)],
    295: [(212, 64.0), (119, 41.0), (296, 120.0)],
    296: [(205, 38.0), (105, 42.0), (295, 120.0)],
    297: [(40, 37.0), (219, 50.0)],
    298: [(303, 46.0), (225, 75.0), (299, 120.0)],
    299: [(304, 48.0), (60, 63.0), (298, 120.0)],
    300: [(341, 46.0), (87, 43.0)],
    301: [(88, 47.0), (269, 35.0)],
    302: [(246, 37.0), (366, 53.0)],
    303: [(32, 41.0), (298, 46.0), (304, 120.0)],
    304: [(33, 41.0), (299, 48.0), (303, 120.0)],
    305: [(285, 61.0), (229, 43.0)],
    306: [(355, 33.0), (157, 36.0)],
    307: [(215, 60.0), (58, 31.0)],
    308: [(347, 29.0), (338, 33.0)],
    309: [(8, 58.0), (336, 65.0), (310, 120.0)],
    310: [(375, 28.0), (342, 67.0), (309, 120.0)],
    311: [(7, 79.0), (129, 49.0), (313, 120.0), (312, 120.0),
          (314, 120.0), (315, 120.0)],
    312: [(229, 64.0), (350, 37.0), (313, 120.0), (314, 120.0),
          (315, 120.0), (311, 120.0)],
    313: [(219, 81.0), (140, 47.0), (311, 120.0), (314, 120.0),
          (315, 120.0), (312, 120.0)],
    314: [(107, 49.0), (343, 98.0), (315, 120.0), (313, 120.0),
          (312, 120.0), (311, 120.0)],
    315: [(220, 80.0), (344, 107.0), (314, 120.0), (313, 120.0),
          (312, 120.0), (311, 120.0)],
    316: [(369, 27.0), (220, 35.0)],
    317: [(133, 49.0), (203, 53.0)],
    318: [(48, 60.0), (15, 37.0)],
    319: [(15, 73.0)],
    320: [(279, 37.0), (233, 33.0)],
    321: [(100, 59.0), (359, 23.0)],
    322: [(217, 37.0), (238, 27.0)],
    323: [(334, 47.0), (222, 42.0)],
    324: [(128, 42.0), (96, 52.0)],
    325: [(175, 144.0), (353, 69.0), (327, 120.0), (326, 120.0)],
    326: [(202, 112.0), (168, 49.0), (327, 120.0), (325, 120.0)],
    327: [(132, 40.0), (103, 44.0), (325, 120.0), (326, 120.0)],
    328: [(43, 57.0), (275, 41.0)],
    329: [(46, 46.0), (118, 60.0)],
    330: [(222, 31.0), (73, 46.0)],
    331: [(16, 62.0), (135, 65.0)],
    332: [(203, 40.0), (110, 37.0)],
    333: [(208, 48.0), (334, 32.0)],
    334: [(333, 32.0), (323, 47.0)],
    335: [(61, 28.0), (107, 49.0)],
    336: [(309, 65.0), (38, 35.0)],
    337: [(192, 36.0), (268, 39.0)],
    338: [(308, 33.0), (9, 28.0)],
    339: [(142, 27.0), (151, 93.0), (341, 120.0), (340, 120.0)],
    340: [(125, 107.0), (143, 29.0), (341, 120.0), (339, 120.0)],
    341: [(169, 54.0), (300, 46.0), (339, 120.0), (340, 120.0)],
    342: [(310, 67.0), (65, 41.0), (344, 120.0), (343, 120.0)],
    343: [(314, 98.0), (32, 54.0), (344, 120.0), (342, 120.0)],
    344: [(315, 107.0), (33, 52.0), (342, 120.0), (343, 120.0)],
    345: [(149, 79.0), (254, 75.0)],
    346: [(174, 72.0), (358, 33.0), (347, 120.0)],
    347: [(294, 46.0), (308, 29.0), (346, 120.0)],
    348: [(232, 46.0), (45, 43.0)],
    349: [(99, 54.0), (154, 33.0)],
    350: [(312, 37.0), (8, 38.0)],
    351: [(85, 46.0), (56, 59.0)],
    352: [(184, 36.0), (244, 37.0)],
    353: [(325, 69.0), (217, 29.0)],
    354: [(230, 62.0), (30, 24.0), (355, 120.0)],
    355: [(139, 46.0), (306, 33.0), (354, 120.0)],
    356: [(227, 38.0), (77, 57.0)],
    357: [(247, 23.0), (278, 59.0)],
    358: [(346, 33.0), (99, 31.0)],
    359: [(321, 23.0), (137, 54.0)],
    360: [(80, 49.0), (368, 47.0)],
    361: [(292, 38.0), (208, 42.0)],
    362: [(56, 75.0), (256, 37.0)],
    363: [(365, 28.0)],
    364: [(365, 28.0), (161, 28.0)],
    365: [(363, 28.0), (364, 28.0)],
    366: [(302, 53.0), (204, 51.0), (367, 120.0)],
    367: [(103, 30.0), (189, 49.0), (366, 120.0)],
    368: [(360, 47.0), (231, 40.0)],
    369: [(58, 31.0), (316, 27.0)],
    370: [(189, 35.0), (286, 35.0)],
    371: [(158, 66.0), (156, 46.0)],
    372: [(186, 33.0), (53, 47.0)],
    373: [(196, 37.0)],
    375: [(165, 33.0), (310, 28.0)]
}

noms = {
    0: 'Abbesses',
    1: 'Alexandre Dumas',
    2: 'Alma Marceau',
    3: 'Alésia',
    4: 'Anatole France',
    5: 'Anvers',
    6: 'Argentine',
    7: 'Arts et Métiers',
    8: 'Arts et Métiers',
    9: 'Assemblée Nationale',
    10: 'Aubervilliers-Pantin, Quatre Chemins',
    11: 'Avenue Émile Zola',
    12: 'Avron',
    13: 'Barbès Rochechouart',
    14: 'Barbès Rochechouart',
    15: 'Basilique de Saint-Denis',
    16: 'Bastille',
    17: 'Bastille',
    18: 'Bastille',
    19: 'Bel Air',
    20: 'Belleville',
    21: 'Belleville',
    22: 'Bercy',
    23: 'Bercy',
    24: 'Bibliothèque François Mitterand',
    25: 'Billancourt',
    26: 'Bir-Hakeim',
    27: 'Blanche',
    28: 'Bobigny, Pablo Picasso',
    29: 'Bobigny-Pantin, Raymond Queneau',
    30: 'Boissière',
    31: 'Bolivar',
    32: 'Bonne Nouvelle',
    33: 'Bonne Nouvelle',
    34: 'Botzaris',
    35: 'Boucicaut',
    36: 'Boulogne, Jean Jaurès',
    37: 'Boulogne, Pont de Saint-Cloud, Rond Point Rhin et Danube',
    38: 'Bourse',
    39: 'Brochant',
    40: 'Bréguet-Sabin',
    41: 'Buttes Chaumont',
    42: 'Buzenval',
    43: 'Bérault',
    44: 'Cadet',
    45: 'Cambronne',
    46: 'Campo-Formio',
    47: 'Cardinal Lemoine',
    48: 'Carrefour Pleyel',
    49: 'Censier Daubenton',
    50: 'Champs Élysées, Clémenceau',
    51: 'Champs Élysées, Clémenceau',
    52: 'Chardon Lagâche',
    53: 'Charenton-Écoles',
    54: 'Charles Michels',
    55: 'Charles de Gaulle, Étoile',
    56: 'Charles de Gaulle, Étoile',
    57: 'Charles de Gaulle, Étoile',
    58: 'Charonne',
    59: "Chaussée d'Antin, La Fayette",
    60: "Chaussée d'Antin, La Fayette",
    61: 'Chemin Vert',
    62: 'Chevaleret',
    63: 'Château Landon',
    64: 'Château Rouge',
    65: "Château d'Eau",
    66: 'Château de Vincennes',
    67: 'Châtelet',
    68: 'Châtelet',
    69: 'Châtelet',
    70: 'Châtelet',
    71: 'Châtelet',
    72: 'Châtillon-Montrouge',
    73: 'Cité',
    74: 'Cluny, La Sorbonne',
    75: 'Colonel Fabien',
    76: 'Commerce',
    77: 'Concorde',
    78: 'Concorde',
    79: 'Concorde',
    80: 'Convention',
    81: 'Corentin Celton',
    82: 'Corentin-Cariou',
    83: 'Corvisart',
    84: 'Cour Saint-Émilion',
    85: 'Courcelles',
    86: 'Couronnes',
    87: 'Crimée',
    88: 'Croix de Chavaux',
    89: 'Créteil-Préfecture',
    90: 'Créteil-Université',
    91: "Créteil-l'Echat, Hôpital Henri Mondor",
    92: 'Danube',
    93: 'Daumesnil',
    94: 'Daumesnil',
    95: 'Denfert Rochereau',
    96: 'Denfert Rochereau',
    97: 'Dugommier',
    98: 'Dupleix',
    99: 'Duroc',
    100: 'Duroc',
    101: 'Edgar Quinet',
    102: 'Esplanade de la Défense',
    103: 'Europe',
    104: 'Exelmans',
    105: 'Faidherbe-Chaligny',
    106: 'Falguière',
    107: 'Filles du Calvaire',
    108: "Fort d'Aubervilliers",
    109: 'Franklin D. Roosevelt',
    110: 'Franklin D. Roosevelt',
    111: 'Félix Faure',
    112: 'Gabriel Péri, Asnières-Gennevilliers',
    113: 'Gaité',
    114: 'Galliéni',
    115: 'Gambetta',
    116: 'Gambetta',
    117: "Gare d'Austerlitz",
    118: "Gare d'Austerlitz",
    119: 'Gare de Lyon',
    120: 'Gare de Lyon',
    121: "Gare de l'Est",
    122: "Gare de l'Est",
    123: "Gare de l'Est",
    124: 'Gare du Nord',
    125: 'Gare du Nord',
    126: 'Garibaldi',
    127: 'George V',
    128: 'Glacière',
    129: 'Goncourt',
    130: 'Grande Arche de la Défense',
    131: 'Guy Môquet',
    132: 'Havre Caumartin',
    133: 'Havre Caumartin',
    134: 'Hoche',
    135: 'Hôtel de Ville',
    136: 'Hôtel de Ville',
    137: 'Invalides',
    138: 'Invalides',
    139: 'Iéna',
    140: 'Jacques Bonsergent',
    141: 'Jasmin',
    142: 'Jaurès',
    143: 'Jaurès',
    144: 'Jaurès',
    145: 'Javel',
    146: 'Jourdain',
    147: 'Jules Joffrin',
    148: 'Jussieu',
    149: 'Jussieu',
    150: 'Kléber',
    151: 'La Chapelle',
    152: 'La Courneuve, 8 Mai 1945',
    153: 'La Fourche',
    154: 'La Motte Picquet, Grenelle',
    155: 'La Motte Picquet, Grenelle',
    156: 'La Motte Picquet, Grenelle',
    157: 'La Muette',
    158: 'La Tour-Maubourg',
    159: 'Lamarck Caulaincourt',
    160: 'Laumière',
    161: 'Le Kremlin-Bicêtre',
    162: 'Le Peletier',
    163: 'Ledru Rollin',
    164: 'Les Gobelins',
    165: 'Les Halles',
    166: 'Les Sablons',
    167: 'Liberté',
    168: 'Liège',
    169: 'Louis Blanc',
    170: 'Louis Blanc',
    171: 'Louise Michel',
    172: 'Lourmel',
    173: 'Louvre, Rivoli',
    174: 'Mabillon',
    175: 'Madeleine',
    176: 'Madeleine',
    177: 'Madeleine',
    178: "Mairie d'Issy",
    179: "Mairie d'Ivry",
    180: 'Mairie de Clichy',
    181: 'Mairie de Montreuil',
    182: 'Mairie de Saint-Ouen',
    183: 'Mairie des Lilas',
    184: 'Maison Blanche',
    185: 'Maisons-Alfort les Juilliottes',
    186: 'Maisons-Alfort, Stade',
    187: 'Malakoff-Plateau de Vanves',
    188: 'Malakoff-Rue Étienne Dolet',
    189: 'Malesherbes',
    190: 'Maraîchers',
    191: 'Marcadet Poissonniers',
    192: 'Marcadet Poissonniers',
    193: 'Marcel Sembat',
    194: 'Marx Dormoy',
    195: 'Maubert Mutualité',
    196: 'Michel Ange Auteuil',
    197: 'Michel Ange Auteuil',
    198: 'Michel Ange Molitor',
    199: 'Michel Ange Molitor',
    200: 'Michel Bizot',
    201: 'Mirabeau',
    202: 'Miromesnil',
    203: 'Miromesnil',
    204: 'Monceau',
    205: 'Montgallet',
    206: 'Montparnasse Bienvenue',
    207: 'Montparnasse Bienvenue',
    208: 'Montparnasse Bienvenue',
    209: 'Montparnasse Bienvenue',
    210: 'Mouton-Duvernet',
    211: 'Ménilmontant',
    212: 'Nation',
    213: 'Nation',
    214: 'Nation',
    215: 'Nation',
    216: 'Nationale',
    217: 'Notre Dame de Lorette',
    218: 'Notre-Dame-des-Champs',
    219: 'Oberkampf',
    220: 'Oberkampf',
    221: 'Odéon',
    222: 'Odéon',
    223: 'Opéra',
    224: 'Opéra',
    225: 'Opéra',
    226: 'Ourcq',
    227: 'Palais Royal, Musée du Louvre',
    228: 'Palais Royal, Musée du Louvre',
    229: 'Parmentier',
    230: 'Passy',
    231: 'Pasteur',
    232: 'Pasteur',
    233: 'Pelleport',
    234: 'Pernety',
    235: 'Philippe-Auguste',
    236: 'Picpus',
    237: 'Pierre Curie',
    238: 'Pigalle',
    239: 'Pigalle',
    240: 'Place Balard',
    241: 'Place Monge',
    242: "Place d'Italie",
    243: "Place d'Italie",
    244: "Place d'Italie",
    245: 'Place de Clichy',
    246: 'Place de Clichy',
    247: 'Place des Fêtes',
    248: 'Place des Fêtes',
    249: 'Plaisance',
    250: 'Poissonnière',
    251: 'Pont de Levallois, Bécon',
    252: 'Pont de Neuilly',
    253: 'Pont de Sèvres',
    254: 'Pont-Marie',
    255: 'Pont-Neuf',
    256: 'Porte Dauphine',
    257: 'Porte Dorée',
    258: 'Porte Maillot',
    259: "Porte d'Auteuil",
    260: "Porte d'Italie",
    261: "Porte d'Ivry",
    262: "Porte d'Orléans",
    263: 'Porte de Bagnolet',
    264: 'Porte de Champerret',
    265: 'Porte de Charenton',
    266: 'Porte de Choisy',
    267: 'Porte de Clichy',
    268: 'Porte de Clignancourt',
    269: 'Porte de Montreuil',
    270: 'Porte de Pantin',
    271: 'Porte de Saint-Cloud',
    272: 'Porte de Saint-Ouen',
    273: 'Porte de Vanves',
    274: 'Porte de Versailles',
    275: 'Porte de Vincennes',
    276: 'Porte de la Chapelle',
    277: 'Porte de la Villette',
    278: 'Porte des Lilas',
    279: 'Porte des Lilas',
    280: 'Pré-Saint-Gervais',
    281: 'Pyramides',
    282: 'Pyramides',
    283: 'Pyrénées',
    284: 'Père Lachaise',
    285: 'Père Lachaise',
    286: 'Péreire',
    287: 'Quai de la Gare',
    288: 'Quai de la Rapée',
    289: 'Quatre Septembre',
    290: 'Rambuteau',
    291: 'Ranelagh',
    292: 'Raspail',
    293: 'Raspail',
    294: 'Rennes',
    295: 'Reuilly Diderot',
    296: 'Reuilly Diderot',
    297: 'Richard Lenoir',
    298: 'Richelieu Drouot',
    299: 'Richelieu Drouot',
    300: 'Riquet',
    301: 'Robespierre',
    302: 'Rome',
    303: 'Rue Montmartre, Grands Boulevards',
    304: 'Rue Montmartre, Grands Boulevards',
    305: 'Rue Saint-Maur',
    306: 'Rue de la Pompe',
    307: 'Rue des Boulets',
    308: 'Rue du Bac',
    309: 'Réaumur Sébastopol',
    310: 'Réaumur Sébastopol',
    311: 'République',
    312: 'République',
    313: 'République',
    314: 'République',
    315: 'République',
    316: 'Saint-Ambroise',
    317: 'Saint-Augustin',
    318: 'Saint-Denis-Porte de Paris',
    319: 'Saint-Denis-Université',
    320: 'Saint-Fargeau',
    321: 'Saint-Francois Xavier',
    322: 'Saint-Georges',
    323: 'Saint-Germain-des-Prés',
    324: 'Saint-Jacques',
    325: 'Saint-Lazare',
    326: 'Saint-Lazare',
    327: 'Saint-Lazare',
    328: 'Saint-Mandé, Tourelle',
    329: 'Saint-Marcel',
    330: 'Saint-Michel',
    331: 'Saint-Paul, Le Marais',
    332: 'Saint-Philippe du Roule',
    333: 'Saint-Placide',
    334: 'Saint-Sulpice',
    335: 'Saint-Sébastien-Froissart',
    336: 'Sentier',
    337: 'Simplon',
    338: 'Solférino',
    339: 'Stalingrad',
    340: 'Stalingrad',
    341: 'Stalingrad',
    342: 'Strasbourg Saint-Denis',
    343: 'Strasbourg Saint-Denis',
    344: 'Strasbourg Saint-Denis',
    345: 'Sully Morland',
    346: 'Sèvres Babylone',
    347: 'Sèvres Babylone',
    348: 'Sèvres Lecourbe',
    349: 'Ségur',
    350: 'Temple',
    351: 'Ternes',
    352: 'Tolbiac',
    353: "Trinité d'Estienne d'Orves",
    354: 'Trocadéro',
    355: 'Trocadéro',
    356: 'Tuileries',
    357: 'Télégraphe',
    358: 'Vaneau',
    359: 'Varenne',
    360: 'Vaugirard',
    361: 'Vavin',
    362: 'Victor Hugo',
    363: 'Villejuif, Louis Aragon',
    364: 'Villejuif, Léo Lagrange',
    365: 'Villejuif, P. Vaillant Couturier',
    366: 'Villiers',
    367: 'Villiers',
    368: 'Volontaires',
    369: 'Voltaire',
    370: 'Wagram',
    371: 'École Militaire',
    372: 'École Vétérinaire de Maisons-Alfort',
    373: "Église d'Auteuil",
    374: 'Église de Pantin',
    375: 'Étienne Marcel'}