CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = copy.copy(u)
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print((len(ans)))





# Optimized solution
# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print((len(ans)))
# Original solution
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    trial += 1
print(trial)

# Optimized solution
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm == answer:
                    print(trial)
                    exit()
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    
# print(trial)
# Original solution
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
queue = [[ini_state, zero_x, zero_y]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = set()
visited |= {hashnum(ini_state)}
trial = 0
while answer not in visited:
    new_queue = []
    trial += 1
    for q in queue:
        state, zero_x, zero_y = q
        for i in range(len(dx)):
            new_state = copy.deepcopy(state)
            new_x = zero_x + dx[i]
            new_y = zero_y + dy[i]
            if 0 <= new_x < 3 and 0 <= new_y < 3:
                new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                perm = hashnum(new_state)
                if perm == answer:
                    print(trial)
                    exit()
                if perm not in visited:
                    visited |= {perm}
                    new_queue.append([new_state, new_x, new_y])
    queue = new_queue
    
# print(trial)

# Optimized solution
import copy
def hashnum(state):
    num = 0
    for i in range(3):
        for j in range(3):
            num *= 10
            num += state[i][j]
    return num

answer = 123456780
ini_state = []
for i in range(3):
    temp = [int(n) for n in input().split(" ")]
    if 0 in temp:
        zero_x, zero_y = temp.index(0), i
    ini_state.append(temp)
end_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
queue = [[ini_state, zero_x, zero_y, 0], [end_state, 2, 2, 1]]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = {}
if hashnum(ini_state) == answer:
    print((0))
else:
    visited[hashnum(ini_state)] = [0, 0]
    visited[answer] = [0, 1]
    trial = 0
    ended = 0
    while queue:
        new_queue = []
        trial += 1
        for q in queue:
            if ended:
                break
            state, zero_x, zero_y, direction = q
            for i in range(len(dx)):
                new_state = copy.deepcopy(state)
                new_x = zero_x + dx[i]
                new_y = zero_y + dy[i]
                if 0 <= new_x < 3 and 0 <= new_y < 3:
                    new_state[new_y][new_x], new_state[zero_y][zero_x] = new_state[zero_y][zero_x], new_state[new_y][new_x]
                    perm = hashnum(new_state)
                    if perm in visited and direction != visited[perm][1]:
                        print((trial + visited[perm][0]))
                        ended = 1
                        break
                    elif perm not in visited:
                        visited[perm] = [trial, direction]
                        new_queue.append([new_state, new_x, new_y, direction])
        queue = new_queue
# Original solution
v,e = list(map(int, input().split()))
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
group = [[i] for i in range(v)]
key = [i for i in range(v)]
sum = 0
for i,j,k in adj:
    if key[i] != key[j]:
        h = key[j]
        group[key[i]] += group[h]
        sum += k
        for t in group[h]:
            key[t] = key[i]
        group[h] = []
        if len(group[key[i]]) == v:
            break
print(sum)


# Optimized solution
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x, y):
    return root(x) == root(y)

def unite(x, y):
    x = root(x)
    y = root(y)
    par[x] = y

v,e = list(map(int, input().split()))
adj = [list(map(int, input().split())) for i in range(e)]
adj.sort(key = lambda x:x[2])
par = [i for i in range(v)]
sum = 0

for i,j,k in adj:
    if not same(i, j):
        sum += k
        unite(i, j)
print(sum)
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = list(map(int, each))
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    path_heap = []
    hp.heappush(path_heap, (distance[init_v], init_v))

    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in list(adj_table[current_vertex].items()):
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(path_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = list(map(int, _input[0].split()))
    v_info = [x.split() for x in _input[1:]]

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print((sum(prim_span_tree())))

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6

output:
5
"""

import sys
import heapq as hp

WHITE, GRAY, BLACK = 0, 1, 2


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = list(map(int, each))
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def prim_span_tree():
    distance[init_v] = 0
    parent[init_v] = -1
    path_heap = []
    hp.heappush(path_heap, (0, init_v))

    while len(path_heap) >= 1:
        current_vertex = hp.heappop(path_heap)[1]

        color[current_vertex] = BLACK

        for adj_vertex, adj_weight in list(adj_table[current_vertex].items()):
            if color[adj_vertex] is not BLACK:
                if adj_weight < distance[adj_vertex]:
                    distance[adj_vertex] = adj_weight
                    parent[adj_vertex] = current_vertex
                    color[adj_vertex] = GRAY
                    hp.heappush(path_heap, (adj_weight, adj_vertex))

    return distance


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, edges = list(map(int, _input[0].split()))
    v_info = [x.split() for x in _input[1:]]

    parent = [-1] * vertices
    distance = [float('inf')] * vertices
    color = [WHITE] * vertices
    init_v = 0

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)
    print((sum(prim_span_tree())))
# Original solution
import sys

def kruskal(v_count: int, edges: list) -> int:
    tree = [-1]*v_count

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for (w, _s, _t), _ in zip([p for p in sorted(edges) if unite(*p[1:])],
                              list(range(v_count-1))):
        cost += w
    return cost

V, E = list(map(int, input().split()))
edges = [(w, s, t) for s, t, w in (list(map(int, l.split())) for l in sys.stdin)]
print((kruskal(V, edges)))


# Optimized solution
import sys
from itertools import islice

def kruskal(v_count: int, edges: list) -> int:
    tree = [-1]*v_count

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a):
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(list(filter(unite, sorted(edges))), v_count-1):
        cost += w
    return cost

V, E = list(map(int, input().split()))
edges = [(w, s, t) for s, t, w in (list(map(int, l.split())) for l in sys.stdin)]
print((kruskal(V, edges)))
# Original solution
from heapq import heappush, heappop
class Prim:
    """ find minimum spanning tree by Prim's algorithm
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
            start: start vertex
            INF: Infinity cost
        """
        self.prim(V, E, start, INF)

    def prim(self, V, E, start=0, INF=10**9):
        used = [False] * V
        self.mincost = 0
        que = []
        heappush(que, (0, 0))
        while len(que) > 0:
            cost, v = heappop(que)
            if used[v]: continue
            used[v] = True
            self.mincost += cost
            for to, c in E[v]:
                heappush(que, (c, to))

    def minCost(self):
        return self.mincost
    

    
V, E = list(map(int, input().split()))
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = list(map(int, input().split()))
    edge[s].append((t, w))
    edge[t].append((s, w))

msp = Prim(V, edge)
print((msp.minCost()))

# Optimized solution
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       
       used in SRM505 div.2 900
    """
    def __init__(self, n):
        self.par = list(range(n)) # parent
        self.rank = [0] * n # depth of tree

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

class Kruskal:
    """ Kruskal's algorithm: find minimum spanning tree
        Complexity: O(E log(V))
        used in GRL2A(AOJ)
    """

    def __init__(self, V, E, start=0, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list (undirected graph)
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2: edges.append((cost, v1, v2))
        edges.sort()
        self.mincost = 0
        self.minSpanningTree = []
        uf = UnionFindTree(V)
        for cost, v1, v2 in edges:
            if uf.same(v1, v2) == False:
                self.mincost += cost
                uf.unite(v1, v2)
                self.minSpanningTree.append((v1, v2, cost))

    def minCost(self):
        return self.mincost

    def getMinSpanningTree(self):
        return sorted(self.minSpanningTree)
    
V, E = list(map(int, input().split()))
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = list(map(int, input().split()))
    edge[s].append((t, w))
    edge[t].append((s, w))

msp = Kruskal(V, edge)
print((msp.minCost()))
# Original solution
import array
import collections
import heapq

AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1
 
# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # ????????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

max_v, max_e = list(map(int, input().split()))
adjacency_list = collections.defaultdict(set)
for _ in range(max_e):
    s, t, w = list(map(int, input().split()))
    adjacency_list[s].add(AdjacentVertex(t, w))
    adjacency_list[t].add(AdjacentVertex(s, w))
(_, key) = compute_mst_prim(max_v, adjacency_list)

print((sum(key.values())))

# Optimized solution
import heapq
from collections import defaultdict

INF = float('inf')


V, E = list(map(int, input().split()))
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = list(map(int, input().split()))
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    isVisited = [False] * x
    hq = [(0,0)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        isVisited[u] = True
        
        for v, c in Adj_list[u]:
            if not isVisited[v] and d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print((prim(V)))
# Original solution
import heapq
def prim(g, v):
    for vi in range(v):
        g[vi].sort()
    
    cost = 0
    heap = iter(g[0])
    rest_tree = set(range(1, v))
    while rest_tree:
        d, u = next(heap)
        if u in rest_tree:
            cost += d
            rest_tree -= {u}
            heap = heapq.merge(heap, g[u])
    return cost

from sys import stdin
readline = stdin.readline


v, e = list(map(int, readline().split()))
from collections import defaultdict
g = defaultdict(list)
for _ in range(e):
    s, t, d = list(map(int, readline().split()))
    g[s].append((d, t))
    g[t].append((d, s))

print((prim(g, v)))

# Optimized solution
def kruskal(g, size):
    g.sort(key=itemgetter(2), reverse=True)
    uf = union_find(size)
    tree = []
    while len(tree) < size - 1:
        u, v, d = g.pop()
        if not uf.union(u, v):
            tree.append((u, v, d))
    return tree

class union_find:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:return True
        
        if self.table[y] < self.table[x]:x, y = y, x

        self.table[x] += self.table[y]
        self.table[y] = x
        return False
            
    def find(self, x):
        if self.table[x] < 0:return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]

from sys import stdin
from operator import itemgetter

import heapq

readline = stdin.readline


v, e = list(map(int, readline().split()))

g = [list(map(int, readline().split())) for _ in range(e)]

tree = kruskal(g, v)

print((sum(d for s, t, d in tree)))
# Original solution
# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

while weight:
  a, b, c = weight[0]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  weight.pop(0)
  
print(sum_weight)
  


  


# Optimized solution
# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

for i in range(E):
  a, b, c = weight[i]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  else:
    continue
  
print(sum_weight)
# Original solution
from collections import defaultdict
import heapq

vertices,edges = list(map(int,input().split(" ")))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = list(map(int,input().split(" ")))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = set()
now_weight = 0
way[0] = 0

while len(went) < vertices:
    here_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    now_weight += here_weight
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
        if c not in went and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
    went = went | {here}
print(now_weight)

# Optimized solution
from collections import defaultdict
import heapq

vertices,edges = list(map(int,input().split(" ")))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = list(map(int,input().split(" ")))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = [0] * vertices
now_weight = 0
way[0] = 0

while queue:
    here_weight,here = heapq.heappop(queue)
    #print(went)
    if went[here]:
        continue
    went[here] = 1
    now_weight += here_weight
    min_weight,next_t = float("inf"),-1
    for c in link[here]:
        if not went[c] and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
print(now_weight)