Harryxun/stf_run huggingface dataset:
N,C = map(int,input().split())
ST = []
STC = [[] for _ in range(C)]
for _ in range(N):
  s,t,c = map(int,input().split())
  STC[c-1].append([s,t])
for i in range(C):
  STC[i].sort(key=lambda x:x[0])
  s=STC[i][0][0]
  t=STC[i][0][1]
  for j in range(1,len(STC[i])):
    if t==STC[i][j][0]:
      t=STC[i][j][1]
      if j==len(STC[i])-1:
        ST.append([s,0])
        ST.append([t,1])
    else:
      ST.append([s,0])
      ST.append([t,1])
ST.sort(key=lambda x:x[1])
ST.sort(key=lambda x:x[0])

ans =[0]
for st in ST:
  if st[1]==0:
    ans.append(ans[-1]+1)
  else:
    ans.append(ans[-1]-1)
print(max(ans))



### FIXED CODE ###

N,C = map(int,input().split())
ST = []
for _ in range(N):
  s,t,c = map(int,input().split())
  ST.append([s,0,c])
  ST.append([t,1,c])
ST.sort(key=lambda x:x[0])
ST.sort(key=lambda x:x[2])
for i in range(len(ST)-1):
  if ST[i][2]==ST[i+1][2] and ST[i][0]==ST[i+1][0]:
    ST[i][1]=2
    ST[i+1][1]=2

ST.sort(key=lambda x:x[1])
ST.sort(key=lambda x:x[0])

ans =[0]
for st in ST:
  if st[1]==0:
    ans.append(ans[-1]+1)
  elif st[1]==1:
    ans.append(ans[-1]-1)
print(max(ans))
import math
a = int(input())
num = math.gcd(2,a)
print(a*2/num)

### FIXED CODE ###

import fractions
a = int(input())
num = fractions.gcd(2,a)
print(a*2//num)
x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[int(input())])

### FIXED CODE ###

x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(x[int(input())-1])
a = input(),
b = input()

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())
p=list(map(int,input().split()))
l=[]

p.sort()

for i in range(K+1):
  l.append(p[i])
print(sum(l))



### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
l=[]

p.sort()

for i in range(K):
  l.append(p[i])
print(sum(l))
import fractions
import numpy as np
mod=10**9+7
def lcm(a,b):
  s=fractions.gcd(a,b)
  return a*b//s

n=int(input())
a=list(map(int,input().split()))
l=a[0]
for i in a:
    l=lcm(l,i)
a=np.array(a)
print(int(sum(l/a%mod)%mod))

### FIXED CODE ###

from fractions import gcd
MOD=10**9+7
N,*A=map(int,open(0).read().split())

def lcm(a,b):
  return a*b//gcd(a,b)
s=1
for i in A:
  s=lcm(s,i)
s%=MOD
ans=0
for i in A:
  ans+=s*pow(i,MOD-2,MOD)
  ans%=MOD
print(ans)
from collections import deque
n = int(input())
L = []
for i in range(n):
    L.append(input())

ANS = ['blank page']
d = deque()
d.append('blank page')

for i in range(1, n):
    if L[i] == 'use the back button':
        d.pop()
        t = d.pop()
        ANS.append(t)
        d.append(t)
    else:
        s = L[i][6:]
        ANS.append(s)
        d.append(s)
        # s = L[i].split()
        # s = s[2:]
        # ANS.append(' '.join(s))
        # d.append(' '.join(s))

for i in ANS:
    print(i)

### FIXED CODE ###

from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))

# if n == 1:
#     print(1)
#     sys.exit()

d = defaultdict(int)

for key in A:
    d[key] += 1

# if len(d) == 1: # 全部同じ数
#     print(0)
#     sys.exit()

B = list(d)
# B.sort()

# if B[0] == 1: # 1が含まれる場合
#     print(d[1])
#     sys.exit()
# length = len(d)
m = max(d)
flag = [0 for i in range(m+1)]

for i in B:
    t = i
    while t <= m:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1 and d[i] == 1:
        ans += 1

print(ans)
from collections import Counter


N = int(input())
ball = [[] for i in range(N)]
for i in range(N):
    ball[i] = list(map(int, input().split()))

vector = [0] * ((N * (N - 1)) // 2)
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        x = ball[i][0] - ball[j][0]
        y = ball[i][1] - ball[j][1]
        if x < 0:
            x, y = -x, -y
        elif x == 0:
            if y < 0:
                y = -y
        vector[cnt] = x * (10 ** 10) + y
        cnt += 1
C = Counter(vector)
print(N - C.most_common()[0][1])

### FIXED CODE ###

from collections import Counter


N = int(input())
ball = [[] for i in range(N)]
for i in range(N):
    ball[i] = list(map(int, input().split()))

vector = [0] * ((N * (N - 1)) // 2)
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        x = ball[i][0] - ball[j][0]
        y = ball[i][1] - ball[j][1]
        if x < 0:
            x, y = -x, -y
        elif x == 0:
            if y < 0:
                y = -y
        vector[cnt] = x * (10 ** 10) + y
        cnt += 1
C = Counter(vector)
if N == 1:
    print(1)
else:
    print(N - C.most_common()[0][1])
N,H=map(int,input().split())

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

d.sort(key=lambda x:x[0],reverse=True)
a = d[0][0]

d.sort(key=lambda x:x[1],reverse=True)

i=0
dam=0
b_damage=[]

while d[i][1]>a:
    dam+=d[i][1]
    b_damage.append(dam)
    i+=1
    if i==N:
        break

r = H//a + 1
l = 0

def damage(k):
    if k<len(b_damage)+1:
        return b_damage[k-1]
    else:
        l=k-len(b_damage)
        return b_damage[-1]+a*l


while r-l!=1:
    mid=(r+l)//2
    dam = damage(mid)
    if dam >= H:
        r=mid
    else:
        l=mid
print(r)




### FIXED CODE ###

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

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

d.sort(key=lambda x:x[0],reverse=True)
a = d[0][0]

d.sort(key=lambda x:x[1],reverse=True)

i=0
dam=0
b_damage=[]

while d[i][1]>a:
    dam+=d[i][1]
    b_damage.append(dam)
    i+=1
    if i==N:
        break

r = H//a + 1
l = 0

def damage(k):
    if k<len(b_damage)+1:
        return b_damage[k-1]
    elif len(b_damage)==0:
        return a*k
    else:
        l=k-len(b_damage)
        return b_damage[-1]+a*l


while r-l!=1:
    mid=(r+l)//2
    dam = damage(mid)
    if dam >= H:
        r=mid
    else:
        l=mid
print(r)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


import math

A, B, C = input_int()

migi = math.sqrt(C)

hidari = math.sqrt(A) + math.sqrt(B)

if hidari < migi:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

from decimal import *

getcontext().prec = 28      # デフォルト28桁のところを20桁にする


A, B, C = input_int()

A = Decimal(A).sqrt()
B = Decimal(B).sqrt()
C = Decimal(C).sqrt()



if (A+B) < C:
    print("Yes")
else:
    print("No")
n = int(input())
v = [int(i) for i in input().split()]
m = n//2

a = [v[2*i] for i in range(0,m)]
b = [v[2*i+1] for i in range(0,m)]

def mode(arr):
        r = [0] * (max(arr) + 1)
        for a in arr:
            r[a] += 1
        return r.index(max(r))

A = mode(a)
B = mode(b)

if v.remove(A) == []:
    print(m)
    exit()
if A == B:
    if a.count(A) < b.count(B):
        C = mode(a.remove(A))
        print(n - a.count(C) - b.count(B))
    else:
        if b.count(B) == m:
            print(n-m)
        else:
            C = mode(b.remove(B))
            print(n - a.count(A) - b.count(C))
else:
    print(n - a.count(A) - b.count(B))

### FIXED CODE ###

n = int(input())
v = [int(i) for i in input().split()]
m = n//2

a = [v[2*i] for i in range(0,m)]
b = [v[2*i+1] for i in range(0,m)]

def mode(arr):
        r = [0] * (max(arr) + 1)
        for a in arr:
            r[a] += 1
        return r.index(max(r))

A = mode(a)
B = mode(b)

v.remove(A)

if v == []:
    print(m)
    exit()
if A == B:
    if a.count(A) < b.count(B):
        a.remove(A)
        C = mode(a)
        print(n - a.count(C) - b.count(B))
    else:
        if b.count(B) == m:
            print(n - m)
        else:
            if a.count(A) == b.count(B):
                t = a.count(A)
                a.remove(A)
                b.remove(B)
                D = mode(a)
                E = mode(b)
                if a.count(D) > b.count(E):
                    print(n - t - a.count(D))
                else:
                    print(n - t - b.count(E))
            else:
                b.remove(B)
                C = mode(b)
                print(n - a.count(A) - b.count(C))
else:
    print(n - a.count(A) - b.count(B))
inf = 1e10
n,m = map(int,raw_input().split())
edge = [map(int,raw_input().split()) for i in range(m)]
d = [[inf]*n for i in range(n)]
for i in range(m):
	d[0] = 0
	while 1:
		update = False
		a,b,c = edge[i]
		if d[a] != inf and d[b] > d[a] - c:
			d[b] = d[a] - c
			update = True
		if not update: break
print abs(d[n-1])

### FIXED CODE ###

inf = 1e9
n,m = map(int,raw_input().split())
edge = [map(int,raw_input().split()) for i in range(m)]
d = [inf]*n
d[0] = 0
while 1:
	update = 0
	for i in range(m):
		a,b,c = edge[i]
		if d[a] != inf and d[b] > d[a] - c:
			d[b] = d[a] - c
			update = 1
	if update == 0: break
print abs(d[n-1])
A=input()
for i in range(3):
  if A[i]=='1':
    A[i]='9'
  else if A[i]=='9':
    A[i]='1'
print(A)

### FIXED CODE ###

n = input()
for c in n:
    if (c == '1'):
        print('9', end='')
    elif (c == '9'):
        print('1', end='')
    else:
        print(c, end='')
print()
N = int(input())
X = [int(_) for _ in input().split()]
L = sorted(X)

small = L[N//2]
large = L[N//2+1]

for i in X:
    if i <= small:
        print(large)
    else:
        print(small)

### FIXED CODE ###

N = int(input())
X = [int(_) for _ in input().split()]
L = sorted(X)

small = L[N//2-1]
large = L[N//2]

for i in X:
    if i <= small:
        print(large)
    else:
        print(small)
s=input()
t=input()
n=len(s)

dic={}
ans='Yes'
for i in range(n):
    if s[i] in dic:
        if dic[t[i]]==t[i]:
            continue
        else:
            ans='No'
            break
    
    if t[i] not in dic:
        dic[t[i]]=s[i]
    else:
        if dic[t[i]]==s[i]:
            continue
        else :
            ans='No'
            break

print(ans)

### FIXED CODE ###

s=input()
t=input()
n=len(s)

dic={}
ans='Yes'
for i in range(n):
    if t[i] not in dic:
        dic[t[i]]=s[i]
    
    else:
        if dic[t[i]]==s[i]:
            continue
        else :
            ans='No'
            break
    
if len(dic)!=len(set(dic.values())):
    ans='No'
print(ans)
print(input()[::-3]))

### FIXED CODE ###

print(input()[::-1])
s = input()
if s <= '2019/04/19':
  print(Heisei)
else:
  print(TDB)

### FIXED CODE ###

a = list(map(int,input().split("/")))
if a[1] > 4:
  print("TBD")
else:
  print("Heisei")
n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].append(b-1)

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def spread(pi):
  for i in t[pi]:
    c[i] += c[pi]
    spread(i)

spread(0)

print(*c)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].append(b-1)
  t[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def dsf(ci,pi):
  for i in t[ci]:
    if i != pi:
      c[i] += c[ci]
      dsf(i, ci)

dsf(0,-1)

print(*c)
d,t,s = map(int,input().split())
if d <= s * t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()
ls = []
for i in range(len(s) - len(t) + 1):
    ls.append(s[i:i+len(t)])
now = 0
minimum = len(t)
for i in range(len(ls)):
    now = 0
    for j in range(len(t)):
        if t[j] == ls[i][j]:
            now += 1
    if len(t) - now < minimum:
        minimum = len(t) - now
print(minimum)
r  = int(input())
print(math.pi * 2 * r)

### FIXED CODE ###

import math

r  = int(input())
print(math.pi * 2 * r)
S = input()
k = int.input()
if S.len()<=K:
  print(S)
else:
  print(S[:K]+"...")
 

### FIXED CODE ###

k = int(input())
S = input()

if len(S)<=k:
  print(S)
else:
  print(S[:k]+"...")
while True:
    try:
        a, b = map(int, raw_input().split())
        def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a%b)
        g = gcd(a,b)
        l = a*b/gcd(a,b)
        print g, l

### FIXED CODE ###

while True:
    try:
        a, b = map(int, raw_input().split())
        def gcd(a, b):
            if b == 0:
                return a
            else:
                return gcd(b, a%b)
        g = gcd(a,b)
        l = a*b/g
        print g, l
    except:
        break
a=int(input())
ans=0
for i in range(1,n+1):
  num=n//i
  ans+=((num+1)//2)*i
print(ans)

### FIXED CODE ###

a=int(input())
ans=0
for i in range(1,a+1):
  num=a//i
  ans+=(((num+1)*num)//2)*i
print(ans)
n,d=map(int,input().split())
count=0
for i in range(n):
  x,y = map(int, input().split())
  if x**2+y**2<=d**2:
  count=+1
print(count)

### FIXED CODE ###

import math
 
n,d=map(int,input().split())
count=0
for i in range(n):
  x,y = map(int, input().split())
  if math.sqrt((x**2)+(y**2))<=d:
   count+=1
print(count)
ans = 0
y = []
z = []
for i in range(5):
    X = int(input())
    if X % 10 != 0:
        y.append(10 - X%10)
    z.append(X)
print(sum(z) + sum(y) - max(y))

### FIXED CODE ###

List= [int(input()) for i in range(5)]
amari =9
time = 0
flag = False;
for i in List:
    if(i%10 != 0):
        time += 10 - i%10
        amari = min(amari,i%10)
        flag = True
output = sum(List) + time
if(flag):
    output -= 10 - amari
print(output)
from collections import deque
inf = 1000000000
h, w = map(int, input().split())
root = [[-np.inf]*w for i in range(h)]
root[0][0] = 1
s = [[] for i in range(h)]

cnt = 0
for i in range(h):
    s[i] = input()
    for j in range(w):
        if s[i][j] == '#': cnt+=1
dw = [-1, 0, 1, 0]
dh = [0, 1, 0, -1]
que = deque()
que.append([0, 0])
while que:
    x, y = que.pop()
    for dx, dy in zip(dw, dh):
        nx, ny = x+dx, y+dy
        if 0<=nx<w and 0<=ny<h and root[ny][nx]<=0 and s[ny][nx]=='.':
                que.append([nx, ny])
                root[ny][nx] = root[y][x] + 1
if root[h-1][w-1]<0:
    print(-1)
else:
    print(h*w - cnt - root[h-1][w-1])

### FIXED CODE ###

from collections import deque
inf = 1000000000
h, w = map(int, input().split())
root = [[-1]*w for i in range(h)]
root[0][0] = 1
s = [[] for i in range(h)]

cnt = 0
for i in range(h):
    s[i] = input()
    for j in range(w):
        if s[i][j] == '#': cnt+=1
dw = [-1, 0, 1, 0]
dh = [0, 1, 0, -1]
que = deque()
que.append([0, 0])
while len(que)>0:
    x, y = que.popleft()
    for dx, dy in zip(dw, dh):
        nx, ny = x+dx, y+dy
        if 0<=nx<w and 0<=ny<h and root[ny][nx]==-1 and s[ny][nx]=='.':
                que.append([nx, ny])
                root[ny][nx] = root[y][x] + 1
if root[h-1][w-1]<0:
    print(-1)
else:
    print(h*w - cnt - root[h-1][w-1])
S = input()
T = input()
slide_num = len(S) - len(T)
if slide_num < 0:
    exit()
for slide in range(slide_num+1):
    for j in range(len(S)-slide):
        if S[j+slide] == T[j] or S[j+slide] == '?':
            None
        else:
            break
    else:
        print((S[:2] + T + S[2+len(T):]).replace('?', 'a'))
        exit()
print('UNRESTORABLE')

### FIXED CODE ###

S = input()
T = input()
L = []
slide_num = len(S) - len(T)
if slide_num < 0:
    print('UNRESTORABLE')
    exit()
for slide in range(slide_num+1):
    for j in range(len(T)):
        if S[j+slide] == T[j] or S[j+slide] == '?':
            None
        else:
            break
    else:
        L.append((S[:slide] + T + S[slide+len(T):]).replace('?', 'a'))

if L:
    print(L.pop())
else:
    print('UNRESTORABLE')
import sys
sys.setrecursionlimit(10**6) 
input = sys.stdin.readline 
N,Q= map(int, input().split())
es=[]
ope=[]
for _ in range(N-1):
    a,b=map(int, input().split())
    es.append((a,b))
for _ in range(Q):
    p,x=map(int, input().split())
    ope.append((p,x))
point=[0]*N
import numpy as np
point=np.array(point)
nodes=np.eye(N, dtype=int)
for e in es:
    if sum(nodes[e[0]-1])>=sum(nodes[e[1]-1]):
        nodes[e[0]-1][e[1]-1]=1
        nodes[:,e[1]-1]=np.logical_or(nodes[:,e[1]-1],nodes[:,e[0]-1])
    else:
        nodes[e[1]-1][e[0]-1]=1
        nodes[:,e[0]-1]=np.logical_or(nodes[:,e[1]-1],nodes[:,e[0]-1])
for o in ope:
    point+=nodes[o[0]-1]*o[1]
string=""
for i in range(N):
    string+=str(int(point[i]))+" "
print(string)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

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

def dfs(now , prev = -1):
    for next in graph[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next , now)

dfs(0)
print(*point)
# coding: UTF8
N = 3
# N = int(input())

str = [input() for i in range(N)]
# print str
a = str[0]
b = str[1]
h = str[2]

S = (a + b) * h // 2
print(S)


### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
 
print(int((a+b)*h//2))
n,k = map(int,input().split())
p = [int(i)-1 for i in input().split()]
c = list(map(int,input().split()))

def calc_score(x):
    
    score = 0
    score_max = -10**10
    score_list = [-float("inf")]*n
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_max = max(score_max, score)
            score_list[cnt-1] = score
        else:
            return score_max
            
    if score>0:
        return max(score_list[:k%cnt]) + (k//cnt) * score
    else:
        return score_max

ans = max(calc_score(i) for i in range(n))
print(ans)

### FIXED CODE ###

#出来るだけループして端数を全部みるだとうまくいかない（最初と最後に負のスコアが固まっている場合など）

from numba import njit,i8
import numpy as np


n,k = map(int,input().split())
p = np.array([int(i)-1 for i in input().split()],np.int64)
c = np.array(list(map(int,input().split())),np.int64)

@njit(i8(i8,i8[:],i8[:]), cache = True)
def calc_score(x,p,c):
    n = p.size
    score = 0
    score_list = np.zeros(n,np.int64)
    cnt = 0
    visit = [0]*n
    while not visit[p[x]]:
        x = p[x]
        visit[x] = 1
        cnt += 1
        if cnt<=k:
            score += c[x]
            score_list[cnt-1] = score
        else:
            return score_list[:k].max()
    
    if score>0:
        tmp = np.arange(cnt)
        return (score_list[tmp] + ((k-1-tmp)//cnt) * score).max()
    else:
        return score_list[:cnt].max()

ans = max(calc_score(i,p,c) for i in range(n))
print(ans)
while list[0] != 0 or list[1] != 0:
    list = [x for x in input().split( )]
    print(' '.join(map(str,sorted(list))))




### FIXED CODE ###

while True:
    l = [int(x) for x in input().split( )]
    if l == [0,0]:
        break
    else:
        l.sort()
        print(*l)
n = int(input())
a = [int(i) for i in input().split()]
 
if 0 in a: 
    ans = 0
else:
    ans = 1
    for ai in a:
        ans *= ai
        if ans > 10**18:
            ans = -1
            break
print(prod)

### FIXED CODE ###

A,B = map(int, input().split())
print(A*B)
dic = {"A" : "T", "T" : "A", "C" : "G", "G" : "C"}
print(dict[input()])

### FIXED CODE ###

dic = {"A" : "T", "T" : "A", "C" : "G", "G" : "C"}
print(dic[input()])
S = input()
c = 0
cmax = 0
for c in S:
  if c == "R":
    c += 1
    if cmax < c:
      cmax = c
  else:
    c = 0
print(cmax)

### FIXED CODE ###

S = input()
cnt = 0
cmax = 0
for c in S:
  if c == "R":
    cnt += 1
    if cmax < cnt:
      cmax = cnt
  else:
    cnt = 0
print(cmax)
import heapq
from collections import deque

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

info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]

for b, c in info:
    tree[b].append(c)
    tree[c].append(b)

visited = [False] * n
group = []
for i in range(n):
    if visited[i]:
        continue
    q = deque([i])
    visited[i] = True
    tmp = [a[i]]
    while q:
        pos = q.pop()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            q.append(next_pos)
            tmp.append(a[next_pos])
    group.append(tmp)

for i in range(len(group)):
    group[i] = sorted(group[i])
    
ans = 0
cnt = len(group)*2 - 2

if cnt == 0:
    print(0)
    exit()
    
for i in range(len(group)):
    ans += group[i][0]
    cnt -= 1
    group[i][0] = 10**9 + 7

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)

for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappush(q)
print(ans)
    

### FIXED CODE ###

import heapq
from collections import deque


n, m = map(int, input().split())
a = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]

for b, c in info:
    tree[b].append(c)
    tree[c].append(b)

visited = [False] * n
group = []
for i in range(n):
    if visited[i]:
        continue
    q = deque([i])
    visited[i] = True
    tmp = [a[i]]
    while q:
        pos = q.pop()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            q.append(next_pos)
            tmp.append(a[next_pos])
    group.append(tmp)

for i in range(len(group)):
    group[i] = sorted(group[i])

ans = 0
cnt = len(group)*2 - 2

if cnt == 0:
    print(0)
    exit()
    
for i in range(len(group)):
    ans += group[i][0]
    cnt -= 1
    group[i][0] = 10**9 + 7

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)

for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappop(q)
print(ans)
a, b = map(int, input().split())
C = []
for _ in range(a):
  c, t = map(int, input().split())
  if t <= b:
    C.append(c)
print(min(C))

### FIXED CODE ###

a, b = map(int, input().split())
C = []
for _ in range(a):
  c, t = map(int, input().split())
  if t <= b:
    C.append(c)
if not C ==[]:
  print(min(C))
else:
  print("TLE")
#!/usr/bin/env python3

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

ret = 0
for l in range(0, N):
    Sum = 0
    for r in range(l, N):
        Sum += A[r]
        if Sum % M == 0:
            ret += 1
print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

[N, K] = [int(x) for x in input().split(" ")]
print(0 if (N % K == 0) else 1)
s = list(int(input()))

a1 = [0, 1] * (len(s) // 2)
a2 = [1, 0] * (len(s) // 2)
if len(s) % 2 == 1:
    a1.append(0)
    a2.append(1)

count = 0
l = [0] * 2
for i in range(len(s)):
    if s[i] != a1[i]:
        l[0] += 1
    if s[i] != a2[i]:
        l[1] += 1
print(min(l))

### FIXED CODE ###

st = list(input())
s = [int(i) for i in st]

a1 = [0, 1] * (len(s) // 2)
a2 = [1, 0] * (len(s) // 2)
if len(s) % 2 == 1:
    a1.append(0)
    a2.append(1)

count = 0
l = [0] * 2
for i in range(len(s)):
    if s[i] != a1[i]:
        l[0] += 1
    if s[i] != a2[i]:
        l[1] += 1
print(min(l))
X = int(input())
def dfs(t, x):
    global X
    if t>X:
        return X
    if x==X:
        return t-1
    return min(dfs(t+1,x+t),dfs(t+1,x))
print(dfs(0,0))

### FIXED CODE ###

X = int(input())
sum_time = 0
for i in range(X):
    sum_time+=(i+1)
    if sum_time>=X:
        print(i+1)
        break
#B - Power Socket
A,B = input().split()
A = int(A)
B = int(B)

count = 0
total_plug = 1
for i in range(1,20):
    count += 1
    total_plug += (A - 1)
    if B <= total_plug:
        break
        
print(count)

### FIXED CODE ###

S = input()
T = input()
count = 0
for i in range(3):
  if S[i] == T[i]:
    count += 1
print(count)