Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03042 (python)

Fixed submission:
S = input()

S_one = int(S[:2])
S_two = int(S[2:])

if S_one == 0:
    if 1 <= S_two <= 12:
        print('YYMM')
    else:
        print('NA')
elif 1 <= S_one <= 12:
    if 1 <= S_two <= 12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
else:
    if 1 <= S_two <= 12:
        print('YYMM')
    else:
        print('NA')

Buggy submission (verdict: Runtime Error):
if A == 0 & B == 0:
    print('NA')
elif 1 <= A <= 12:
    if 1 <= B <= 12:
        print('AMBIGUOUS')
    else:
        print('MMYY')
elif 1 <= B <= 12:
    if 1 <= A <= 12:
        print('AMBIGUOUS')
    else:
        print('YYMM')
else:
    print('NA')
Problem p03127 (python)

Fixed submission:
import fractions
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(n):
    ans = fractions.gcd(ans, a[i])
print(ans)

Buggy submission (verdict: Runtime Error):
import math
n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in range(n):
    ans = math.gcd(ans, a[i])
print(ans)
Problem p03208 (python)

Fixed submission:
n,k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 10

for i in range(n-k+1):
    ans = min(h[i+k-1] - h[i],ans)

print(ans)

Buggy submission (verdict: Runtime Error):
n,k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = h[-1]

for i in range(n-k+1):
    if h[i+k-1] - h[i] < ans:
        ans = h[i+2] - h[i]

print(ans)

Buggy submission (verdict: Runtime Error):
n,k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
ans = 10 ** 5

for i in range(n-k+1):
    if h[i+k-1] - h[i] < ans:
        ans = h[i+2] - h[i]

print(ans)
Problem p03207 (python)

Fixed submission:
n = int(input())
p = sorted([int(input()) for _ in range(n)])
print(sum(p[:-1]) + p[-1]//2)

Buggy submission (verdict: Runtime Error):
n = int(input())
p = sorted([int(input()) for _ in range(n)])
print(p[:-1] + p[-1]//2)
Problem p02933 (python)

Fixed submission:
a=int(input())
s=input()

if a>=3200:
    print(s)
else:
    print("red")

Buggy submission (verdict: Runtime Error):
a=int(input())
s=input()

if a>=3200:
    print(s)
else:
    print(red)
Problem p02676 (python)

Fixed submission:
k = int(input())
s = input()
if k >= len(s):
  print(s)
else:
  print(s[:k]+"...")

Buggy submission (verdict: Runtime Error):
k = int(input())
    s = input()
    if len(s) <= k:
        print(s)
    else:
        print(s[:k]+'...')

Buggy submission (verdict: Runtime Error):
k = int(input())
    s = str(input())
    if len(s) <= k:
        print(s)
    else:
        print(s[:k]+'...')

Buggy submission (verdict: Runtime Error):
k = int(input())
    s = str(input())
    if len(s) <= k:
        print(s)
    else:
        print(s[:k])

Buggy submission (verdict: Runtime Error):
 k = int(input())
    s = str(input())
    if len(s) <= k:
        print(str(s))
    else:
        print(s[:k])
Problem p02699 (python)

Fixed submission:
s,w=input().split()
s=int(s)
w=int(w)
if s>w:
    print("safe")
if w>s:
   print("unsafe")
if w==s:
   print("unsafe")

Buggy submission (verdict: Runtime Error):
   s,w=input().split()
s=int(s)
w=int(w)
if s>w:
    print("safe")
else:
    print("unsafe")
Problem p02679 (python)

Fixed submission:
import sys
from collections import namedtuple, defaultdict
from math import gcd
input = sys.stdin.readline

class Point:
    def __init__(self, x, y):
        g = gcd(abs(x), abs(y))

        x //= g
        y //= g

        if x < 0:
            x *= -1
            y *= -1

        elif x == 0 and y < 0:
            y *= -1

        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f'({self.x}, {self.y})'

def main():
    n = int(input())
    
    p = []
    d = defaultdict(lambda: 0)
    zeros = 0

    for _ in range(n):
        x, y = map(int, input().split())

        if x == 0 and y == 0:
            n -= 1
            zeros += 1
            continue

        p.append(Point(x, y))
        d[p[-1]] += 1

    MOD = 10 ** 9 + 7

    pw = [ pow(2, i, MOD) for i in range(n + 1) ]

    ans = 1
    tot = 0

    for x in d.keys():
        if x.x > 0 and x.y >= 0 and Point(-x.y, x.x) in d:
            s = d[x]
            t = d[Point(-x.y, x.x)]

            tot += s + t
            value = (pw[s] + pw[t] - 1 + MOD) % MOD
            ans = ans * value % MOD

    ans = ans * pw[n - tot] % MOD
    ans = (ans - 1 + MOD + zeros) % MOD

    print(ans)
main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import namedtuple, defaultdict
from math import gcd
input = sys.stdin.readline

class Point:
    def __init__(self, x, y):
        g = gcd(abs(x), abs(y))

        x //= g
        y //= g

        if x < 0:
            x *= -1
            y *= -1

        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f'({self.x}, {self.y})'

def main():
    n = int(input())
    
    p = []
    d = defaultdict(lambda: 0)

    for _ in range(n):
        x, y = map(int, input().split())


        p.append(Point(x, y))
        d[p[-1]] += 1

    # print(d)

    MOD = 10 ** 9 + 7

    pw = [ pow(2, i, MOD) for i in range(n + 1) ]

    ans = 1
    tot = 0

    # pair = 0
    # for x in range(n):
    #     for y in range(x + 1, n):
    #         if p[x].x * p[y].x + p[x].y * p[y].y == 0:
    #             pair += 1

    # print(f'pairs = {pair}')

    for x in d.keys():
        if x.x > 0 and x.y >= 0 and x in d and Point(-x.y, x.x) in d:
            s = d[x]
            t = d[Point(-x.y, x.x)]

            # print(s, t)

            tot += s + t
            value = (pw[s] + pw[t] - 1 + MOD) % MOD
            ans = ans * value % MOD

    # print(f'tot={tot}, n={n}')

    ans = ans * pw[n - tot] % MOD
    ans = (ans - 1 + MOD) % MOD

    print(ans)
main()
Problem p04005 (python)

Fixed submission:
from math import *

a, b, c = map(int, input().split())

def calc(a, b, c):
	r = a // 2

	ans = a * b * c
	for i in range(max(1, r - 5), min(r + 5, a - 1) + 1):
		v1 = i * b * c
		v2 = (a - i) * b * c
		ans = min(ans, abs(v1 - v2))

	return ans

res = a * b * c

res = min(res, calc(a, b, c))
res = min(res, calc(a, c, b))
res = min(res, calc(b, a, c))
res = min(res, calc(b, c, a))
res = min(res, calc(c, a, b))
res = min(res, calc(c, b, a))

print(res)

Buggy submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;

typedef long long int64;

int64 a, b, c, ans = LLONG_MAX;

void calc(int64 a, int64 b, int64 c) {
	int64 r = a / 2;

	for(int64 i = max(1LL, r - 5); i <= min(r + 5, a - 1); i++) {
		int64 v1 = i * b * c;
		int64 v2 = (a - i) * b * c;
		ans = min(ans, llabs(v1 - v2));
	}
}

int main() {
	scanf("%lld%lld%lld", &a, &b, &c);

	calc(a, b, c);
	calc(a, c, b);
	calc(b, a, c);
	calc(b, c, a);
	calc(c, a, b);
	calc(c, b, a);

	printf("%lld\n", ans);
	return 0;
}

Buggy submission (verdict: Runtime Error):
from math import *

a, b, c = map(int, input().split())

def calc(a, b, c):
	r = sqrt(a)

	ans = a * b * c
	for i in range(max(1, r - 5), min(r + 5, a - 1) + 1):
		v1 = i * b * c
		v2 = (a - i) * b * c
		ans = min(ans, abs(v1 - v2))

	return ans

res = a * b * c

res = min(res, calc(a, b, c))
res = min(res, calc(a, c, b))
res = min(res, calc(b, a, c))
res = min(res, calc(b, c, a))
res = min(res, calc(c, a, b))
res = min(res, calc(c, b, a))

print(res)
Problem p02754 (python)

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

if B==0:
    print(N)
elif A==0:
    print(0)
else:
    n = (N//(A+B))
    ans = n * A
    N -= n*(A+B)
    if N >= A:
        ans+=A
    else:
        ans+=N
    print(ans)

Buggy submission (verdict: Runtime Error):
ans = (N // (A+B)) * A
N -= ((A+B) * (N // (A+B)))
if N >= A:
    ans+=A
else:
    ans+=N

print(ans)
Problem p02831 (python)

Fixed submission:
import fractions
A,B = map(int,input().split())
ans = A * B // fractions.gcd(A, B)
print(ans)

Buggy submission (verdict: Runtime Error):
import fractions
A,B = map(int,input.split())
ans = fractions.gcd(A, B)
print(ans)
Problem p02676 (python)

Fixed submission:
k=int(input())
s=input()
if len(s)<=k: print(s)
else: print(s[:k]+"...")

Buggy submission (verdict: Runtime Error):
k=int(input())
s=input()
if s.len()<=k: print(s)
else: print(s[:k]+"...")

Buggy submission (verdict: Runtime Error):
k=int(input)
s=input()
if s.len()<=k: print(s)
else: print(s[:k]+"...")
Problem p02954 (python)

Fixed submission:
if __name__ == '__main__':
  str = input()
  strList = [c for c in str]
  strList.append('e')
  strLength = len(strList)
  rLength = 0
  lLength = 0
  i = 0
  changePoint = 0

  child = [0 for i in range(strLength-1)]

  c = 'R'
  
  while(c != 'e'):
    c = strList[i]
    while(c == 'R'):
      i += 1
      c = strList[i]
      rLength += 1
    
    changePoint = i
    
    while(c == 'L'):
      i += 1
      c = strList[i]
      lLength += 1

    rRight = int(rLength/2)
    rLeft = rLength - rRight

    lLeft = int(lLength/2)
    lRight = lLength - lLeft

    child[changePoint-1] += rLeft + lLeft
    child[changePoint] += rRight + lRight

    rLength = 0
    lLength = 0
  
  for numOfChild in child:
    print(numOfChild, end="")
    print(' ', end="")

Buggy submission (verdict: Runtime Error):
if __name__ == '__main__':
  str = input()
  strList = [c for c in str]
  strList.append('e')
  strLength = len(strList)
  rLength = 0
  lLength = 0
  i = 0
  changePoint = 0

  child = [0 for i in range(strLength)]

  c = 'R'
  
  while(c != 'e'):
    c = strList[i]
    while(c == 'R'):
      i += 1
      c = strList[i]
      rLength += 1
    
    changePoint = i
    
    while(c == 'L'):
      i += 1
      c = strList[i]
      lLength += 1

    rRight = rLength/2
    rLeft = rLength - rRight

    lLeft = lLength/2
    lRight = lLength - lLeft

    child[changePoint-1] += rLeft + lLeft
    child[changePoint-1] += rRight + lRight
  
  for numOfChild in child:
    print(str(numOfChild) + ' ')

Buggy submission (verdict: Runtime Error):
if __name__ == '__main__':
  n = int(input())
  heights = map(int, input().split(' '))

  prev = -100
  answer = 'Yes'

  for height in heights:
    if (height >= prev + 1):
      height = height -1
    elif height == prev:
      height = height
    else:
      answer = 'No'
      print(answer)
      exit()
    prev = height
  print(answer)
Problem p02987 (python)

Fixed submission:
from collections import Counter

arr = list(input())
c = Counter(arr)
print("Yes" if c.most_common()[0][1] == 2 and c.most_common()[1][1] == 2 else "No")

Buggy submission (verdict: Runtime Error):
a, b, c, d = input()

string_set = set(a, b, c, d)

print("YES" if len(string_set) == 2 and not a ^ b ^ c ^ d else "NO")
Problem p02990 (python)

Fixed submission:
def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a


def comb_mod(n, k, mod):
    if k > n:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    fact_n_div_k = (fact_n * pow(fact_k, mod - 2, mod)) % mod
    return (fact_n_div_k * pow(fact_n_k, mod - 2, mod)) % mod


n, k = map(int, input().split())
mod = 10 ** 9 + 7

for i in range(1, k + 1):
    ans = comb_mod(n - k + 1, i, mod) * comb_mod(k - 1, i - 1, mod)
    ans %= mod
    print(ans)

Buggy submission (verdict: Runtime Error):
from scipy.special import comb

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

mod = 10 ** 9 + 7
curr_sum = 0

for i in range(1, k + 1):
    ans = (comb(n - k + i, n - k, exact=True) - curr_sum)
    ans *= comb(k - 1, i - 1, exact=True)
    ans %= mod
    print(ans)
    curr_sum += ans
Problem p03015 (python)

Fixed submission:
def main():

    n = input()
    length = len(n)
    mod = 10 ** 9 + 7

    cnt = 1
    j = n.count("1")

    for digit, num in enumerate(n[::-1], 1):
        if num == "1":
            j -= 1
            cnt += (pow(3, digit - 1, mod) + 1) * pow(2, j, mod)
            cnt %= mod

    print(cnt)


main()

Buggy submission (verdict: Runtime Error):
def main()
    
    n = input()
    length = len(n)
    mod = 10 ** 9 + 7
    
    cnt = 1
    j = n.count("1")
    
    for digit, num in enumerate(n[::-1], 1):
        if num == "1":
            j -= 1
            cnt += (pow(3, digit - 1) + 1) * pow(2, j)
            cnt %= mod
    
    print(cnt)


main()
Problem p03045 (python)

Fixed submission:
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xyz = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y, z in xyz:
        merge(x-1, y-1)
    print(par.count(-1))

union_find()

Buggy submission (verdict: Runtime Error):
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y in xy:
        merge(x-1, y-1)
    print(par.count(-1))


union_find()
Problem p03221 (python)

Fixed submission:
import sys
input = sys.stdin.readline

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

p.sort()
cnt = 0
pre = -1

for city in p:
    if city[0] == pre:
        cnt = cnt + 1
    else:
        pre = city[0]
        cnt = 1

    city.append("{:0>6}{:0>6}".format(city[0], cnt))

p.sort(key = lambda x: x[2])

for city in p:
    print(city[3])

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

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

pre = [[] for _ in range(n)]
p = []

for i in range(m):
    p.append(list(map(int, input().split())))
    pre[p[i][0] - 1].append(p[i][1])

for i in range(m):
    pref = "{:0>6}".format(p[i][0])

    years = pre[p[i][0] - 1]
    years.sort()

    y = years.index(p[i][1]) + 1
    year = "{:0>6}".format(y)
    print(pref + year)
Problem p03242 (python)

Fixed submission:
s = input()

print(s.replace("9", "x").replace("1", "9").replace("x", "1"))

Buggy submission (verdict: Runtime Error):
s = input()

print(s.replace("9", "x").replace("1", "9").replace("x", "1")
Problem p03774 (python)

Fixed submission:
n, m = map(int, input().split())

students = [list(map(int, input().split())) for _ in range(n)]
checkpoints = [list(map(int, input().split())) for _ in range(m)]

for a, b in students:
    min_distance = float("inf")
    min_checkpoint = 0
    for i, cd in enumerate(checkpoints):
        c, d = cd
        if abs(c - a) + abs(d - b) < min_distance:
            min_checkpoint = i + 1
            min_distance = abs(c - a) + abs(d - b)
    print(min_checkpoint)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())

abs = [list(map(int, input().split())) for _ in range(n)]
cds = [list(map(int, input().split())) for _ in range(m)]

for a, b in abs:
  min_distance = float("inf")
  min_checkpoint = 0
  for i, cd in enumerate(cds):
    c, d = cd
    if abs(c - a) + abs(d - b) < min_checkpoint:
      min_checkpoint = i + 1
  print(min_checkpoint)
Problem p03775 (python)

Fixed submission:
def divisible_length(n):
    min_length = len(str(n))
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            min_length = min(min_length, max(len(str(i)), len(str(n // i))))
    return min_length

n = int(input())
print(divisible_length(n))

Buggy submission (verdict: Runtime Error):
def divisible_length(n):
	min_length = len(str(n))
  	for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            min_length = min(min_length, len(str(i)))
            if i != n // i:
	            min_length = min(min_length, len(str(n // i)))
    return min_length


n = int(input())
print(divisible_length(n))
Problem p02676 (python)

Fixed submission:
def main():
    num = int(K)
    if num >= len(S):
        print(S)
    else:
        print(S[:num]+'...')

K = int(input())
S = input()

main()

Buggy submission (verdict: Runtime Error):
def main():
    num = int(K)
    if num >= len(S):
        print(S)
    else:
        print(S[:num]+'...')

K, S = input().split()

main()
Problem p02723 (python)

Fixed submission:
message = input()

temp_list=list(message)


if (temp_list[2] == temp_list[3]) and (temp_list[4] == temp_list[5]):
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
message = input()

temp_list=list(message)


if (temp_list[2] == temp_list[3]) and (temp_list[4] == temp_list[5]):
    print("Yes")
else
    print("No")
Problem p03003 (python)

Fixed submission:
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    if S[0] == S[1] and S[1] == 1 and T[0] == T[1] and T[1] == 1:
        hogehoge
        pass

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


if __name__ == '__main__':
    main()
Problem p03045 (python)

Fixed submission:
import sys
sys.setrecursionlimit(100000)

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

# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

used = set()

for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
for i,p in enumerate(PARENT):
    if root(p) == i:
        cnt += 1
print(cnt)

Buggy submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)
    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = {root(n) for n in used}

ans = (len(uf) + 1) // 2 + (N - len(used))
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

used = set()


def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret


def same(n1, n2):
    return root(n1) == root(n2)


def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2


L = []
for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1

    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)

    if z % 2 == 0:
        unite(x, y)

cnt = 0
uf = [root(n) for n in PARENT]

ansset = set(uf) - (set(range(N)) - used)

ans = (len(ansset) + 1) // 2 + (N - len(used))
print(ans)