Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N, M, K  = (int(i) for i in input().split())
graph = [[0] * (N+1) for i in range(N+1)]
graph2 = [[0] * (N+1) for i in range(N+1)]

#ABC = [[int(i) for i in input().split()] for i in range(N)]
for i in range(M):
    A, B =  (int(i) for i in input().split())
    graph[A][B] = 1
    graph[B][A] = 1
    graph2[A][B] = 1
    graph2[B][A] = 1

for j in range(K):
    A, B =  (int(i) for i in input().split())
    graph2[A][B] = -1
    graph2[B][A] = -1

graph = np.array(graph)
#print(graph)
#print(graph2)
n, labels = connected_components(graph)

#print(n)
# 2
#print(labels)

for i in range(1, N+1):
    count = 0
    for j in range(1,N+1):
        if i == j:
            continue
        if graph2[i][j] == 0 and labels[i] == labels[j]:
            #print(i, j)
            count += 1
    print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

N, M, K  = (int(i) for i in input().split())

#graph = np.zeros((N+1, N+1))
#graph2 = [[0] * (N+1) for i in range(N+1)]
uf = UnionFind(N)
fblist = [0] * (N+1)

for i in range(M):
    A, B =  (int(i) for i in input().split())
    uf.union(A, B)
    fblist[A] += 1
    fblist[B] += 1
 
for j in range(K):
    A, B =  (int(i) for i in input().split())
    if uf.same(A, B):
        fblist[A] += 1
        fblist[B] += 1

for i in range(1, N+1):
    print(uf.size(i) - fblist[i] - 1, end=" ")

print()
### BUGGY CODE ###

from scipy.special import comb

N, M, K = list(map(int, input().split()))
mod = 998244353

c = comb(N-1, K, exact=True)
exp = ((M-1) ** (N-1-K)) % mod

answer = (M * c * exp) % mod

for t in range(1, K+1):
    c = ((c * (K - t + 1)) // (N-1-K+t))
    exp = (exp*(M-1)) % mod
    answer += (M * c * exp) % mod
    answer = answer % mod

print(answer)

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
mod = 998244353

c = 1
answer = 0

for i in range(K+1):
    answer += (M * c  * pow(M-1, N - i - 1, mod)) % mod
    answer %= mod
    c = (c * (N-i-1) * pow(i+1, mod-2, mod)) % mod
    
print(answer)
### BUGGY CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += (A[i][k] * B[k][j]) % MOD
                C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

MOD = 10**9+7

def dot(A, B):
    N = len(A)
    K = len(A[0])
    assert len(B) == K
    M = len(B[0])
    C = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            for k in range(K):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= MOD
    return C



def mp(A, n):
    assert len(A) == len(A[0])
    B = [[0] * len(A) for _ in range(len(A))]
    for i in range(len(A)):
        B[i][i] = 1

    while n:
        n, i = divmod(n, 2)
        if i:
            B = dot(A, B)
        A = dot(A, A)

    return B


ans = sum([sum(r) % MOD for r in mp(A, K)]) % MOD
print(ans)
### BUGGY CODE ###

A, B, N = map(int, input().split())
biggest = 0

for i in range(1, N+1):
    X = ((A*i) // B)
    Y = A * (i // B)
    if biggest < (X - Y):
        biggest = X - Y

print(biggest)

### FIXED CODE ###

A, B, N = map(int, input().split())


if N >= B:
    X = (A*(B-1)) // B
    Y = A * ((B-1)//B)
    print(X-Y)
else:
    X = (A*N) // B
    Y = A * (N//B)
    print(X-Y)
### BUGGY CODE ###

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(60):
    c = 0
    for a in A:
        if (a>>i) & 1: c += 1
        
    ans += (c * (N-c) % MOD * 2 **i % MOD) % MOD
        
print(ans%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    ans = 0
    MOD = 10**9+7
    k = 1
    x = np.max(A)
    n = 1 if x == 0 else int(np.log2(x))+1

    for i in range(n):
        c = np.count_nonzero(A%2)
        A >>= 1
        ans = (ans + c * (N-c) * k) % MOD
        k = (2*k) % MOD

    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
dist = [[None]*W for _ in range(H)]

stack = deque([])
for h in range(H):
    for w in range(W):
        if maze[h][w]=="#":
            stack.append((h,w))
            dist[h][w] = 0

ans = 0
while stack:
    ch,cw = stack.popleft()
    ans = max(ans, dist[ch][cw])
    for y,x in zip([0,0,-1,1], [1,-1,0,0]):
        nh,nw = ch+y, cw+x
        if not(0 <= nh < H and 0 <= nw < W):
            continue
        if dist[nh][nw] == None:
            stack.append((nh,nw))
            dist[nh][nw] = dist[ch][cw] + 1
        else:
            dist[nh][nw] = min(dist[nh][nw], dist[ch][cw] + 1)

print(ans)
# print(*dist, sep="\n")


### FIXED CODE ###

from collections import deque

H,W = map(int, input().split())
maze = [input() for _ in range(H)]
visited = [[False]*W for _ in range(H)]
q = deque([])

# initialize
for h in range(H):
    for w in range(W):
        if maze[h][w] == "#":
            q.append((h,w,0))
            visited[h][w] = True

ans = 0
while q:
    h,w,d = q.popleft()
    for dy,dx in zip([0,0,-1,1], [-1,1,0,0]):
        nh, nw = h+dy, w+dx
        if not(0<=nh<H and 0<=nw<W):
            continue
        if not visited[nh][nw]:
            q.append((nh,nw,d+1))
            visited[nh][nw] = True
            ans = max(ans, d+1)

print(ans)
### BUGGY CODE ###

import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
# import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

input = sys.stdin.readline

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

B = list(itertools.accumulate(A))

ans = 0
for l in range(N):
    for r in range(l, N):
        t = B[r] - (B[l - 1] if l - 1 >=0 else 0)
        if t % M == 0:
            ans += 1

print(ans)


### FIXED CODE ###

import sys
import collections
from collections import Counter
# from collections import deque
# from collections import defaultdict
import itertools
# from itertools import accumulate
# from itertools import permutations
# from itertools import combinations
# from itertools import takewhile
from itertools import compress
import functools
# from functools import reduce
import math
# from math import gcd
# from math import inf
# from math import ceil
# from math import floor
# from math import log10
# from math import log2
# from math import log
from math import factorial

# import re

input = sys.stdin.readline

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

B = list(itertools.accumulate(A))
C = [0] + [x % M for x in B]

ans = 0

CNT = collections.Counter(C)

for k, v in CNT.items():
    if v >= 2:
        ans += v * (v - 1) // 2

print(ans)
### BUGGY CODE ###

S = input()
cnt = 0

length = len(S)
for i in range(0,len(S)-4):
  for j in range(i+4,i+4+length//3):
    if int(S[i:j+1]) % 2019 == 0 and j<length:
      cnt += 1

print(cnt)

### FIXED CODE ###

import collections
S = input()
cnt = 0

mod = [0]
reverse_S = S[::-1]
for i in range(len(reverse_S)):
  now = int(reverse_S[i]) * pow(10,i,2019)
  mod.append((now + mod[i]) % 2019)


c = collections.Counter(mod)
hindo = c.values()
for i in hindo:
  if i != 1:
    cnt += i*(i-1)//2


print(cnt)
### BUGGY CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    info[a - 1].append(b - 1)
    info[b - 1].append(a - 1)


def checker(n, info2):
    for i in info[n]:
        if n in info2[i]:
            continue
        else:
            info2[n].append(i)
            checker(i, info2)


def plus(n, val):
    ans[n] += val
    for i in info2[n]:
        plus(i, val + Query[i])


info2 = [[] for _ in range(N)]
checker(0, info2)
Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))


### FIXED CODE ###

import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
check = [1 for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    info[a - 1].append(b - 1)
    info[b - 1].append(a - 1)


def plus(n, val):
    ans[n] += val
    check[n] = 0
    for i in info[n]:
        if check[i]:
            plus(i, val + Query[i])


Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))
### BUGGY CODE ###

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
n,m,k=map(int,input().split())
w=998244353
t=0
c=1
b=m*((m-1)**(n-1))%w
for i in range(k+1):
    t += c * b
    t %= w
    c*=(n-1-i)
    c*=power_func(i+1,w-2,w)
    c%=w
    b*=power_func(m-1,w-2,w)
    b%=w

print(t)

### FIXED CODE ###

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
n,m,k=map(int,input().split())
w=998244353
t=0
c=1
b=m*((m-1)**(n-1))%w
g=power_func(m-1,w-2,w)
for i in range(k+1):
    t += c * b
    t %= w
    if i<k:
        c*=(n-1-i)
        c*=power_func(i+1,w-2,w)
        c%=w
        b*=g
        b%=w
if m==1 and k==n-1:
    print(1)
else:
    print(t)
### BUGGY CODE ###

n = int(input())
ans = 0
anslist = []
for i in range(n):
  s = input()
  slist = [i for i in s]
  slist.sort()
  for j in range(len(anslist)):
    if slist == anslist[j]:
      ans += 1
  anslist.append(slist)
print(ans)

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n = int(input())
ans = 0
sum = 0
ansdic = {}
for i in range(n):
  s = input()
  slist = [i for i in s]
  slist.sort()
  smoji = ','.join(slist)
  if smoji in ansdic:
    ansdic[smoji] += 1
  else:
    ansdic[smoji] = 1
for i in ansdic:
  if ansdic[i] > 1:
    sum += cmb(ansdic[i],2)
print(sum)
### BUGGY CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

mx = max(P)
ans = 0.0
for i in range(0, n - k + 1):
    T = P[i: i + k]
    if mx in T:
        tmp = 0.0
        for t in T:
            M = [j for j in range(1, t + 1)]
            tmp += sum(M) / t
        ans = max(tmp, ans)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))

C = [(1 + p) / 2 for p in P]

ans = tmp = sum(C[: k])
for i in range(k, n):
    tmp += (C[i] - C[i - k])
    ans = max(tmp, ans)

print(ans)
### BUGGY CODE ###

import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S1 = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}

S = []
for i in range(N):
    S.append(alpha[S1[i]])


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = S[j]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)

# 文字の交換


def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        bc = S[i - 1]
        ac = alpha[y]
        S[i - 1] = ac
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)


### FIXED CODE ###

import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    # i文字目を、変化点があった文字として探索する
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)
### BUGGY CODE ###

n = int(input())
listx = [int(input()) for i in range(n)]

listx.sort()
listy=[]

x=listx.pop(0)
listy.append(x)
x=listx.pop(-1)
listy.append(x)
listy.sort()

while len(listx)>=1:
    abs1=abs(listx[0]-listy[-1])
    abs2=abs(listx[-1]-listy[0])

    if abs1 < abs2:
        x=listx.pop(-1)
        listy.insert(0,x)
    else:
        x=listx.pop(0)
        listy.append(x)
    
    if listy[0] > listy[-1]:
        listy.reverse()
ans=0
for i in range(len(listy)-1):
    ans=ans+abs(listy[i]-listy[i+1])

print(ans)


### FIXED CODE ###

import itertools
import numpy as np
data_num = int(input()) 
data = [int(input()) for i in range(data_num)] 
#data_num=5
#data=[6,8,1,2,3]

data.sort()
npdata=np.array(data)

parts1=[1]
parts2=[2 for i in range(data_num-2)]
parts1.extend(parts2)
parts1.append(1)
npparts1=np.array(parts1)

parts0=[(-1)**(i+1) for i in range(data_num)]
npparts0=np.array(parts0)

y=npparts1*npparts0

y=y.tolist()
y.sort()

y=np.array(y)
z1=sum(data*y)

parts01=[(-1)**i for i in range(data_num)]
npparts0=np.array(parts01)

y=npparts1*npparts0

y=y.tolist()
y.sort()
y=np.array(y)
z2=sum(data*y)

print(max(z1,z2))
### BUGGY CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b - visited)]
    return -1


print(BC132_E())

### FIXED CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())
### BUGGY CODE ###

n, q = map(int, input().split())
nei = {}
for i in range(n):
  nei[i] = set()
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    nei[u].add(v)
    nei[v].add(u)
  else:
    stack = [u]
    visited = set()
    flag = False
    while stack:
      node = stack.pop()
      if node in visited:
        continue
      if node == v:
        flag = True
        break
      visited.add(node)
      for next_node in nei[node]:
        stack.append(next_node)
    if flag:
      print(1)
    else:
      print(0)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
n, q = map(int, input().split())
un = UnionFind(n)
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    un.union(u, v)
  else:
    print(1 if un.same(u, v) else 0)
### BUGGY CODE ###

x = int(input())

y = 1000
s = -1000
t = -1000

a = 0
b = 0

while s < y:
    t = -y
    while t < y:
        if s ** 5 - t ** 5 == x:
            a = int(s)
            b = int(t)
        t += 1
    s += 1

print(a, b)






### FIXED CODE ###

x = int(input())

y = 1000
s = -1000
t = -1000

a = 0
b = 0

while s < y:
    t = -y
    while t < y:
        if s ** 5 - t ** 5 == x:
            a = int(s)
            b = int(t)
        t += 1
    s += 1

print(a, b)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())
lr = []
for i in range(q):
    lr.append(list(input().split()))

for i in range(q):
    cnt = 0
    start = int(lr[i][0])-1
    end = int(lr[i][1])-1

    cnt = s[start:(end+1)].count('AC')

    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())
lr = []
for i in range(q):
    lr.append(list(input().split()))

n = len(s)
ary = [0 for i in range(len(s)+1)]

for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        ary[i+1] = ary[i] + 1
    else:
        ary[i+1] = ary[i]

for i in range(q):
    ans = ary[int(lr[i][1])] - ary[int(lr[i][0])]
    print(ans)
### BUGGY CODE ###

import heapq
def dijkstra_heap(s,g,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * (n+2)
    used = [True] * (n+2) #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
    for i in range(n+2):
        x,y,r=edge[i][0],edge[i][1],edge[i][2]
        dist=((x-sx)**2+(y-sy)**2)**(1/2)
        heapq.heappush(edgelist,[max(dist-r-sr,0),i])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        v = minedge[1]
        if not used[v]:
            continue
        d[v] = minedge[0]
        used[v] = False
        bx,by,br=edge[v][0],edge[v][1],edge[v][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-bx)**2+(y-by)**2)**(1/2)
            if used[i]:
                heapq.heappush(edgelist,[max(dist-r-br,0)+d[v],i])
        if not used[g]:
            break
    return d[g]

sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
n=int(input())
edge=[[sx,sy,0],[gx,gy,0]]
for i in range(2,n+2):
    x,y,r=map(int,input().split())
    edge.append([x,y,r])
print(dijkstra_heap(0,1,edge))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    import heapq
    def dijkstra_heap(s,g,edge):
        #始点sから各頂点への最短距離
        d = [10**20] * (n+2)
        used = [True] * (n+2) #True:未確定
        d[s] = 0
        used[s] = False
        edgelist = []
        sx,sy,sr=edge[s][0],edge[s][1],edge[s][2]
        for i in range(n+2):
            x,y,r=edge[i][0],edge[i][1],edge[i][2]
            dist=((x-sx)**2+(y-sy)**2)**(1/2)
            heapq.heappush(edgelist,(max(dist-r-sr,0),i))
        while len(edgelist):
            minedge = heapq.heappop(edgelist)
            #まだ使われてない頂点の中から最小の距離のものを探す
            v = minedge[1]
            if not used[v]:
                continue
            d[v] = minedge[0]
            used[v] = False
            bx,by,br=edge[v][0],edge[v][1],edge[v][2]
            for i in range(n+2):
                x,y,r=edge[i][0],edge[i][1],edge[i][2]
                dist=((x-bx)**2+(y-by)**2)**(1/2)
                if used[i]:
                    heapq.heappush(edgelist,(max(dist-r-br,0)+d[v],i))
            if not used[g]:
                break
        return d[g]

    sx,sy,gx,gy = map(int,input().split()) #n:頂点数　w:辺の数
    n=int(input())
    edge=[(sx,sy,0),(gx,gy,0)]
    for i in range(2,n+2):
        x,y,r=map(int,input().split())
        edge.append((x,y,r))
    print(dijkstra_heap(0,1,edge))

if __name__ == '__main__':
    main()