Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
inf = float('inf')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    u = 0

    for i in range(n - 1):
        for v, cost in Adj[u]:
            if d[u] + cost < d[v]:
                p[v] = u
                d[v] = d[u] + cost

        min_n = 0
        min_w = inf
        for v in range(n):
            if not checked[v] and d[v] < min_w:
                min_n = v
                min_w = d[v]

        u = min_n
        checked[u] = True

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n):
        u, k, *line = [int(i) for i in input().split()]
        for j in range(k):
            Adj[u].append((line[2*j], line[2*j + 1]))

    # debug(Adj, locals())

    d = SSSP(n, Adj)

    for i in range(n):
        print(i, d[i])

if __name__ == '__main__':
    solve()

Fixed submission:
import sys
import heapq
from collections import namedtuple
inf = float('inf')
Node = namedtuple('Node', 'd, no')

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def SSSP(n, Adj):
    d = [inf] * n
    p = [-1] * n
    checked = [False] * n
    d[0] = 0
    checked[0] = True
    heap = [Node(d[0], 0)]

    while heap:
        u = heapq.heappop(heap)

        if d[u.no] < u.d:
            continue

        checked[u.no] = True

        for v, cost in Adj[u.no]:
            if not checked[v] and d[u.no] + cost < d[v]:
                d[v] = d[u.no] + cost
                p[v] = u.no
                heapq.heappush(heap, Node(d[v], v))

    return d

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n):
        u, k, *line = [int(i) for i in input().split()]
        for j in range(k):
            Adj[u].append((line[2*j], line[2*j + 1]))

    # debug(Adj, locals())

    d = SSSP(n, Adj)

    for i in range(n):
        print(i, d[i])

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import math
a,b = map(int,input().split())
print(math.gcd(a,b))

Fixed submission:
import sys

def solve():
    a, b = map(int, input().split())
    ans = gcd(a, b)
    print(ans)

def gcd(a, b):
    return gcd(b, a % b) if b else a

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
 
inf = 10**9 + 1

def solve():
    n = int(stdin.readline())
    R = [int(stdin.readline()) for i in range(n)]

    ans = max_profit2(n, R)

    print(ans)

def max_profit(n, R):
    max_d = -inf
    min_v = R[0]

    for i in range(1, n):
        max_d = max(max_d, R[i] - min_v)
        min_v = min(min_v, R[i])

    return max_d

def max_profit2(n, R):
    max_dif = -inf

    for left in range(n):
        for j in range(left + 1, n):
            max_dif = max(max_dif, R[j] - R[left])

    return max_dif
    
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None
 
if __name__ == '__main__':
    solve()

Fixed submission:
from sys import stdin
 
inf = 10**9 + 1

def solve():
    n = int(stdin.readline())
    max_d = -inf
    min_v = inf * 2

    for i in range(n):
        r = int(stdin.readline())

        max_d = max(max_d, r - min_v)
        min_v = min(min_v, r)

    print(max_d)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None
 
if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):

def InsertionSort(A, n, g):
    cnt = 0

    for i in range(g, n):
        v = A[i]
        j = i - g

        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1

        A[j + g] = v

    return cnt

def ShellSort(A, n):
    total_cnt = 0

    G = [1]
    span = 2

    while span < len(A):
        G.append(span)
        span *= 2

    G.reverse()

    m = len(G)

    for i in range(m):
        total_cnt += InsertionSort(A, n, G[i])

    return m, G, total_cnt

n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

m, G, cnt = ShellSort(A, n)

print(m)
print(*G)
print(cnt)

for a in A:
    print(a)

Fixed submission:

def InsertionSort(A, n, g):
    cnt = 0

    for i in range(g, n):
        v = A[i]
        j = i - g

        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1

        A[j + g] = v

    return cnt

def ShellSort(A, n):
    tot_cnt = 0
    G = [1]
    span = 4

    while span < n:
        G.append(span)
        span = span * 3 + 1

    G.reverse()
    m = len(G)

    for g in G:
        tot_cnt += InsertionSort(A, n, g)

    return m, G, tot_cnt


n = int(input())
A = []

for i in range(n):
    A.append(int(input()))

m, G, tot_cnt = ShellSort(A, n)

print(m)
print(*G)
print(tot_cnt)
print(*A, sep = "\n")
Buggy python submission (verdict: Runtime Error):

from collections import deque

n = int(input())
linked_list = deque([])

for i in range(n):
    line = input().split()
    cmd = line[0]

    if len(line) == 2:
        value = line[1]

    if cmd == "insert":
        linked_list.insert(0, value)
    elif cmd == "delete":
        linked_list.remove(value)
    elif cmd == "deleteFirst":
        linked_list.popleft()
    elif cmd == "deleteLast":
        linked_list.pop()

print(*linked_list)

Fixed submission:

import sys
from collections import deque

n = int(sys.stdin.readline())

inputs = []

for i in range(n):
    inputs.append(sys.stdin.readline().split())

linked_list = deque([])

for line in inputs:
    cmd = line[0]

    if len(line) == 2:
        value = line[1]

    if cmd == "insert":
        linked_list.appendleft(value)
    elif cmd == "delete":
        if value in linked_list:
            linked_list.remove(value)
    elif cmd == "deleteFirst":
        linked_list.popleft()
    elif cmd == "deleteLast":
        linked_list.pop()

print(*linked_list)

Buggy python submission (verdict: Runtime Error):

from collections import deque

n = int(input())
linked_list = deque([])

for i in range(n):
    line = input().split()
    cmd = line[0]

    if len(line) == 2:
        value = line[1]

    if cmd == "insert":
        linked_list.appendleft(value)
    elif cmd == "delete":
        linked_list.remove(value)
    elif cmd == "deleteFirst":
        linked_list.popleft()
    elif cmd == "deleteLast":
        linked_list.pop()

print(*linked_list)

Fixed submission:

import sys
from collections import deque

n = int(sys.stdin.readline())

inputs = []

for i in range(n):
    inputs.append(sys.stdin.readline().split())

linked_list = deque([])

for line in inputs:
    cmd = line[0]

    if len(line) == 2:
        value = line[1]

    if cmd == "insert":
        linked_list.appendleft(value)
    elif cmd == "delete":
        if value in linked_list:
            linked_list.remove(value)
    elif cmd == "deleteFirst":
        linked_list.popleft()
    elif cmd == "deleteLast":
        linked_list.pop()

print(*linked_list)
Buggy python submission (verdict: Time Limit Exceeded):
danmen = input()
depth = []
tmp_dpt = 0

for line in danmen:
    depth.append(tmp_dpt)

    if line == "\\":
        tmp_dpt -= 1
    elif line == "/":
        tmp_dpt += 1

depth.append(tmp_dpt)

# print(depth)

i = 0
L = []

while i < len(danmen):
    if danmen[i] == "\\":
        if depth[i] in depth[i + 1:]:
            stack = 0
            area = 0

            for line in danmen[i:]:
                if line == "\\":
                    area += 1 + 2 * stack
                    stack += 1
                elif line == "/":
                    stack -= 1
                    area += 1 + 2 * stack
                else:
                    area += 2 * stack

                if stack == 0:
                    break

            if area != 0:
                L.append(area // 2)
                i += depth[i + 1:].index(depth[i])
        
    i += 1

print(sum(L))
print(len(L), *L)

Fixed submission:

danmen = input()

down = []
edge = []
pool = []

for (i, line) in enumerate(danmen):
    if line == "\\":
        down.append(i)
    elif down and line == "/":
        left = down.pop()
        area = i - left

        while edge:
            if edge[-1] < left:
                break
            edge.pop()
            area += pool.pop()

        edge.append(left)
        pool.append(area)

print(sum(pool))
print(len(pool), *pool)
Buggy python submission (verdict: Time Limit Exceeded):

def BinarySearch(n, S, t):
    """ ????????????????????? """
    left = 0
    right = n - 1

    while left <= right:
        center = (left + right) // 2

        if t > S[center]:
            left = center + 1
        elif t < S[center]:
            right = center - 1
        else:
            return center

    return -1

n = int(input())
S = [int(s) for s in input().split()]

q = int(input())
T = [int(t) for t in input().split()]

cnt = 0

for t in T:
    if BinarySearch(n, S[:], t) != -1:
        cnt += 1

print(cnt)

Fixed submission:
import sys

def BinarySearch(S, n, t):
    bottom = 0
    top = n - 1

    while bottom <= top:
        center = (bottom + top) // 2

        if S[center] == t:
            return center
        elif S[center] < t:
            bottom = center + 1
        else:
            top = center - 1

    return -1


n = int(sys.stdin.readline())
S = [int(s) for s in sys.stdin.readline().split()]

q = int(sys.stdin.readline())
T = {int(t) for t in sys.stdin.readline().split()}

ans = sum(BinarySearch(S, n, t) != -1 for t in T)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = [int(s) for s in input().split()]

q = int(input())
T = [int(t) for t in input().split()]
 
cnt = sum(t in S for t in T)
 
print(cnt)

Fixed submission:
import sys

def BinarySearch(S, n, t):
    bottom = 0
    top = n - 1

    while bottom <= top:
        center = (bottom + top) // 2

        if S[center] == t:
            return center
        elif S[center] < t:
            bottom = center + 1
        else:
            top = center - 1

    return -1


n = int(sys.stdin.readline())
S = [int(s) for s in sys.stdin.readline().split()]

q = int(sys.stdin.readline())
T = {int(t) for t in sys.stdin.readline().split()}

ans = sum(BinarySearch(S, n, t) != -1 for t in T)

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

def h1(key):
    return key % M

def h2(key):
    return 1 + key % (M - 1)

def H(key, i):
    return (h1(key) + i * h2(key)) % M

def my_insert(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] is None:
            dic[j] = key
            return j
        else:
            i += 1

def my_search(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] == key:
            return True
        elif dic[j] is None or i >= M:
            return False
        else:
            i += 1

def str2int(s):
    res = s

    res = res.replace("A", "1")
    res = res.replace("C", "2")
    res = res.replace("G", "3")
    res = res.replace("T", "4")

    return int(res)

M = 1_000_003
dic = [None] * M

n = int(sys.stdin.readline())

for k in range(n):
    cmd, s = sys.stdin.readline().split()

    if cmd == "insert":
        my_insert(dic, str2int(s))
    else:
        print("yes" if my_search(dic, str2int(s)) else "no")

Fixed submission:
import sys

def h1(key):
    return key % M

def h2(key):
    return 1 + key % (M - 1)

def H(key, i):
    return (h1(key) + i * h2(key)) % M

def my_insert(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] is None:
            dic[j] = key
            return j
        else:
            i += 1

def my_search(dic, key):
    i = 0

    while 1:
        j = H(key, i)
        if dic[j] == key:
            return True
        elif dic[j] is None or i >= M:
            return False
        else:
            i += 1

def str2int(s):
    res = s

    res = res.replace("A", "1")
    res = res.replace("C", "2")
    res = res.replace("G", "3")
    res = res.replace("T", "4")

    return int(res)

M = 1000003
dic = [None] * M

n = int(sys.stdin.readline())

for k in range(n):
    cmd, s = sys.stdin.readline().split()

    if cmd == "insert":
        my_insert(dic, str2int(s))
    else:
        print("yes" if my_search(dic, str2int(s)) else "no")
Buggy python submission (verdict: Runtime Error):
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return True

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return False
    pass

# ??\?????¨
n, k = map(int, sys.stdin.readline().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    capable = [None] * (max_p - min_p + 1)
    capable[0] = False
    capable[-1] = True

    bottom = 0
    top = len(capable)

    while bottom < top:
        mid = (bottom + top) // 2

        if capable[mid] is None:
            capable[mid] = is_capable(n, k, w, min_p + mid)

        if capable[mid] == True:
            if capable[mid - 1] is None:
                capable[mid - 1] = is_capable(n, k, w, min_p + mid - 1)

            if capable[mid - 1] == False:
                bnd = mid
                break
            else:
                top = mid - 1
        elif capable[mid] == False:
            if capable[mid + 1] is None:
                capable[mid + 1] = is_capable(n, k, w, min_p + mid + 1)

            if capable[mid + 1] == True:
                bnd = mid + 1
                break
            else:
                bottom = mid + 2

    ans = min_p + bnd

    print(ans)
    # print(capable)

Fixed submission:
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return i

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return i
    pass

# ??\?????¨
n, k = map(int, sys.stdin.readline().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    # print(max_p, min_p)
    # sys.exit(0)
    
    bottom = min_p
    top = max_p

    while top - bottom > 1:
        mid = (bottom + top) // 2

        if is_capable(n, k, w, mid) == n:
            top = mid
        else:
            bottom = mid

    print(top)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin, stderr

def rec(A, i, m):
    if i == 0:
        return m == 0 or A[i] == m

    return rec(A, i - 1, m) or rec(A, i - 1, m - A[i])

n = int(input())
A = [int(i) for i in input().split()]
q = int(input())
M = [int(i) for i in input().split()]

for m in M:
    if rec(A, n - 1, m):
        print('yes')
    else:
        print('no')

Fixed submission:
def solve():
    def dfs(idx, end, value, is_make):
        if idx == end:
            if value > 2000:
                return
            
            is_make[value] = True
            return

        dfs(idx + 1, end, value + A[idx], is_make)
        dfs(idx + 1, end, value, is_make)

    n = int(input())
    A = [int(i) for i in input().split()]
    q = int(input())
    M = [int(i) for i in input().split()]

    is_make = [False] * (2000 + 1)
    dfs(0, n, 0, is_make)

    for m in M:
        print('yes' if is_make[m] else 'no')

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = []
    R = []

    for i in range(n1):
        L.append(A[left + i])

    for j in range(n2):
        R.append(A[mid + j])

    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    return right - left

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0

n = int(input())
S = [int(s) for s in input().split()]

ans = mergeSort(S, 0, n)

print(*S)
print(ans)

Fixed submission:

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid] + [float("inf")]
    R = A[mid:right] + [float("inf")]

    i = 0
    j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    return right - left

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0

n = int(input())
S = [int(s) for s in input().split()]

ans = mergeSort(S, 0, n)

print(*S)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def insertHeap(H, A, key):
    A.append(key)
    i = H + 1

    while i > 1 and A[i] > A[i // 2]:
        A[i], A[i // 2] = A[i // 2], A[i]
        i //= 2

def popHeap(H, A):
    max_ = A[1]

    A[1] = A[H]
    A.pop()
    maxHeapify(H - 1, A, 1)

    return max_

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(H, A, largest)

def buildMaxHeap(H, A):
    for i in range(H // 2, 0, -1):
        maxHeapify(H, A, i)

H = 0
A = [None]

while 1:
    cmd = sys.stdin.readline().split()
    # print(A, file=sys.stderr)

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(popHeap(H, A))
        H -= 1
    else:
        insertHeap(H, A, int(cmd[1]))
        H += 1

Fixed submission:
import sys
from heapq import heappush, heappop

heap = []

while 1:
    cmd = sys.stdin.readline().split()

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(-heappop(heap))
    else:
        heappush(heap, -int(cmd[1]))

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def insertHeap(H, A, key):
    A[H] = key
    i = H

    while i > 1 and A[i] > A[i // 2]:
        A[i], A[i // 2] = A[i // 2], A[i]
        i //= 2

def popHeap(H, A):
    max_ = A[1]

    A[1] = A[H]
    maxHeapify(H - 1, A, 1)

    return max_

def maxHeapify(H, A, i):
    left = 2 * i
    right = 2*i + 1

    if left <= H and A[left] > A[i]:
        largest = left
    else:
        largest = i
    if right <= H and A[right] > A[largest]:
        largest = right

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(H, A, largest)

def buildMaxHeap(H, A):
    for i in range(H // 2, 0, -1):
        maxHeapify(H, A, i)

MAX_ = 2 * 10**6
H = 0
A = [None] * (MAX_ + 1)

while 1:
    cmd = sys.stdin.readline().split()
    # print(A, file=sys.stderr)

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(popHeap(H, A))
        H -= 1
    else:
        H += 1
        insertHeap(H, A, int(cmd[1]))

Fixed submission:
import sys
from heapq import heappush, heappop

heap = []

while 1:
    cmd = sys.stdin.readline().split()

    if cmd[0] == 'end':
        break

    if cmd[0] == 'extract':
        print(-heappop(heap))
    else:
        heappush(heap, -int(cmd[1]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    n = int(input())
    a = [int(input()) for i in range(n)]
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    ans = max(dp)

    print(ans)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Fixed submission:
from sys import stdin

def solve():
    n = int(stdin.readline())
    A = [int(stdin.readline()) for i in range(n)]

    inf = 10**9 + 1
    dp = [inf] * n

    for a in A:
        j = nibutan(dp, a)
        dp[j] = a

    for i, v in enumerate(dp):
        if v == inf:
            print(i)
            return

    print(n)

def nibutan(dp, a):
    btm = -1
    top = len(dp)

    while top - btm > 1:
        mid = (top + btm) // 2
        if dp[mid] >= a:
            top = mid
        else:
            btm = mid

    assert 0 <= top < len(dp)
    return top

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.is_same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        # self.rank = [0] * n

    def find_root(self, x):
        if x != self.root[x]:
            self.root[x] = self.find_root(self.root[x])

        return self.root[x]

    def is_same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)
        self.root[p] = q

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Fixed submission:
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []
    
    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    def find_root(self, x):
        if self.root[x] == x:
            return x

        res = self.root[x]

        while res != self.root[res]:
            res = self.root[res]

        return res

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

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()