Harryxun/stf_run huggingface dataset:
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())
    
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    uf.union(A[i],B[i])
groups = uf.group_count()
print(groups-1)

### 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())
    
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
groups = uf.group_count()
print(groups-1)
N, M = map(int, input().split())
sc = [tuple(map(int, input().split())) for _ in range(M)]

for i in range(1000):
    t = str(i)
    if len(t) != N:
        continue
    ok = True
    for s, c in sc:
        if t[int(s)] != int(c):
            ok = False
            break
    if ok:
        print(i)
        exit()
print(-1)


### FIXED CODE ###

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

t = [-1] * N
for _ in range(M):
    s, c = map(int, input().split())
    s -= 1
    if t[s] != -1 and t[s] != c:
        print(-1)
        exit()
    t[s] = c

if N == 1 and t[0] == 0:
    print(0)
    exit()

if N == 1 and t[0] == -1:
    print(0)
    exit()

if t[0] == 0:
    print(-1)
    exit()

if t[0] == -1:
    t[0] = 1

for i in range(1, N):
    if t[i] == -1:
        t[i] = 0

print(''.join(map(str, t)))
import itertools


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

lights = []
for i in range(M):
    lights.append([int(x) - 1 for x in input().split()[1:]])

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

is_ok = 0
for mode in itertools.product((0, 1), repeat=M):
    mode = list(mode)
    on = 0
    for i, light in enumerate(lights):
        sw = 0
        for x in light:
            sw += mode[x]
        if sw % 2 == patterns[i]:
            on += 1
    if on == M:
        is_ok += 1

print(is_ok)


### FIXED CODE ###

import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=N):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)
b = input()

if b == A:
    print("T")
elif b == T:
    print("C")
elif b == C:
    print("G")
elif b == G:
    print("C")


### FIXED CODE ###

b = input()

if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "C":
    print("G")
elif b == "G":
    print("C")
n = int(input())
if n[0] == n[2]:
	print('Yes')
else:
	print('No')

### FIXED CODE ###

n = input()
if n[0] == n[2]:
	print('Yes')
else:
	print('No')
ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

print(ma_map[2])
ma.sort()
print(dfs(N))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

ma_map = [ -1, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]
N, M = (int(i) for i in input().split())
ma = list(int(i) for i in input().split())
memo = [-1] * 100000

def dfs(num):
	if memo[num] != -1: return memo[num]
	if num == 0: return 0

	ret = -1
	for p in ma:
		if 0 <= num - ma_map[p]:
			d = dfs(num - ma_map[p])
			if d == -1: continue
			ret = max(dfs(num - ma_map[p]) * 10 + p, ret)

	memo[num] = ret
	return ret

ma.sort()
print("{}".format(dfs(N)))
A, B = map(int, input().split())

def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x == A) and (y == B)

answer = -1
for n in range(20000):
    if test(n):
        ans = n
        break
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
A,B = map(int,read().split())
 
def test(n):
    x = n * 8 // 100
    y = n * 10 // 100
    return (x == A) and (y == B)
 
answer = -1
for n in range(20000):
    if test(n):
        answer = n
        break
print(answer)
N = input()
if N % 10 == 3:
  print('bon')
elif N % 10 == 0:
  print('pon')
elif N % 10 == 1:
  print('pon') 
elif N % 10 == 6:
  print('pon')
elif N % 10 == 8:
  print('pon')  
else:
  print('hon')
 

### FIXED CODE ###

N = int(input())
if N % 10 == 3:
  print('bon')
elif N % 10 == 0:
  print('pon')
elif N % 10 == 1:
  print('pon') 
elif N % 10 == 6:
  print('pon')
elif N % 10 == 8:
  print('pon')  
else:
  print('hon')
X=int(input())

if 400<=X<=599:
    print(8)
elif 600<=X<=799:
    print(6)
elif 800<=X<=999:
    prnit(6)
elif 1000<=X<=1199:
    print(5)
elif 1200<=X<=1399:
    print(4)
elif 1400<=X<=1599:
    print(3)
elif 1600<=X<=1799:
    print(2)
elif 1800<=X<=1999:
    print(1)

### FIXED CODE ###

x = int(input())
 
if 400 <= x <= 599:
    print(8)
elif 600 <= x <= 799:
    print(7)
elif 800 <= x <= 999:
    print(6)
elif 1000 <= x <= 1199:
    print(5)
elif 1200 <= x <= 1399:
    print(4)
elif 1400 <= x <= 1599:
    print(3)
elif 1600 <= x <= 1799:
    print(2)
elif 1800 <= x <= 1999:
    print(1)
import collections
N=int(input())
S=list(input() for i in range(N))
S=collections.Counter(S)
S=S.most_common()
if S[0][1]>S[1][1]:
  print(S[0][0])
else:
  s=[i for i in S if i[1]==S[0][1]]
  s=dict(s)
  s=list(s.keys())
  s=sorted(s)
  for i in s:
    print(i)

### FIXED CODE ###

import collections
N=int(input())
S=list(input() for i in range(N))
S=collections.Counter(S)
S=S.most_common()
if len(S)==1:
  print(S[0][0])
elif S[0][1]>S[1][1]:
  print(S[0][0])
else:
  s=[i for i in S if i[1]==S[0][1]]
  s=dict(s)
  s=list(s.keys())
  s=sorted(s)
  for i in s:
    print(i)
s=list(int(input()))
q=int(input())
for i in range(q):
    t=list(input())
    if t[0]==1:
        s.reverse()
    else:
        if t[1]==1:
            s.insert(0,t[2])
        else:
            s.append(t[2])
print("".join(s))


### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
rev=0
for i in range(q):
    t=list(input().split())
    if t[0]=="1":
        rev=rev+1
    else:
        if t[1]=="1":
            if rev%2==0:
                s.appendleft(t[2])
            else:
                s.append(t[2])
        else:
            if rev%2==0:
                s.append(t[2])
            else:
                s.appendleft(t[2])
if rev%2==0:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
from collections import Counter


def main():
    n = int(input())
    v = list(map(int, input().split()))
    a = [v[i] for i in range(n) if i % 2 == 0]
    b = [v[i] for i in range(n) if i % 2 == 1]
    half_n = n // 2
    a_count = Counter.most_common(Counter(a))
    b_count = Counter.most_common(Counter(b))
    ans = 0
    if a_count[0][1] > b_count[0][1]:
        ans += half_n - a_count[0][1]
        if a_count[0][0] == b_count[0][0]:
            ans += half_n - b_count[1][1]
        else:
            ans += half_n - b_count[0][1]
    elif a_count[0][1] < b_count[0][1]:
        ans += half_n - b_count[0][1]
        if a_count[0][0] == b_count[0][0]:
            ans += half_n - a_count[1][1]
        else:
            ans += half_n - a_count[0][1]
    else:
        if a_count[0][0] == b_count[0][0]:
            ans += half_n - a_count[0][1]
            ans += half_n - b_count[1][1]
        else:
            ans += half_n - a_count[0][1]
            ans += half_n - b_count[0][1]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    v = list(map(int, input().split()))
    # a = [v[i] for i in range(n) if i % 2 == 0]
    # b = [v[i] for i in range(n) if i % 2 == 1]

    # a_count = Counter.most_common(Counter(a))
    # b_count = Counter.most_common(Counter(b))

    # half_n = n // 2
    ac = Counter(v[::2]).most_common(2)
    bc = Counter(v[1::2]).most_common(2)

    if ac[0][0] != bc[0][0]:
        print(n - ac[0][1] - bc[0][1])
    else:
        if len(bc) == 1 or len(ac) == 1:
            print(n // 2)
        else:
            print(n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1]))

    # ans = 0

    # half_n = n // 2
    # eq = a_count[0][0] == b_count[0][0]
    # h_ac0 = half_n - a_count[0][1]
    # h_bc0 = half_n - b_count[0][1]

    # if len(a_count) == 1 and len(b_count) == 1:
    #     if eq:
    #         print(half_n)
    #         exit()
    #     else:
    #         print(ans)
    #         exit()

    # if a_count[0][1] > b_count[0][1]:
    #     ans += h_ac0
    #     if eq:
    #         ans += half_n - b_count[1][1]
    #     else:
    #         ans += h_bc0
    # elif a_count[0][1] < b_count[0][1]:
    #     ans += h_bc0
    #     if eq:
    #         ans += half_n - a_count[1][1]
    #     else:
    #         ans += h_ac0
    # else:
    #     if eq:
    #         ans += h_ac0
    #         ans += half_n - b_count[1][1]
    #     else:
    #         ans += h_ac0
    #         ans += h_bc0
    # print(ans)


if __name__ == '__main__':
    main()
N = int(input())
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)


def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  now = pow(2, N-1, MOD)-1
  for t in ts:
    now -= pow(2, t, MOD)-1
  ans += now
  return res

ans = 0
MOD = 10**9+7
dfs(1)
print((ans * pow(pow(2, N, MOD), MOD-2, MOD)) % MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  # print(v, ts)

  # now = pow(2, N-1, MOD)-1
  now = pows[N-1]-1
  for t in ts:
    # now -= pow(2, t, MOD)-1
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7
# 高速化1
pows = [1] * (N+1)
for i in range(1, N+1):
  pows[i] = (pows[i - 1] * 2) % MOD

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)
# -*- coding: utf-8 -*-
import numpy as np
import math

A, B = input().split()
A = int(A)
B_float = float(B)
B_int = int(B[0]+B[2:])
if B_float < 1:
    B_float = B_float*100
    C = A*B_float/100
    #C_str = str(C)
    print("{}".format(int(C)))
else:
    C = A*B_int
    C_str = str(C)
    #iti = C_str.find('.')
    print("{}".format(int(C_str[:-2])))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import math

A, B = input().split()
A = int(A)
B_float = float(B)
B_int = int(B[0]+B[2:])
if B_float < 1:
    B_float = B_float*100
    C = A*B_float/100
    #C_str = str(C)
    print("{}".format(int(C)))
elif not A==0:
    C = A*B_int
    C_str = str(C)
    #iti = C_str.find('.')
    print("{}".format(int(C_str[:-2])))
elif A==0:
    print("{}".format(0))
n = int(input())

u = [0] * (n-1)
v = [0] * (n-1)
w = [0] * (n-1)

node = [i for i in range(n)]

group1 = []
group2 = []

for i in range(n-1):
    u[i], v[i], w[i] = map(int, input().split())
    u[i] -= 1
    v[i] -= 1
    w[i] = w[i] % 2
    # 同じなら0、違ったら1
    if w[i] == 0:
        if node[u[i]] == u[i]:
            node[u[i]] = node[v[i]]
        elif node[u[i]] != u[i]:
            node[v[i]] = node[u[i]]

for i in range(n-1):
    if w[i] == 1:
        if u[i] in group1:
            group2.append(node[v[i]])
        elif u[i] in group2:
            group1.append(node[v[i]])
        elif v[i] in group1:
            group2.append(node[u[i]])
        elif v[i] in group2:
            group1.append(node[u[i]])
        else:
            group1.append(node[v[i]])
            group2.append(node[u[i]])

for i in range(n):
    if node[i] in group1:
        node[i] = 0
    else:
        node[i] = 1

for color in node:
    print(color)


### FIXED CODE ###

n, k = map(int, input().split())
s = str(input())

s = s[:k-1] + s[k-1].lower() + s[k:]
print(s)
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
d = factor(m)

def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr
M = 10**9+7 # 出力の制限
N = max(d.values())+10+n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

if m!=1:
    ans = 1
    for v in d.values():
        ans *= cmb(v+n-1, n-1, M)
        ans %= M
else:
    ans = 1
print(ans%M)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())

def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr

d = factor(m)

M = 10**9+7 # 出力の制限
N = max(d.values())+10+n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

if m!=1:
    ans = 1
    for v in d.values():
        ans *= cmb(v+n-1, n-1, M)
        ans %= M
else:
    ans = 1
print(ans%M)
n = int(input())

d = n//2
print((n-d)/d)

### FIXED CODE ###

n = int(input())

d = n//2
print((n-d)/n)
N, M = map(int, input().split())
if N == 1:
    print(1)
else:
    A = [int(input()) for _ in range(M)]

    S =[0]*(N + 1)
    S[0] = 1
    if A[0] == 1:
        S[1] = 0
    else:
        S[1] = 1

    for i in range(2, N+1):
        if i in A:
            S[i] = 0
        else:
            S[i] = (S[i-1] + S[i-2]) % 1000000007
    print(S[N])


### FIXED CODE ###

N, M = map(int, input().split())
A = set()
for _ in range(M):
    A.add(int(input()))
p = 10 ** 9 + 7
DP = [0 for _ in range(N + 1)]
DP[0] = 1
if 1 in A:
    DP[1] = 0
else: DP[1] = 1
for i in range(2, N+1):
    if i in A:
        DP[i] = 0
    else:
        DP[i] = (DP[i-1] + DP[i-2])%p
print(DP[N])
import bisect

n = 10**5
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

is_simular_2017 = is_prime.copy()

for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if not is_prime[(i + 1) // 2]:
            is_simular_2017[i] = False


simular_2017 = [i for i in range(len(is_simular_2017)) if is_simular_2017[i]]

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    count = 0
    insert_index1 = bisect.bisect_left(simular_2017, l)
    insert_index2 = bisect.bisect_left(simular_2017, r)
    if insert_index2 - insert_index1 != 0:
        print(insert_index2 - insert_index1)
    else:
        print(1 if l == simular_2017[insert_index1] else 0)

### FIXED CODE ###

import bisect

n = 10**5
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False

for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, n + 1, i):
        is_prime[j] = False

num = [0] * (n + 1)

cnt = 0
for i in range(n + 1):
    if is_prime[i] and (i + 1) // 2 > 0:
        if is_prime[(i + 1) // 2]:
            cnt += 1
    num[i] = cnt

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

for l, r in LR:
    print(num[r] - num[l - 1])
while True:
    H, W = map(int, input().split())
    if W == 0 and H == 0:
        break
   for i in range(H):
        print ('#' * W)
    print()

### FIXED CODE ###

while True:
    H, W = map(int, input().split())
    if W == 0 and H == 0:
        break
  
    for i in range(H):
        print ('#' * W)
    print()
N,K=(int(x) for x in input().split())
b=1
a=1
while a=<N:
    b=b+1
    a=K**b
else:
     print(b)

### FIXED CODE ###

N,K=(int(x) for x in input().split())
b=1
a=1
if N==1:
    print(1)
else:
     while a<=N:
          b=b+1
          a=K**b
     else:
          print(b)
N = int(input())
if N <=111:
    print("111")
elif N <=222:
    print("222")
elif N <=333:
    print("333")
elif N <= 444:
    print("444")
elif N <=555:
    print("555")
elif N <=666
    print("666")
elif N <=777:
    print("777")
elif N <=888:
    print("888")
else:
    print("999")

### FIXED CODE ###

N = int(input())
if N <=111:
    print("111")
elif N <=222:
    print("222")
elif N <=333:
    print("333")
elif N <= 444:
    print("444")
elif N <=555:
    print("555")
elif N <=666:
    print("666")
elif N <=777:
    print("777")
elif N <=888:
    print("888")
else:
    print("999")
n=int(input())
h=list(map(int,input().split()))
cost=0
for i in range(n-1):
    if h[i]>h[i+1]:
        cost+=(h[i]-h[i+1])
    cost+=h[n-1]
print(cost)

### FIXED CODE ###

l=list(map(int,input().split()))
l.remove(max(l))
print(int(l[0]*l[1]/2))
N = int(input())
A = B = C = 0

for i in range(N):
  a,b,c = map(int,input())
  A,B,C = max(B + a,C+a),max(A+b,C+b),max(A+c,B+c)
 
print(max(A,B,C))

### FIXED CODE ###

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

dp = [[0,0,0] for _ in range(N)]
dp[0] = li[0]

for i in range(N-1):
  for j in range(3):
    for k in range(3):
      if j == k: continue
      dp[i+1][j] = max(dp[i+1][j], dp[i][k] + li[i+1][j])
print(max(dp[-1]))
import numpy as np
n=int(input())
lx=[]
ly=[]
for i in range(n):
  x,y=map(int,input().split())
  lx.append(x+y)
  ly.append(x-y)
ax,bx,ay,by=max(lx),min(lx),max(ly),min(ly)
print(max(ax-bx,ay-by))

### FIXED CODE ###


n=int(input())
lx=[]
ly=[]
for i in range(n):
  x,y=map(int,input().split())
  lx.append(x+y)
  ly.append(x-y)
ax,bx,ay,by=max(lx),min(lx),max(ly),min(ly)
print(max(ax-bx,ay-by))
a,b=map(int,input().split())
print a*b, 2*a+2*b

### FIXED CODE ###

a,b=map(int,raw_input().split())
print a*b, 2*a+2*b
N, K = map(int, input().split())
for i in range(K):
  D = list(int(input()))
  A = list(map(int, input().split()))
print(N - len(set(A)))

### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    A = []
    for i in range(K):
        d = int(input())
        a = list(map(int, input().split()))
        A.extend(a)
    print(N - len(set(A)))
resolve()
n = int(raw_input()) 

G = [0 for i in range(n)] 
a = [[0 for i in range(n)] for j in range(n)]
dis = [99999 for i in range(n)]
dis[0] = 0


def bfs_visit(s):
    for k in range(n):
      if a[s][k] == 1:
        if dis[k] > dis[s] + 1:
          dis[k] = dis[s] + 1
          bfs_visit(k)

for i in range(n):
    G = map(int, raw_input().split())
    for j in range(G[1]):
        a[G[0]-1][G[2+j]-1] = 1
 

for s in range(n):
    bfs_visit(s)
for s in range(n):
    if dis[s] == 99999:
       dis[s] = -1
for s in range(n):
    print (s+1, d[s])

### FIXED CODE ###

n = int(raw_input())
   
dis = [99999 for i in range(n)]
G = [0 for i in range(n)]
v = [[0 for i in range(n)] for j in range(n)]
   
def BFS(s):
  for e in range(n):
    if v[s][e] == 1:
      if dis[e] > dis[s] + 1:
        dis[e] = dis[s]+1
        BFS(e)
   
for i in range(n):
  G = map(int, raw_input().split())
  for j in range(G[1]):
    v[G[0]-1][G[2+j]-1] = 1
   
dis[0] = 0
for s in range(n):
  BFS(s)
for s in range(n):
  if dis[s] == 99999:
    dis[s] = -1
for s in range(n):
  print'{0} {1}'.format(s+1, dis[s])
N, M = map(int, input().split())
Grap = {j+1:[] for j in range(N)}
memo = {j+1: 0 for j in range(N)} # 各頂点からの最長経路をメモ. -1で初期化.
done = {j+1: False for j in range(N)}
ans = 0

for _ in range(M):
  x, y = map(int, input().split())
  Grap[x].append(y)

#print(memo)
#print(done)
def dp(v):# 頂点nから始まる最長経路を返す.
  if done[v]: 
    return memo[v]
  elif done[v] == False:
    answ = 0
    for to in Grap[v]:
      answ = max(answ, dp(to)+1)
    memo[v] = answ
    done[v] = True
    #print(memo)
    #print(done)
    return answ

for n in range(1,N+1):
  #print(dp(n))
  ans = max(ans, dp(n))
print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
MEMO = [-1 for _ in range(N+1)]

for _ in range(M):
  x, y = map(int, input().split())
  G[x].append(y)


def dp_LP(v):# 頂点nから始まる最長経路を返す.
  if MEMO[v] != -1:
    return MEMO[v]
  else:
    ans = 0
    for i in G[v]:
      ans = max(ans, dp_LP(i)+1)
    MEMO[v] = ans

    return ans



answer = 0
for n in range(1,N+1):
  answer = max(answer, dp_LP(n))
print(answer)