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

import sys
sys.setrecursionlimit(1000000)
def find_root(edges, root, group, before, now):
    group.append(now)
    children = edges[now]
    for child in children:
        if child != before and child not in group:
            root, group = find_root(edges, root, group, now, child)
    return root, group
    
if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [[] for _ in range(N)]
    rails = [[] for _ in range(N)]
    road_roots = [None]*N
    rail_roots = [None]*N
    answer = [1]*N
        
    for i in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        roads[p].append(q)
        roads[q].append(p)
    
    for i in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        rails[r].append(s)
        rails[s].append(r)
    
    for i, r in enumerate(road_roots):
        if r is None:
            root, group = find_root(roads, i, [], -1, i)
            for g in group:
                road_roots[g] = root

    for i, r in enumerate(rail_roots):
        if r is None:
            root, group = find_root(rails, i, [], -1, i)
            for g in group:
                rail_roots[g] = root
                
    railroads=[[rail, road] for rail, road in zip(road_roots, rail_roots)]

    for n in range(N):
        for d in range(1, N-n):
            if railroads[n] == railroads[n+d]:
                answer[n] += 1 
                answer[n+d] += 1
                
    print(' '.join(list(map(str, answer))))

### FIXED CODE ###

from collections import defaultdict
def build_tree(N, edges):
    root_list = [i for i in range(N)]
    for p, q in edges:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

if __name__ == '__main__':
    N, K, L = map(int, input().split())
    roads = [None]*K
    rails = [None]*L
    for k in range(K):
        roads[k] = list(map(int, input().split()))
    for l in range(L):
        rails[l] = list(map(int, input().split()))
    
    
    '''N = 2*10**5
    L = int(N/2)
    K = int(N/2)
    roads = [None]*K
    rails = [None]*L
    for i in range(L):
        roads[i] = [2*i, 2*i+1]
    for i in range(K):
        rails[i] = [2*i, 2*i+1]'''
    
    road_roots = build_tree(N, roads)
    rail_roots = build_tree(N, rails)
    
    railroads = defaultdict(int)
    RR = []
    for n in range(N):
        rr = (get_root(road_roots, n), get_root(rail_roots, n))
        RR.append(rr)
        railroads[rr] += 1
    answer = [railroads[key] for key in RR]
    print(' '.join(map(str, answer)))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

memo={}

def f(n):
    if n==0:
        return 0
    elif n in memo:
        return memo[n]
    else:
        pc = format(n, 'b').count('1')
        return f(n%pc)+1

def main():
    N = int(input())
    X = list(input())
    for i in range(N):
        xi = X[:]
        if X[i]=='1':
            xi[i]='0'
        elif X[i]=='0':
            xi[i]='1'
        print(f(int(''.join(xi),2)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def pc(x):
    return format(x, 'b').count('1')

N = int(input())
X = input()
Xn = int(X,2)
p = pc(Xn)
X = list(X)

Xp = Xn%(p+1)
if p==1:
    Xm = 0
else:
    Xm = Xn%(p-1)

def f(i):
    if p==1 and X[i]=='1':
        #Xi == 0 > POPcount ==0
        return 0
    else:
        if X[i]=='1':
            # p->p-1
            ret = Xm - pow(2, N-1-i, p-1)
            ret %= p-1
        else:
            # p->p+1
            ret = Xp + pow(2, N-1-i, p+1)
            ret %= p+1
        cnt = 1
        while ret > 0:
            ret %= pc(ret)
            cnt += 1
        return cnt

def main():
    for i in range(N):
        ret = f(i)
        print(ret)

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

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


AX=[0]*(N+1)
na=N+1
for i in range(1,N+1):
    AX[i]=AX[i-1]+A[i-1]
    if K<AX[i]:na=min(na,i)

BX=[0]*(M+1)
nb=M+1
for i in range(1,M+1):
    BX[i]=BX[i-1]+B[i-1]
    if K<BX[i]:nb=min(nb,i)

ans=0
for i in range(na):
 for j in range(nb):
   if K < AX[i]+BX[j]:break
   ans=max(ans,i+j)
            
print(ans)

### FIXED CODE ###

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

AX=[0]*(N+1)
na=N+1
for i in range(1,N+1):
    AX[i]=AX[i-1]+A[i-1]
    if K<AX[i]:na=min(na,i)

BX=[0]*(M+1)
nb=M+1
for i in range(1,M+1):
    BX[i]=BX[i-1]+B[i-1]
    if K<BX[i]:nb=min(nb,i)

import bisect        
ans=0
for i in range(na):
 j=bisect.bisect_right(BX,K-AX[i])-1
 # print(na,t,i,j)
 ans=max(ans,i+j)
            
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	G_fix
# CreatedDate:  2020-06-05 21:28:41 +0900
# LastModified: 2020-06-05 21:54:44 +0900
#


import os
import sys
import heapq
#import numpy as np
#import pandas as pd


def main():
    n,m = map(int,input().split())
    path = [[] for _ in range(n+1)]
    to_cnt = [0]*(n+1)
    longest_cnt = [0]*(n+1)
    for _ in range(m):
        x,y = map(int,input().split())
        path[x].append(y)
        to_cnt[y]+=1
#    print(to_cnt)
    
    Q = []
    for i in range(1,n+1):
        if to_cnt[i]==0:
            Q.append(i)

#    longest_cnt[s]=1
    heapq.heapify(Q)
    count=0
    while(Q):
        u = heapq.heappop(Q)
        for v in path[u]:
            to_cnt[v]-=1
            if longest_cnt[u]+1>longest_cnt[v]:
                longest_cnt[v]=longest_cnt[u]+1
            heapq.heappush(Q,v)
    print(max(longest_cnt))



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections

# input処理を高速化する
input = sys.stdin.readline

def chmax(a, b):
    """ 最大値を返す関数 """
    if a >= b:
        return a
    return b

def main():
    # 入力
    N, M = map(int, input().split())
    # 隣接関係は隣接リストで管理する
    lst_edge = [[] for _ in range(N)]
    # 各頂点の入力辺の本数
    deg = [0] * N
    for _ in range(M):
        x, y = map(int, input().split())
        # 最初のindexをゼロにする
        lst_edge[x-1].append(y-1)
        deg[y-1] += 1

    # 入力辺を持たない頂点をqueueに入れる
    que = collections.deque()
    for v in range(N):
        if deg[v] == 0:
            que.append(v)

    # 各頂点の最初に入力辺を持たなかった点からの距離
    dp = [0] * N

    # For sequences, (strings, lists, tuples), use the fact that empty sequences are false.
    # https://www.python.org/dev/peps/pep-0008/#programming-recommendations
    while que:
        v = que.popleft()
        lst_nv = lst_edge[v]
        for nv in lst_nv:
            # エッジ(v, nv)をグラフから削除する
            deg[nv] -= 1
            if deg[nv] == 0:
                # エッジがなくなったことで、入力辺がなくなったらqueueに入れる
                que.append(nv)
                # 最初に入力辺を持たなかった点からの距離
                dp[nv] = chmax(dp[nv], dp[v] + 1)

    print(max(dp))

main()
### BUGGY CODE ###

N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a,  b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, K + 2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nPr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return ((factorial[n] * inverse[r]) % MOD) * (inverse[n - r] * factorial[r] % MOD) % MOD


ans = K
stack = [[0, 0]]  # [頂点番号, 深さ]
visited = [False] * N
while stack:
    n, depth = stack.pop()
    visited[n] = True

    child = 0
    for to in T[n]:
        if visited[to]:
            continue

        child += 1
        stack.append([to, depth + 1])

    if depth == 0:
        ans *= nPr(K - 1, child)
    else:
        ans *= nPr(K - 2, child)

print(ans % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
T = [[] for i in range(N)]
MOD = 10 ** 9 + 7
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)


stack = [0]
visited = [0] * N
child_num = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1
    for to in T[n]:
        if visited[to]:
            continue
        child_num[n] += 1
        stack.append(to)


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, 10 ** 5 + 1):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))


# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = K
stack = [0]
visited = [0] * N
while stack:
    n = stack.pop()
    visited[n] = 1

    if n == 0:
        ans = ans * nCr(K - 1, child_num[n]) * factorial[child_num[n]] % MOD
    else:
        ans = ans * nCr(K - 2, child_num[n]) * factorial[child_num[n]] % MOD
    for to in T[n]:
        if visited[to]:
            continue
        stack.append(to)

print(ans % MOD)
### BUGGY CODE ###

import math
import copy
# import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

a = getInputListInt()
min = a[0]
max = a[1]

ans_max = 2019
ans = ans_max

for i in range(min, max):
    for j in range(i+1, max+1):
        tmp = (i*j) % ans_max

        if ans > tmp:
            ans = tmp
        
        if ans == 0:
            break

print(ans)

### FIXED CODE ###

import math
import copy
# import numpy as np

# ===FUNCTION===

def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList

# ===CODE===

a = getInputListInt()
min = a[0]
max = a[1]

ans_max = 2019
ans = ans_max

flg = False

for i in range(min, max):
    for j in range(i+1, max+1):
        tmp = (i*j) % ans_max

        if ans > tmp:
            ans = tmp

        if ans == 0:
            flg = True
            break

    if flg:
        break

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

import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

for i in range(M):
    a = A.pop()
    a = a // 2
    bisect.insort_right(A, a)

# print(A)
x = sum(A)
print(x)

### FIXED CODE ###

import heapq

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = [-1 * i for i in A]

    heapq.heapify(A)

    for i in range(M):
        a = heapq.heappop(A)
        a = -1 * (-1 * a // 2)
        heapq.heappush(A, a)


    x = -1 * sum(A)
    print(x)


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

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()
### BUGGY CODE ###

import numpy as  np
import math
 
def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
 
 
x = int(input())
data = get_sieve_of_eratosthenes(x+100000000)
data = np.array(data)
indices = np.where(data > x)[0]
# print(indices)
print(data[indices[0]])
 

### FIXED CODE ###

import numpy as  np
import math

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


x = int(input())
data = get_sieve_of_eratosthenes(x+100)
data = np.array(data)
indices = np.where(data >= x)[0]
# print(indices)
print(data[indices[0]])
### BUGGY CODE ###

from collections import Counter

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

A.sort()
A_max = A[-1]


def prime_factorization(n):
    counter = Counter()

    if n < 2:
        return counter

    for i in range(2, int(n ** 0.5) + 1):
        if i * i > n:
            break

        while n % i == 0:
            counter[i] += 1
            n //= i

    if n > 1:
        counter[n] += 1

    return counter


used = set()
A_set = set(A)

pairwise = True
setwise = True

u = set()
flag = True
for a in A:
    counter = prime_factorization(a)

    if flag:
        u = set(counter.keys())
        flag = False
    else:
        u = u.intersection(counter.keys())

    if pairwise:
        for k in counter.keys():
            if k in used:
                continue

            v = k
            cnt = 1

            while v <= A_max:
                if v != a and v in A_set:
                    pairwise = False
                    break

                cnt += 1
                v = k * cnt

            if not pairwise:
                break

            used.add(k)


if pairwise:
    print('pairwise coprime')
elif not u:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

from collections import defaultdict
from math import gcd

N = int(input())
A = list(map(int, input().split()))
A_set = set(A)

num = 10 ** 6
primes = [0] * (num + 1)
primes[0] = 1
primes[1] = 1

for i in range(2, num + 1):
    if primes[i] != 0:
        continue

    cnt = 1
    while i * cnt <= num:
        primes[i * cnt] = i
        cnt += 1


def func(n):
    res_dic = defaultdict(int)
    while n > 1:
        x = primes[n]
        res_dic[x] += 1
        n //= x

    return res_dic


pairwise = True
cnt_dic = defaultdict(int)
for a in A:
    dic = func(a)

    for k in dic.keys():
        cnt_dic[k] += 1
        if cnt_dic[k] > 1:
            pairwise = False
            break

g = A[0]
for a in A[1:]:
    g = gcd(g, a)

if pairwise:
    print('pairwise coprime')
elif g == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

from operator import mul
from functools import reduce
N=int(input())
li = list(map(int,input().split()))	
if reduce(mul, li)<=10**18:
  print(reduce(mul, li))
else:
  print("-1")

### FIXED CODE ###

n = int(input())
As = list(map(int, input().split()))

result = As[0]
if 0 in As:
    print(0)
else:
    for i in range(n-1):
        result = result*As[i+1]
        if result > 10**18 :
            print(-1)
            break
        else:
            continue
    if result <= 10**18 :
        print(result)
### BUGGY CODE ###

import sys
N, A, B = map(int, input().split())
count = 0
while True:
    for i in range(A):
        N -= 1
        count += 1
        if N == 0:
            print(count)
            sys.exit()
    for j in range(B):
        N -= 1
        if N == 0:
            print(count)
            sys.exit()

### FIXED CODE ###

N, A, B = map(int, input().split())
answer = N // (A+B) * A
remainder = N % (A+B)
answer += min(remainder, A)
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n=int(input())

A=list(map(int,input().split()))

ans=0

for i in range(n-1):
    for j in range(i+1,n):
        
        ans += (A[i] * A[j]) % (10**9+7)

print(ans % (10**9+7))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n=int(input())

A=list(map(int,input().split()))

B=[A[0]]

for i in range(len(A)-1):
    B.append((B[i]+A[i+1]) % (10**9+7))

ans=0

for i in range(n-1):
    
    ans += (A[i] * (B[-1]-B[i])  % (10**9+7))
    
#    for j in range(i+1,n):
        
#        ans += (A[i] * A[j]) % (10**9+7)
#
print(ans % (10**9+7))
### BUGGY CODE ###

import sys
s = input()
K = int(input())
     
sort_s = sorted(list(s))
temp = []
for i in range(len(s)):
    for j in range(1,K+1):
        # if i >j:
        # print("{},{}".format(i,j))
        if i+j <= len(s):
            temp.append(s[i:i+j])
sort_temp=sorted(temp)
ans =[]
for i in sort_temp:
    if i not in ans:
        ans.append(i)
sort_ans = sorted(ans)
print(sort_ans[K-1])

### FIXED CODE ###

import sys
s = input()
K = int(input())
     
# sort_s = sorted(list(s))
temp = set()
# temp = []
for i in range(len(s)):
    for j in range(i+1,i+K+1):
        # if i >j:
        # print("{},{}".format(i,j))
        temp.add(s[i:j])
        # if i+j <= len(s):
            # temp.append(s[i:i+j])
ans = sorted(temp)
print(ans[K-1])
### BUGGY CODE ###

h, w = map(int, input().split())

def calc(big, small1, small2):
    sqs = [big, small1, small2]
    if None in sqs:
        return float("inf")
    sqs = sorted(sqs)
    return abs(sqs[0] - sqs[-1])


results = []
def sq_split(h, w, depth, target=None, target2=None):
    if depth == 2:
        # print(h, w, h*w, target, target2)
        results.append([h*w, target, target2])
    if h != 1:
        sq_split(h//2, w, depth + 1, target=((h + 1)//2) * w, target2=target)
        sq_split((h + 1)//2, w, depth + 1, target=(h//2) * w, target2=target)
    if w != 1:
        sq_split(h, w//2, depth + 1, target=h * ((w + 1) // 2), target2=target)
        sq_split(h, (w + 1)//2, depth + 1, target=h * (w//2), target2=target)

sq_split(h, w, 0)
# print(sorted(results, key=lambda x: calc(*x)))
print(sorted(map(lambda x: calc(*x), results))[0])


### FIXED CODE ###

h, w = map(int, input().split())

ans_wsplit = [max(abs((i * w) - (((h - i) + 1) // 2) * w), abs((i * w) - ((h - i) // 2) * w)) for i in range(1, h)]
ans_hsplit = [max(abs((i * h) - (((w - i) + 1) // 2) * h), abs((i * h) - ((w - i) // 2) * h)) for i in range(1, w)]

ans_wline = [max(abs((i * w) - ((w + 1) // 2) * (h - i)), abs((i * w) - (w // 2) * (h - i))) for i in range(1, h)]
ans_hline = [max(abs((i * h) - ((h + 1) // 2) * (w - i)), abs((i * h) - (h // 2) * (w - i))) for i in range(1, w)]

print(min(ans_wsplit + ans_hsplit + ans_wline + ans_hline))