from collections import deque

def bfs(graph, start_node):
    # 1. 各頂点の状態を管理する辞書
    # 距離: 資料の (0), (1), (2) に相当。未発見(白)は None とします
    distances = {node: None for node in graph}
    # 訪問済み(赤)を記録するセット
    visited = set()

    # 2. 橙状態の頂点を格納するキューを用意 [cite: 11]
    queue = deque([start_node])

    # 始点の設定 (0 step) [cite: 17]
    distances[start_node] = 0

    print(f"探索開始: 頂点 {start_node}")

    # キューが空になるまで繰り返す
    while queue:
        # キューの先頭から頂点を取り出す (訪問=赤状態へ) [cite: 17, 30]
        # キューの先頭（古いもの）から取り出す
        current_node = queue.popleft()

        if current_node in visited:
            continue

        visited.add(current_node)
        print(f"頂点 {current_node} を訪問 (距離: {distances[current_node]})")

        # 隣接する頂点を順に確認
        for neighbor in graph[current_node]:
            # 未発見(白状態)の頂点があればキューに追加(橙状態) [cite: 30, 45]
            if distances[neighbor] is None:
                # 距離を 1 step 更新 [cite: 17, 30]
                distances[neighbor] = distances[current_node] + 1
                queue.append(neighbor)             # 新しく見つけたものは末尾（後ろ）に入れる
                print(f"  -> 頂点 {neighbor} を発見 (橙状態, 次に訪問予定)")

    return distances

# --- データの準備 (トレース資料のグラフ) ---
# 0: [1, 2], 1: [0, 5, 3], 2: [0, 3, 4] ... のつながりを定義
graph = {
    0: [1, 2],
    1: [0, 3, 5],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 6],
    5: [1, 3, 7],
    6: [4],
    7: [5]
}

# 実行
result_distances = bfs(graph, 0)

print("\n最終的な各頂点への最短距離:")
for node, dist in sorted(result_distances.items()):
    print(f"頂点 {node}: {dist} step")