Harryxun/sft_time huggingface dataset:
### BUGGY 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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def max_group_members(self):
        return max([len(self.members(r)) for r in self.roots()])
    
N,M = map(int,input().split())

uf = UnionFind(N+1)
for _ in range(M):
    a,b = list(map(int, input().split()))
    uf.union(a,b)

print(uf.max_group_members())


### 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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    def max_group_members(self):
        return -min([i for i in self.parents if i<0])
    
N,M = map(int,input().split())

uf = UnionFind(N+1)
for _ in range(M):
    a,b = list(map(int, input().split()))
    uf.union(a,b)

print(uf.max_group_members())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def f(D, S, T, W):
    close = [set(), set(), set()]
    Q = []
    index = 0
    end = 1
    Q.append((S, 0, 0))

    while end > index:
        p, c, l = Q[index]
        index += 1
        if l == 0 and p == T:
            return c
        close[l].add(p)

        ns = D.setdefault(p, set())
        l, c = (l + 1) % 3, c + (l + 1) // 3
        for n in ns:
            if n in close[l]:
                continue
            Q.append((n, c, l))
            end += 1
    return -1

if __name__ == "__main__":
    N, M = list(map(int, input().split()))
    D = {}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D.setdefault(u, set()).add(v)

    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1

    print(f(D, S, T, N * M * 10))


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = list(map(int, input().split()))

def f(D, S, T):
    close = [[False] * N, [False] * N, [False] * N]
    Q = []
    index = 0
    Q.append((S, 0, 0))

    while len(Q) > index:
        p, c, l = Q[index]
        index += 1
        
        if close[l][p]:
            continue
        
        if l == 0 and p == T:
            return c // 3
        close[l][p] = True

        l, c = (l + 1) % 3, c + 1
        for n in D[p]:
            if close[l][n]:
                continue
            Q.append((n, c, l))
    return -1

if __name__ == "__main__":
    D = {n: set() for n in range(N)}
    for m in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        D[u].add(v)

    S, T = list(map(int, input().split()))
    S -= 1
    T -= 1

    print(f(D, S, T))
### BUGGY CODE ###

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [float("inf") for _ in range(hmaxa)]
dp[0] = 0

for i,name in enumerate(a):
    a_n = (h+name-1)//name
    for _ in range(a_n):
        for j in range(hmaxa-1):
            if name+j <= hmaxa-1:
                dp[j+name] = min(dp[j]+b[i], dp[j+name])

print(min(dp[h:]))

### FIXED CODE ###

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

for i in range(1, hmaxa):
    ab_child = [dp[i-a]+b for a,b in ab]
    dp[i] = min(ab_child)

print(min(dp[h:]))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9+10] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
  tmp = []
  for j in range(1,min(i+1,K+1)):
    tmp.append(dp[i-j]+abs(h[i]-h[i-j]))
  dp[i] = min(tmp)
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###


def is_prime(q):
    if q == 2:
        return True
    return pow(2, q-1, q) == 1

n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    for i in xrange(a, b+1):
        if is_prime(i) and is_prime((i+1)/2):
            s += 1
    print s


### FIXED CODE ###

import math
def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in xrange(3, int(math.sqrt(n))+1, 2):
        if n%i == 0:
            return False
    return True

m = list()
s = 0
for i in xrange(10**5):
    if is_prime(i) and is_prime((i+1)/2):
        s += 1
    m.append(s)

n = input()
for _ in xrange(n):
    s = 0
    a, b = map(int, raw_input().split())
    print m[b] - m[a-1]
### BUGGY CODE ###

import sys
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
lr = [[None] * w for _ in range(h)]
ab = [[None] * w for _ in range(h)]
row_obs = [[] for _ in range(h)]
col_obs = [[] for _ in range(w)]

def main():
    global mat, h, w
    for i, l in enumerate(mat):
        for j, c in enumerate(l):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
    for b in range(2):
        if b == 0:
            obs = row_obs
        else:
            obs = col_obs
            mat = list(zip(*mat))
            h, w = w, h
        for i in range(h):
            k = 0
            prev = -1
            nxt = obs[i][k] if len(obs[i]) > 0 else w
            for j in range(w):
                if mat[i][j] == '#':
                    prev = obs[i][k]
                    nxt = obs[i][k+1] if k+1 < len(obs[i]) else w
                    k += 1
                else:
                    if b == 0:
                        lr[i][j] = (prev, nxt)
                    else:
                        ab[j][i] = (prev, nxt)
    ans = 0
    h, w = w, h
    mat = list(zip(*mat))
    for i in range(h):
        for j in range(w):
            if mat[i][j] != '#':
                l, r = lr[i][j]
                a, b = ab[i][j]
                ans = max(ans, r - l - 1 + b - a - 1 - 1)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
h, w = [int(x) for x in input().split()]
mat = [input() for _ in range(h)]
cnt = [[0] * w for _ in range(h)]
row_obs = [[-1] for _ in range(h)]
col_obs = [[-1] for _ in range(w)]

def main():
    for i, r in enumerate(mat):
        for j, c in enumerate(r):
            if c == '#':
                row_obs[i].append(j)
                col_obs[j].append(i)
        row_obs[i].append(w)
    for j in range(w):
        col_obs[j].append(h)

    for i in range(h):
        k = 0
        while True:
            prev, nxt = (row_obs[i][k], row_obs[i][k+1])
            for j in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == w:
                break
            k += 1

    for j in range(w):
        k = 0
        while True:
            prev, nxt = (col_obs[j][k], col_obs[j][k+1])
            for i in range(prev+1, nxt):
                    cnt[i][j] += nxt - prev - 1
            if nxt == h:
                break
            k += 1

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, cnt[i][j] - 1)
    print(ans)

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

import math
A,B,N = map(int, input().split())
c = 0
d = 0
for i in range(1,N+1):
	if B > N:
		d = (math.floor(A * N / B))-(A * (math.floor(N / B)))
		break
	c = (math.floor(A * i / B))-(A * (math.floor(i / B)))
	if c>d:
		d=c
print(d)

### FIXED CODE ###

import math
A,B,N = map(int, input().split())
c = 0
if B > N:
	c = (math.floor(A * N / B))-(A * (math.floor(N / B)))
elif B <= N:
	c = (math.floor(A * (B-1) / B))-(A * (math.floor((B - 1) / B)))
print(c)
### BUGGY CODE ###

import numpy as np
n,k,q = map(int,input().split())
num_array = np.ones(n) * k
for i in range(q):
    num_array -= 1
    num_array[int(input())-1] +=1
for i in num_array:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
count_dict = {s: 0 for s in range(1,n+1)}
for i in range(q):
    seikaisha = int(input())
    if seikaisha in count_dict:
        count_dict[seikaisha] +=1
    else:
        count_dict[seikaisha] = 0
count_dict_sorted = sorted(count_dict.items(), key=lambda x:x[0])
# print(type(count_dict_sorted))
# print(count_dict_sorted)
for i, j in count_dict_sorted:
    if k + j-q >0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

ls = []
ans = 0

for i in range(k):
    ans += p[i]
    
max_ans = ans
max_index = 0

for i in range(n-k):
    ans -= p[i]
    ans += p[i+k]
    if max_ans < ans:
        max_ans = ans
        max_index = i+1

ans = 0
al = []
for i in range(k):
    pp = p[max_index+i]
    if pp == 200000:
        ans += 2000010000.0000002
    else:
        for j in range(pp):
            ans += (1/pp*(j+1))
            al.append(ans)
    
print(ans)
        

### FIXED CODE ###

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

ls = []
ans = 0

for i in range(k):
    ans += p[i]
    
max_ans = ans
max_index = 0

for i in range(n-k):
    ans -= p[i]
    ans += p[i+k]
    if max_ans < ans:
        max_ans = ans
        max_index = i+1

ans = 0
for i in range(k):
    pp = p[max_index+i]
    for j in range(pp):
        ans += (1/pp*(j+1))
    
print(ans)
### BUGGY CODE ###

from collections import deque
k = int(input())
L = [1,2,3,4,5,6,7,8,9]
L = deque(L)
i = 0
while i < k:
    if int(str(L[i])[-1]) == 0:
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n2)
        L.append(n3)
    elif 1 <= int(str(L[i])[-1]) <= 8:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n1)
        L.append(n2)
        L.append(n3)
    elif int(str(L[i])[-1]) == 9:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        L.append(n1)
        L.append(n2)
    i +=1

print(L[k-1])


### FIXED CODE ###

k = int(input())
L = [1,2,3,4,5,6,7,8,9]
i = 0
while i < k:
    if int(str(L[i])[-1]) == 0:
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n2)
        L.append(n3)
    elif 1 <= int(str(L[i])[-1]) <= 8:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        n3 = L[i]*10 + L[i]%10 +1
        L.append(n1)
        L.append(n2)
        L.append(n3)
    elif int(str(L[i])[-1]) == 9:
        n1 = L[i]*10 + L[i]%10 -1
        n2 = L[i]*10 + L[i]%10
        L.append(n1)
        L.append(n2)
    i +=1

print(L[k-1])
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    M = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        M[r - 1][c - 1] = v

    # dp[i][j][k]=(i,j)にいてその行でk個取得済みの場合の価値の最大値
    dp = [[[-1] * 4 for _ in range(C)] for __ in range(R)]
    dp[0][0][0] = 0
    dp[0][0][1] = M[0][0]
    for i in range(R):
        for j in range(C):
            now = dp[i][j]
            for k in range(4):
                nowk = now[k]
                if nowk < 0: continue
                # 下へ
                if i < R - 1:
                    down = dp[i + 1][j]
                    # 取らない
                    down[0] = max(down[0], nowk)
                    # 取る
                    v = M[i + 1][j]
                    if v > 0:
                        down[1] = max(down[1], nowk + v)
                # 右へ
                if j < C - 1:
                    right = dp[i][j + 1]
                    # 取らない
                    right[k] = max(right[k], nowk)
                    # 取る
                    v = M[i][j + 1]
                    if v > 0 and k < 3:
                        right[k + 1] = max(right[k + 1], nowk + v)
    print(max(dp[R - 1][C - 1]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main():
    input = sys.stdin.readline
    R, C, K = map(int, input().split())
    M = [[0] * C for _ in range(R)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        M[r - 1][c - 1] = v

    # dp[i][j][k]=(i,j)にいてその行でk個取得済みの場合の価値の最大値
    dp = [[-1] * 4 for _ in range(C)]
    dp[0][0] = 0
    dp[0][1] = M[0][0]
    for i in range(R):
        nxt = [[-1] * 4 for _ in range(C)]
        for j in range(C):
            now = dp[j]
            for k in range(4):
                nowk = now[k]
                if nowk < 0: continue
                # 下へ
                if i < R - 1:
                    down = nxt[j]
                    # 取らない
                    down[0] = max(down[0], nowk)
                    # 取る
                    v = M[i + 1][j]
                    if v > 0:
                        down[1] = max(down[1], nowk + v)
                # 右へ
                if j < C - 1:
                    right = dp[j + 1]
                    # 取らない
                    right[k] = max(right[k], nowk)
                    # 取る
                    v = M[i][j + 1]
                    if v > 0 and k < 3:
                        right[k + 1] = max(right[k + 1], nowk + v)
        if i < R - 1: dp = nxt
    print(max(dp[C - 1]))

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

import sys
import copy
import time
import random

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

D = None
C = None
S = None


def cnt_score(t):
    global D, C, S
    score = 0
    cnt = [-1] * 26

    for i in range(D):
        score += S[i][t[i] - 1]
        minusscore = 0
        cnt[t[i] - 1] = i
        for j in range(26):
            minusscore += (i - cnt[j]) * C[j]
        score -= minusscore
    return score


def cnt_contest_score(t, contestid, day, isBefore):
    global D, C, S
    score = 0
    minusscore = 0

    t = set(t)

    for i in range(D):
        if i == day and isBefore is False:
            if i in t:
                minusscore += C[contestid]
            else:
                score -= minusscore
                minusscore = 0
        else:
            if i in t:
                score -= minusscore
                minusscore = 0
            else:
                minusscore += C[contestid]

    score -= minusscore

    return score


def main():
    global D, C, S
    D = int(input())
    C = [int(x) for x in input().split()]
    S = [[int(x) for x in input().split()] for _ in range(D)]

    start = time.time()

    ans = []
    A = [[] for j in range(26)]

    for i, s in enumerate(S):
        ans.append(s.index(max(s)) + 1)
        A[s.index(max(s))].append(i)

    # A = [[None] * COL for j in range(ROW)]

    old_score = cnt_score(ans)
    day = 0
    f = False
    while True:
        # new_ans = copy.deepcopy(ans)

        max_sore = old_score
        before_contest = ans[day]
        before_score = cnt_contest_score(A[before_contest - 1], before_contest - 1, day, True)
        before_score += S[day][before_contest - 1]
        max_contest = ans[day]
        ma_score = 0
        for i in range(26):
            # time up
            current = time.time()
            if current - start > 1.90:
                f = True
                break

            # main
            # main
            aa_score = cnt_contest_score(A[before_contest - 1], before_contest - 1, day, False)
            bb_score = cnt_contest_score(A[i], i, day, True)
            after_score = cnt_contest_score(A[i], i, day, False)
            after_score += S[day][i]
            # new_score = cnt_score(new_ans)
            if aa_score > bb_score:
                if aa_score > ma_score:
                    max_contest = i + 1
                    ma_score = aa_score
        A[ans[day] - 1].remove(day)
        A[max_contest - 1].append(day)
        ans[day] = max_contest
        if f:
            break

        # increment day
        day = (day + 1) % D

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    D = int(input())
    C = [int(x) for x in input().split()]
    S = [[int(x) for x in input().split()] for _ in range(D)]


    for i in range(D):
        print(i % 26 + 1)



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

N, X = map(int, input().split())
x = sorted(set(map(lambda s: abs(int(s) - X), input().split())))

for d in range(x[0], 1, -1):
    for xi in x:
        if xi % d != 0:
            break
    else:
        print(d)
        exit()
print(1)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


N, X = map(int, input().split())
x = list(map(lambda s: abs(int(s) - X), input().split()))

if len(x) < 2:
    print(x[0])
    exit()
d = gcd(x[0], x[1])

for i in range(2, len(x)):
    d = gcd(d, x[i])
print(d)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
INF = 10**10
dp = [INF]*N
dp[0] = 0
dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] = min([dp[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(K, i)+1)])
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [0]*N
dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] = min([dp[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(K, i)+1)])
print(dp[N-1])
### BUGGY CODE ###

def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50100):
    if pri(i):
        l.append(i)
s=5143
while 1:
    n=int(raw_input())
    ans=0
    if n==0:
        break
    for i in range(s):
        if l[i]>n:
            break
        elif n-l[i] in l:
            ans+=1
    print ans

### FIXED CODE ###

def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50000):
    if pri(i):
        l.append(i)
s=5133
ans={}
for i in range(5132):
    for j in range(i,5133):
        a,b=l[i],l[j]
        if a+b>50000:
            break
        if ans.has_key(a+b):
            ans[a+b]+=1
        else:
            ans[a+b]=1
while 1:
    n=int(raw_input())
    if n==0:
        break
    print ans[n] if ans.has_key(n) else 0
### BUGGY CODE ###

import numpy as np

n,k=map(int,input().split())
A=list(map(int,input().split()))
rn=np.array([1]*n)
for i in range(n):
  rn[i:min(n,i+k)]=rn[i:min(n,i+k)]*A[i]
  
for i in range(k,n):
  if rn[i-1]<rn[i]:print('Yes')
  else:print('No')

### FIXED CODE ###

from collections import deque

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


for i in range(k,n):
  if A[i]>A[i-k]:print('Yes')
  else:print('No')
### BUGGY CODE ###

n, p = map(int, input().split())
prime = {2, }
for i in range(3, p + 1):
    for x in prime:
        if i % x == 0:
            break
    else:
        prime.add(i)

ans = 1
for x in prime:
    cnt = 0
    while p % x == 0:
        p //= x
        cnt += 1
    if cnt // n != 0:
        ans *= x * (cnt // n)

print(ans)


### FIXED CODE ###

from copy import deepcopy
from math import ceil
n, p = map(int, input().split())
ans = 1
q = deepcopy(p)
for i in range(2, int(p ** 0.5) + 2):
    cnt = 0
    while p % i == 0:
        p //= i
        cnt += 1
    if cnt > 0:
        ans *= i ** (cnt // n)

print(ans if p != q and n != 1 else q)