#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの大きい順にソート
edges.sort(key = lambda x: -x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

#-------- 入力例１ ---------
N = 7       # 頂点数
M = 9       # 辺数
# つながっている２つの頂点とその長さ
edges = [
    (1, 2, 12),
    (1, 3, 10),
    (2, 6, 160),
    (2, 7, 15),
    (3, 4, 1),
    (3, 5, 4),
    (4, 5, 3),
    (4, 6, 120),
    (6, 7, 14)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1
    
    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x
    
    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときのみ処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]
    
    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# 辺を長さの小さい順にソート
edges.sort(key = lambda x: x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
    if not uf.same(a, b):
        uf.unite(a, b)
        answer += c

# 答えの出力
print('解：', answer)

#-------- 入力例１ ---------
N = 5       # 駅の数
M = 5       # ２つの駅をつなぐ路線の数
edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (4, 5),
    (3, 5)
]

Q = 5       # クエリ―数
query = [
    [2, 1, 5],
    [1, 3],
    [2, 1, 5],
    [1, 5],
    [2, 1, 5]
]
#---------------------------
edge = []
# インデックスを0スタートにする
for A, B in edges:
    edge.append((A - 1, B - 1))

# 最後まで残っている辺を求める
last = [True] * M
for q in query:
    if q[0] == 1:
        q[1] -= 1
        last[q[1]] = False
    else:
        q[1] -= 1
        q[2] -= 1

# union-find木
uf = [-1] * N
def root(i):
    while True:
        if uf[i] < 0:
            return i
        if uf[uf[i]] < 0:
            return uf[i]
        uf[i] = uf[uf[i]]
        i = uf[i]

def unite(i, j):
    i = root(i)
    j = root(j)
    if i == j:
        return
    # union by size
    if uf[i] > uf[j]:
        i, j = j, i
    uf[i] += uf[j]
    uf[j] = i

ans = []
for i in range(M):
    if last[i]:
        A, B = edge[i]
        unite(A, B)

# クエリ―を逆順に処理する
for q in reversed(query):
    if q[0] == 1:
        A, B = edge[q[1]]
        unite(A, B)
    else:
        _, U, V = q
        ans.append("移動可能" if root(U) == root(V) else "移動不可")

# クエリ―の順番を戻して、回答を表示
for s in reversed(ans):
    print(s)

#-------- 入力例１ ---------
N = 3       # 頂点数
Q = 4       # クエリ―数
queries = [
    (1, 1, 2),
    (2, 1, 3),
    (1, 2, 3),
    (2, 2, 3)
]
#---------------------------
# Union-Find 木
class unionfind:
    # n 頂点の Union-Find 木を作成
    # 頂点番号が 1 - indexed になるように実装するので n + 1 としている。
    def __init__(self, n):
        self.n = n
        self.par = [ -1 ] * (n + 1) # 最初は親が無い
        self.size = [ 1 ] * (n + 1) # 最初はグループの頂点数が 1

    # 頂点 x の根を返す関数
    def root(self, x):
        # 1 個先（親）がなくなるまで、1 個先（親）に進み続ける
        while self.par[x] != -1:
            x = self.par[x]
        return x

    # 要素 u, v を統合する関数
    def unite(self, u, v):
        rootu = self.root(u)
        rootv = self.root(v)
        if rootu != rootv:
            # u と v が異なるグループのときに処理を行う
            if self.size[rootu] < self.size[rootv]:
                self.par[rootu] = rootv
                self.size[rootv] += self.size[rootu]
            else:
                self.par[rootv] = rootu
                self.size[rootu] += self.size[rootv]

    #  要素 u と v が同一のグループかどうかを返す関数
    def same(self, u, v):
        return self.root(u) == self.root(v)

# クエリの処理
uf = unionfind(N)
for tp, u, v in queries:
    if tp == 1:         # クエリ―１の処理を行う
        uf.unite(u, v)
    if tp == 2:         # クエリ―２の処理を行う
        if uf.same(u, v):
            print(f'頂点 {u} と頂点 {v} は同じ連結成分に属する。')
        else:
            print(f'頂点 {u} と頂点 {v} は同じ連結成分に属さない。')

#-------- 入力例１ ---------
N = 7       # 社員数
T = 3       # 社長の社員番号
R = [(3, 2), (3, 1), (2, 5), (1, 4), (4, 6), (4, 7)]  # 上司または部下の関係 
#-------- 入力例２ ---------
# N = 7       # 社員数
# T = 7       # 社長の社員番号
# R = [(3, 2), (3, 1), (2, 5), (1, 4), (4, 6), (4, 7)]  # 上司または部下の関係 
#---------------------------
g = [[] for i in range(N)]
for A, B in R:
    A -= 1
    B -= 1
    g[A].append(B)
    g[B].append(A)

rank = [0] * N

# 深さ優先探索
#   parent:上司の社員番号
#   i:チェックする社員番号
def dfs(parent, i):
    for j in g[i]:          # ある社員の部下全員分をループ
        if j == parent:     # 上司の社員番号は無視
            continue
        r = dfs(i, j) + 1   # チェックする社員番号を上司として、その部下のランクを取得する
        if rank[i] < r:     # 現在保持しているものよりランクが大きければ更新する
            rank[i] = r
    return rank[i]
dfs(-1, T - 1)  # 上司はいないので-1、社長番号T（インデックス化するため-1）としてランクを取得する

for i in range(N):
    print(f'社員 {i + 1} の階級は {rank[i]}')

#-------- 入力例１ ---------
N = 7                   # 社員数
A = [1, 1, 3, 2, 4, 5]  # 社員番号２から社員番号７の直属の上司の社員番号
#---------------------------
# 隣接リストの作成
G = [list() for i in range(N + 1)]
for i in range(2, N + 1):
    G[A[i - 2]].append(i) # 上司 → 部下の方向に方向に辺を追加

# 動的計画法（dp[x] は社員 x の部下の数）
dp = [0] * (N + 1)
for i in range(N, 0, -1):
    for j in G[i]:
        dp[i] += (dp[j] + 1)

for i in range(1, N + 1):
    print(f'社員 {i} の部下の数は {dp[i]} 人')

#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
from heapq import heappush, heappop

g = [[] for _ in range(N)]
for A, B, C in edges:
    A -= 1
    B -= 1
    g[A].append((B, C))
    g[B].append((A, C))

INF = 1 << 61
cost = [INF] * N
back = [-1] * N
q = []

# 頂点に訪れる部分を関数化
def push(prev, i, c):
    if cost[i] <= c:
        return
    cost[i] = c
    back[i] = prev
    heappush(q, (c, i))

# 復元の都合上後ろから ダイクストラ法を行う
push(-1, N - 1, 0)
while q:
    c, x = heappop(q)
    if cost[x] != c:
        continue # 同じ頂点から複数回探索しない
    for j, d in g[x]:
        push(x, j, c + d)

# 最短経路を復元
ans = [0]
while ans[-1] != N - 1:
    ans.append(back[ans[-1]])

for x in ans:
    print(x + 1)

#-------- 入力例１ ---------
N = 6       # 頂点数
M = 7       # 辺の数
# つながっている頂点とその距離
edges = [
    (1, 2, 14),
    (1, 4, 22),
    (2, 3, 62),
    (2, 5, 5),
    (3, 6, 52),
    (4, 5, 38),
    (5, 6, 18)
]
#---------------------------
import heapq

# 隣接リストの作成
# 重み付きグラフなので、各辺について (隣接頂点, 重み) のタプルを記録
G = [list() for i in range(N + 1)]
for a, b, c in edges:
    G[a].append((b, c))
    G[b].append((a, c))

# 配列・キューの初期化
# キューには (距離, 頂点番号) のタプルを記録
kakutei = [ False ] * (N + 1)
cur = [float('inf')] * (N + 1)  # 距離の暫定値
cur[1] = 0
Q = []
heapq.heappush(Q, (cur[1], 1))

# ダイクストラ法
while len(Q) > 0:
    # 次に確定させるべき頂点を求める
    # 優先度付きキュー Q の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を pos に代入
    pos = heapq.heappop(Q)[1]

    # Q の最小要素が「既に確定した頂点」の場合
    if kakutei[pos] == True:
        continue

    # 暫定値 cur[x] の値を更新する
    kakutei[pos] = True
    for e in G[pos]:
        # pos = e[0], cost = e[1] で対応
        if cur[e[0]] > cur[pos] + e[1]:
            cur[e[0]] = cur[pos] + e[1]
            heapq.heappush(Q, (cur[e[0]], e[0]))

# 答えを出力
for i in range(1, N + 1):
    if cur[i] == float('inf'):
        print('頂点 {} までの最短距離 {}'.format(i, -1))
    else:
        print('頂点 {} までの最短距離 {}'.format(i, cur[i]))

#-------- 入力例１ ---------
H, W = 7, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 4, 5   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#......#',
  '#.######',
  '#..#...#',
  '#..##..#',
  '##.....#',
  '########'
]
#-------- 入力例２ ---------
H, W = 5, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 2, 4   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#.#....#',
  '#.###..#',
  '#......#',
  '########'
]

#---------------------------
# マスごとの移動回数
cost = [[float('inf')] * W for _ in range(H)]

q = [] # queue は list で代用

# マスに移動する部分を関数化
def push(x, y, c):
    if S[x][y] == '#':  # 壁なので移動できない
        return
    if cost[x][y] <= c: # より少ない移動回数で移動済み（設定済み）
        return
    cost[x][y] = c
    q.append((x, y))

# 幅優先探索
push(sx - 1, sy - 1, 0)
for x, y in q:
    # コストを１つ増やす
    c2 = cost[x][y] + 1
    # 上下左右をチェック
    push(x - 1, y, c2)
    push(x, y - 1, c2)
    push(x + 1, y, c2)
    push(x, y + 1, c2)

print('解：', cost[gx - 1][gy - 1])

#-------- 入力例１ ---------
N = 6       # 頂点数
M = 5       # 辺の数
# 頂点同士のつながり情報
edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 6)]
#---------------------------
from collections import deque

# 隣接リストの作成
G = [ list() for i in range(N + 1) ]
for a, b in edges:
    G[a].append(b)
    G[b].append(a)

# 幅優先探索の初期化（dist[i] = -1 で初期化）
dist = [-1] * (N + 1)
dist[1] = 0
Q = deque()
Q.append(1)

# 幅優先探索
while len(Q) > 0:
    pos = Q.popleft() # キュー Q の先頭要素を取り除き、その値を pos に代入する
    for nex in G[pos]:
        if dist[nex] == -1: # まだチェックしてない頂点
            dist[nex] = dist[pos] + 1
            Q.append(nex)

# 頂点 1 から各頂点までの最短距離を出力
for i in range(1, N + 1):
    print('頂点 1 から頂点 {} までの最短経路は {}'.format(i, dist[i]))