Герой Аркадий находится на узкой полоске земли, разделенной на *n* зон, пронумерованных от 1 до *n*. Из *i*-й зоны можно пройти лишь в (*i* - 1)-ю зону и в (*i* + 1)-ю зону, если они существуют. При этом между каждой парой соседних зон находятся пограничные врата, которые могут быть разных цветов, цвет врат между *i*-й и (*i* + 1)-й зоной равен *g*<sub class="lower-index">*i*</sub>.

Аркадий может пройти пограничные врата некоторого цвета, только если он перед этим побывал в одном из шатров хранителей ключей этого цвета и взял ключ. В каждой зоне находится ровно один шатер хранителя ключей некоторого цвета, цвет шатра в *i*-й зоне равен *k*<sub class="lower-index">*i*</sub>. После посещения шатра определенного цвета Аркадий может неограниченное число раз проходить через любые врата этого цвета.

На проход через одни врата Аркадий тратит один ход, на посещение шатра и другие перемещения ходы не требуются. За какое минимальное число ходов Аркадий может попасть из зоны *a* в зону *b*, если изначально у него нет никаких ключей?
Первая строка содержит три целых числа *n*, *a*, *b* (2 ≤ *n* ≤ 100 000, 1 ≤ *a*, *b* ≤ *n*, *a* ≠ *b*) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит *n* - 1 целое число *g*<sub class="lower-index">1</sub>, *g*<sub class="lower-index">2</sub>, ..., *g*<sub class="lower-index">*n* - 1</sub> (1 ≤ *g*<sub class="lower-index">*i*</sub> ≤ 100 000), где *g*<sub class="lower-index">*i*</sub> означает цвет пограничных врат между зонами *i* и *i* + 1.

Третья строка содержит *n* целых чисел *k*<sub class="lower-index">1</sub>, *k*<sub class="lower-index">2</sub>, ..., *k*<sub class="lower-index">*n*</sub> (1 ≤ *k*<sub class="lower-index">*i*</sub> ≤ 100 000), где *k*<sub class="lower-index">*i*</sub> означает цвет шатра хранителя ключей в *i*-й зоне.
В первом примере, чтобы попасть из зоны 4 в зону 1, Аркадию нужно сначала взять ключ цвета 1, пройти в зону 3, там взять ключ цвета 2 и пройти обратно в зону 4 и затем в зону 5, взять там ключ цвета 3 и дойти до зоны 1 за четыре хода.

Во втором примере Аркадий может дойти лишь до четвертой зоны, так как шатров хранителей ключей цвета 1 нет совсем.
def dijkstra_shortest_path(graph, start, p={}, u=[], d={}):
    if len(p) == 0: p[start] = 4 # инициализация начального пути
    # print "start V: %d, " % (start)
    for x in graph[start]:
        if (x not in u and x != start):
            if (x not in p.keys() or (graph[start][x] + p[start]) < p[x]):
                p[x] = graph[start][x] + p[start]

    u.append(start)

    min_v = 0
    min_x = None
    for x in p:
        # print "x: %d, p[x]: %d, mv %d" % (x, p[x], min_v)
        if (p[x] < min_v or min_v == 0) and x not in u:
                min_x = x
                min_v = p[x]

    if(len(u) < len(graph) and min_x):
        return dijkstra_shortest_path(graph, min_x, p, u)
    else:
        return p

if __name__ == '__main__':
    # инициализация графа с помощью словаря смежности
    a, b, c, d, e, f, g, h = range(8)
    N = [
        {b: 7, c: 9, f: 14},
        {a: 7, c: 10, d: 15},
        {a: 9, b: 10, d: 11, f: 2},
        {b: 15, c: 11, e: 6},
        {d: 6, f: 9},
        {a: 14, c: 2, e: 9},
        {h: 2},
        {g: 2},
    ]
    for i in range(1):
        print(dijkstra_shortest_path(N, a))
# b in N[a] - смежность
# len(N[f]) - степень
# N[a][b] - вес (a,b)
# print N[a][b]