Problem p02678 (python)

Fixed submission:
import sys
inf = 10**9
sys.setrecursionlimit(inf)


def connect(signs, to_room, from_room):
    signs[to_room][2].add(from_room)
    signs[from_room][2].add(to_room)
    return signs


def update(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    # from_room_dist = signs[from_room][0]
    # from_to_rooms = signs[from_room][1]
    # signs[to_room][2].add(from_room)
    # signs[to_room][2].discard(from_room)
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1] = to_room
    # signs[from_room][2].discard(to_room)
    for from_from_room in signs[from_room][2]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = update(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = update(signs, from_room, from_from_room)
    for from_to_room in signs[from_room][2]:
        if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
            signs = update(signs, from_room, from_to_room)
        # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    to = [[] for _ in range(n)]
    for a, b in ab:
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    dist = [inf] * n
    pre = [None] * n
    queue = [0]
    while queue:
        v = queue.pop(0)
        for u in to[v]:
            if dist[u] != inf:
                continue
            dist[u] = dist[v] + 1
            pre[u] = v
            queue.append(u)

    pre = [i + 1 for i in pre]
    ans = '\n'.join([str(i) for i in ['Yes'] + pre[1:]])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)

inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][2].add(from_room)
    signs[from_room][2].add(to_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    # from_room_dist = signs[from_room][0]
    # from_to_rooms = signs[from_room][1]
    # signs[to_room][2].add(from_room)
    # signs[to_room][2].discard(from_room)
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1] = to_room
    # signs[from_room][2].discard(to_room)
    for from_from_room in signs[from_room][2]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = change_signs(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = change_signs(signs, from_room, from_from_room)
    for from_to_room in signs[from_room][2]:
        if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
            signs = change_signs(signs, from_room, from_to_room)
        # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, None, set()]] + [[inf, None, set()] for _ in range(n - 1)]
    for a, b in ab:
        # print(a, b)
        signs = share_signs(signs, a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        # print(a_dist, b_dist)
        # if a_dist == b_dist:
        if a_dist < b_dist - 1:
            signs = change_signs(signs, a, b)
        elif b_dist < a_dist - 1:
            signs = change_signs(signs, b, a)
        # print(signs)

    del signs[0:2]
    is_yes = all([True if not i[0] == inf else False for i in signs])
    if is_yes:
        ans = ['Yes'] + [i[1] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][2].add(from_room)
    signs[from_room][2].add(to_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    # from_room_dist = signs[from_room][0]
    # from_to_rooms = signs[from_room][1]
    # signs[to_room][2].add(from_room)
    # signs[to_room][2].discard(from_room)
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1] = to_room
    # signs[from_room][2].discard(to_room)
    for from_from_room in signs[from_room][2]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = change_signs(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = change_signs(signs, from_room, from_from_room)
    for from_to_room in signs[from_room][2]:
        if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
            signs = change_signs(signs, from_room, from_to_room)
        # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, None, set()]] + [[inf, None, set()] for _ in range(n - 1)]
    for a, b in ab:
        # print(a, b)
        signs = share_signs(signs, a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        # print(a_dist, b_dist)
        # if a_dist == b_dist:
        if a_dist < b_dist - 1:
            signs = change_signs(signs, a, b)
        elif b_dist < a_dist - 1:
            signs = change_signs(signs, b, a)
        # print(signs)

    del signs[0:2]
    is_yes = all([True if not i[0] == inf else False for i in signs])
    if is_yes:
        ans = ['Yes'] + [i[1] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][0] = signs[to_room][0] + 1
    signs[from_room][1].discard(to_room)
    signs[from_room][2] = to_room
    for from_from_room in signs[from_room][1]:
        if signs[from_room][0] < signs[from_from_room][0] - 1:
            signs = change_signs(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
        signs = change_signs(signs, from_room, from_to_room)
    # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, set(), None]] + [[inf, set(), None] for _ in range(n - 1)]
    for a, b in ab:
        # print(a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        # print(a_dist, b_dist)
        if a_dist == b_dist and a_dist == inf:
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        elif a_dist < b_dist - 1:
            signs = change_signs(signs, a, b)
        elif b_dist < a_dist - 1:
            signs = change_signs(signs, b, a)
        # print(signs)

    del signs[0:2]
    is_yes = all([True if not dist == inf else False for dist, _, _ in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][1].discard(to_room)
    signs[from_room][2] = to_room
    signs[from_room][0] = signs[to_room][0] + 1
    for from_from_room in signs[from_room][1]:
        signs[from_from_room][1].discard(from_room)
        signs = change_signs(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
        signs = change_signs(signs, from_room, from_to_room)
    # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, set(), None]] + [[inf, set(), None] for _ in range(n - 1)]
    for a, b in ab:
        # print(a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        # print(a_dist, b_dist)
        if a_dist == b_dist and a_dist == inf:
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        elif a_dist < b_dist - 1:
            signs = change_signs(signs, a, b)
        elif b_dist < a_dist - 1:
            signs = change_signs(signs, b, a)
        # print(signs)

    del signs[0:2]
    is_yes = all([True if not dist == inf else False for dist, _, _ in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. 1から始める
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][1].discard(to_room)
    signs[from_room][2] = to_room
    signs[from_room][0] = signs[to_room][0] + 1
    for from_from_room in signs[from_room][1]:
        signs[from_from_room][1].discard(from_room)
        signs = change_signs(signs, from_room, from_from_room)
    # if from_room_dist == inf:
    #     for from_from_room in signs[from_room][1]:
    #         signs[from_from_room][1].discard(from_room)
    #         signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
        signs = change_signs(signs, from_room, from_to_room)
    print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, set(), None]] + [[inf, set(), None] for _ in range(n - 1)]
    for a, b in ab:
        print(a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        print(a_dist, b_dist)
        if a_dist == b_dist:
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        elif a_dist < b_dist - 1:
            signs = change_signs(signs, a, b)
        elif b_dist < a_dist - 1:
            signs = change_signs(signs, b, a)
        print(signs)

    del signs[0:2]
    is_yes = all([True if not dist == inf else False for dist, _, _ in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. fromtoの行き先をfromにする
        b. fromtoの距離をfrom+1にする
        c. fromの来るリストにtoを追加
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][1].discard(to_room)
    signs[from_room][2] = to_room
    signs[from_room][0] = signs[to_room][0] + 1
    if from_room_dist == inf:
        for from_from_room in signs[from_room][1]:
            signs[from_from_room][1].discard(from_room)
            signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0] - 1:
        signs = change_signs(signs, from_room, from_to_room)
    # print(signs)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = [[], [0, set(), None]] + [[inf, set(), None] for _ in range(n - 1)]
    for a, b in ab:
        # print(a, b)
        a_dist = signs[a][0]
        b_dist = signs[b][0]
        # print(a_dist, b_dist)
        if a_dist == b_dist:
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        elif a_dist < b_dist:
            signs = change_signs(signs, a, b)
        else:
            signs = change_signs(signs, b, a)
        # print(signs)

    del signs[0:2]
    is_yes = all([True if not dist == inf else False for dist, _, _ in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. fromtoの行き先をfromにする
        b. fromtoの距離をfrom+1にする
        c. fromの来るリストにtoを追加
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][2] = to_room
    signs[from_room][0] = signs[to_room][0] + 1
    if from_room_dist == inf:
        for from_from_room in signs[from_room][1]:
            signs[from_from_room][1].discard(from_room)
            signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0]:
        signs[from_to_room][2] = from_room
        signs[from_to_room][0] = signs[from_to_room][0] + 1
        signs[from_room][1].add(from_to_room)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = {1: [0, set(), None]}
    for a, b in ab:
        # print(a, b)
        if a in signs or b in signs:
            a_dist = signs.setdefault(a, [inf, set(), None])[0]
            b_dist = signs.setdefault(b, [inf, set(), None])[0]
            # print(a_dist, b_dist)
            if a_dist == b_dist:
                signs = share_signs(signs, a, b)
                signs = share_signs(signs, b, a)
            elif a_dist < b_dist:
                signs = change_signs(signs, a, b)
            else:
                signs = change_signs(signs, b, a)

        else:
            signs[a] = [inf, set(), None]
            signs[b] = [inf, set(), None]
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        # print(signs)

    del signs[1]
    signs = sorted(signs.items(), key=lambda x: x[0])
    # print(signs)
    is_yes = all([True if not i[0] == inf else False for _, i in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for _, i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. fromの距離を記憶
    2. fromの行き先を記憶
    3. toの来るリストにfromを追加
    4. fromの行き先にtoを追加
    5. fromの距離をto+1に変更
    6. もともとのfromの距離がinfなら
        a. fromの来るリスト(fromfrom)の行き先をfromにする
        b. fromfromの来るリストからfromを削除
        c. 1から始める
    7. fromの新しい距離がもともとのfromの行き先(fromto)の距離がより短いなら、
        a. fromtoの行き先をfromにする
        b. fromtoの距離をfrom+1にする
        c. fromの来るリストにtoを追加
    """
    from_room_dist = signs[from_room][0]
    from_to_room = signs[from_room][2]
    signs[to_room][1].add(from_room)
    signs[from_room][2] = to_room
    signs[from_room][0] = signs[to_room][0] + 1
    if from_room_dist == inf:
        for from_from_room in signs[from_room][1]:
            signs[from_from_room][1].remove(from_room)
            signs = change_signs(signs, from_room, from_from_room)
    if from_to_room and signs[from_room][0] < signs[from_to_room][0]:
        signs[from_to_room][2] = from_room
        signs[from_to_room][0] = signs[from_to_room][0] + 1
        signs[from_room][1].add(from_to_room)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(m)]

    signs = {1: [0, set(), None]}
    for a, b in ab:
        # print(a, b)
        if a in signs or b in signs:
            a_dist = signs.setdefault(a, [inf, set(), None])[0]
            b_dist = signs.setdefault(b, [inf, set(), None])[0]
            # print(a_dist, b_dist)
            if a_dist == b_dist:
                signs = share_signs(signs, a, b)
                signs = share_signs(signs, b, a)
            elif a_dist < b_dist:
                signs = change_signs(signs, a, b)
            else:
                signs = change_signs(signs, b, a)

        else:
            signs[a] = [inf, set(), None]
            signs[b] = [inf, set(), None]
            signs = share_signs(signs, a, b)
            signs = share_signs(signs, b, a)
        # print(signs)

    del signs[1]
    signs = sorted(signs.items(), key=lambda x: x[0])
    # print(signs)
    is_yes = all([True if not i[0] == inf else False for _, i in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for _, i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):

import math
inf = 10**9


def share_signs(signs, to_room, from_room):
    signs[to_room][1].add(from_room)
    return signs


def update_inf_room(signs, to_room, inf_rooms):
    for inf_room in inf_rooms:
        signs[inf_room][0] = signs[to_room][0] + 1
        signs[inf_room][2] = to_room
    return signs


def change_signs(signs, to_room, from_room):
    """
    1. toの来るリストにfromを追加
    2. fromの行き先にtoを追加
    3. fromの距離を記憶
    4. fromの距離をto+1に変更
    5. もともとのfromの距離がinfならばfromの来るリストもtoに結びつける
        a. fromの来るリスト(fromfrom)の来るリストからfromを削除
        b. 1,2,3,4を行う
    """
    signs[to_room][1].add(from_room)
    signs[from_room][2] = to_room
    from_room_dist = signs[from_room][0]
    signs[from_room][0] = signs[to_room][0] + 1
    if from_room_dist == inf:
        for from_from_room in signs[from_room][1]:
            signs[from_from_room][1].remove(from_room)
            signs = change_signs(signs, from_room, from_from_room)
    return signs


def main():
    n, m, *ab = map(int, open(0).read().split())
    ab = [ab[2 * i:2 * (i + 1)] for i in range(len(ab) // 2)]

    signs = {1: [0, set(), None]}
    for a, b in ab:
        # print(a, b)
        if a in signs or b in signs:
            a_dist = signs.setdefault(a, [inf, set(), None])[0]
            b_dist = signs.setdefault(b, [inf, set(), None])[0]
            # print(a_dist, b_dist)
            if a_dist == b_dist:
                signs = share_signs(signs, a, b)
                signs = share_signs(signs, b, a)
            elif a_dist < b_dist:
                signs = change_signs(signs, a, b)
            else:
                signs = change_signs(signs, b, a)

        else:
            signs[a] = [inf, set(), None]
            signs[b] = [inf, set(), None]
        # print(signs)

    del signs[1]
    signs = sorted(signs.items(), key=lambda x: x[0])
    # print(signs)
    is_yes = all([True if not i[0] == inf else False for _, i in signs])
    if is_yes:
        ans = ['Yes'] + [i[2] for _, i in signs]
    else:
        ans = ['No']
    ans = '\n'.join([str(i) for i in ans])

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()