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

Fixed submission:
N, A = map(int, input().split())
x = list(map(int, input().split()))
maxX = max(max(x), A)
dp = [[[0 for _ in range(N * maxX + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(N + 1):
        for k in range(N * A + 1):
            if dp[i][j][k] == 0: continue
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

ans = 0
for i in range(1, N + 1):
    ans += dp[N][i][A * i]
print(ans)

Buggy submission (verdict: Runtime Error):
N, A = map(int, input().split())
x = list(map(int, input().split()))
maxX = max(x)
dp = [[[0 for _ in range(N * maxX + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(N + 1):
        for k in range(N * A + 1):
            if dp[i][j][k] == 0: continue
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

ans = 0
for i in range(1, N + 1):
    ans += dp[N][i][A * i]
print(ans)
Problem p02585 (python)

Fixed submission:
# 解説放送

def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    score = []
    checked = [0] * N
    for v in range(N):
        if checked[v]:
            continue
        t = []
        for _ in range(N):
            if checked[v]:
                break
            checked[v] = 1
            t.append(C[v])
            v = P[v]
        score.append(t)

    print(f'{score=}')

    ans = 0
    for loop_lst in score:
        L = len(loop_lst)
        s = sum(loop_lst)
        t = 0
        if s > 0:
            q, K = divmod(K, L)
            t += q * s
        K = min(K, L - 1)
        acc = [0]
        for x in loop_lst:
            acc.append(acc[-1] + x)
        add_v = 0
        for j in range(N)
        for i in range(K):
            add_v = max(acc[i+j] - acc[j])
        ans = max(ans, t + add_v)
    print(ans)


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

Fixed submission:
def main():
    INF = 10 ** 9 + 10

    D = int(input())
    *C, = map(int, input().split())
    # C[type]
    # sum(ci*(d-last(d,i) for ci in C)だけ下がる
    S = [[int(x) for x in input().split()] for _ in range(D)]
    # S[day][type]:=happiness

    last = [-1] * 26

    def diff(d, t):
        ret = S[d][t]
        ret -= sum(ci * (d - last[i]) for i, ci in enumerate(C) if i != t)
        return ret

    T = []
    score = 0
    for d in range(D):
        delta = -INF
        take_t = -1
        for t_ in range(26):
            buf = diff(d, t_)
            if delta < buf:
                delta = buf
                take_t = t_

        last[take_t] = d
        score += buf
        T.append(take_t + 1)
    print(*T, sep='\n')
    # print(score)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from itertools import product
    import os

    INF = 10 ** 9 + 10

    D = int(input())
    *C, = map(int, input().split())
    # C[type]
    # sum(ci*(d-last(d,i) for ci in C)だけ下がる
    S = [[int(x) for x in input().split()] for _ in range(D)]
    # S[day][type]:=happiness

    last = [-1] * 26

    def select(d):
        s = -1
        ret = -1
        for prd in product(range(26), repeat=min(D - d + 1, 2)):
            score = 0
            old = []
            for k, t in enumerate(prd):
                score += S[d + k][t]
                score -= sum(ci * (d + k - last[i]) for i, ci in enumerate(C) if i != t)
                old.append((t, last[t]))
                last[t] = d + k
            old.reverse()
            for t_, d_ in old:
                last[t_] = d_
            if s < score:
                s = score
                ret = prd[0]
        return ret

    T = []
    for d in range(D):
        t = select(d)
        last[t] = d
        T.append(t + 1)
    print(*T, sep='\n')
    # print(os.path.join(os.path.dirname(__file__), 'output_file.txt'))
    # with open(file=os.path.join(os.path.dirname(__file__), 'output_file.txt'), mode='w', encoding='utf-8') as f:
    #     for t in map(str, T):
    #         f.write(t)
    #         f.write('\n')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    INF = 10 ** 9 + 10

    D = int(input())
    *C, = map(int, input().split())
    # C[type]
    # sum(ci*(d-last(d,i) for ci in C)だけ下がる
    S = [[int(x) for x in input().split()] for _ in range(D)]
    # S[day][type]:=happiness

    last = [-1] * 26

    def diff(d, t):
        ret = S[d][t]
        ret -= sum(ci * (d - last[i]) for i, ci in enumerate(C) if i != t)
        return ret

    T = []
    score = 0
    for d in range(D):
        delta = -INF
        take_t = -1
        for t_ in range(26):
            if delta < (buf := diff(d, t_)):
                delta = buf
                take_t = t_

        last[take_t] = d
        score += buf
        T.append(take_t)
    print(*T, sep='\n')
    # print(score)


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

Fixed submission:
def main():
    from collections import defaultdict

    inf = 10 ** 15

    N = int(input())
    *a, = map(int, input().split())

    it = iter(a)

    dp = [defaultdict(lambda: -inf) for _ in range(N + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = next(it)
    for i, x in enumerate(it, 2):
        mi = (i - 1) // 2
        ma = (i + 1) // 2
        for taken_count in range(mi, ma + 1):
            dp[i][taken_count] = max(
                dp[i - 1][taken_count],
                dp[i - 2][taken_count - 1] + x
            )

    ans = dp[N][N // 2]

    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from functools import lru_cache

    inf = 2 * 10 ** 14 + 1

    N = int(input())
    *a, = map(int, input().split())

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


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

Fixed submission:
def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    h, n = map(int, input().split())
    *ab, = (list(map(int, input().split())) for _ in range(n))

    dp = [[inf] * (h + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    # dp[使った魔法][与えたダメージ]=最小魔法消費

    for i, (a, b) in enumerate(ab):
        for hp in range(h + 1):
            if hp < a:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][0] + b)
            else:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][hp - a] + b)

    print(dp[n][h])


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

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

    INF = 1 << 30

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

    dp = [INF] * (H * 2 + 1)
    dp[0] = 0

    for _ in range(N):
        A, B = map(int, input().split())
        for j in range(H):
            dp[j + A] = min(dp[j + A], dp[j] + B)
    print(min(dp[H:]))


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

Fixed submission:
def prime_decomposition(n):
    ret = set()

    x = n

    divisor = 2
    while x % divisor == 0:
        x //= divisor
        ret.add(divisor)

    divisor = 3
    while divisor * divisor <= n:
        while x % divisor == 0:
            x //= divisor
            ret.add(divisor)
        divisor += 2

    if x > 1:
        ret.add(x)

    return ret


def main():
    from functools import reduce
    from operator import mul

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

    pd = prime_decomposition(s)
    if not pd:
        m = s + 1
    else:
        m = reduce(mul, pd) - 1  # 互いに素

    ret = [s] * k + [m] * (n - k)
    print(*ret)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def prime_decomposition(n):
    ret = set()

    x = n

    divisor = 2
    while x % divisor == 0:
        x //= divisor
        ret.add(divisor)

    divisor = 3
    while divisor * divisor <= n:
        while x % divisor == 0:
            x //= divisor
            ret.add(divisor)
        divisor += 2

    if x > 1:
        ret.add(x)

    return ret


def main():
    from functools import reduce
    from operator import mul

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

    pd = prime_decomposition(s)
    m = reduce(mul, pd) - 1  # 互いに素

    ret = [s] * k + [m] * (n - k)
    print(*ret)


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

Fixed submission:
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
*a, = sorted(map(int, input().split()))

# -+-+-+-prepare combination-+-+-+-
# -+-+-+-START-+-+-+-
fact = [1] * (n + 1)
for x in range(2, n + 1):
    fact[x] = x * fact[x - 1] % MOD

invs = [1] * (n + 1)
invs[n] = pow(fact[n], MOD - 2, MOD)
for x in range(n - 1, 0, -1):
    invs[x] = invs[x + 1] * (x + 1) % MOD


def cmb(n, r):
    if n < r:
        return 0
    return (((invs[r] * invs[n - r]) % MOD) * fact[n]) % MOD


# -+-+-+-END-+-+-+-

ret = 0
for lt, x in enumerate(a):
    gt = n - lt - 1
    mi = cmb(gt, k - 1)
    ma = cmb(lt, k - 1)
    ret = (ret + (ma - mi) * x) % MOD

print(ret)

Buggy submission (verdict: Runtime Error):
def main():
    MOD = 10 ** 9 + 7
    n, k = map(int, input().split())
    *a, = map(int, input().split())

    compress = {x: i for i, x in enumerate(sorted(set(a)), 1)}
    rev = {i: x for x, i in compress.items()}

    e = [compress[x] for x in a]

    # -+-+-+-prepare combination-+-+-+-
    # -+-+-+-START-+-+-+-
    fact = [1] * (n + 1)
    for x in range(2, n + 1):
        fact[x] = x * fact[x - 1] % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(fact[n], MOD - 2, MOD)
    for x in range(n - 1, 0, -1):
        invs[x] = invs[x + 1] * (x + 1) % MOD

    def cmb(n, r):
        if n < r:
            return 0
        return (((invs[r] * invs[n - r]) % MOD) * fact[n]) % MOD

    # -+-+-+-END-+-+-+-

    def add(k, x):
        while k <= n:
            b[k] += x
            k += k & -k

    def get(k):
        s = 0
        while k:
            s += b[k]
            k -= k & -k
        return s

    ret = 0
    b = [0] * (n + 10)

    cnt = [0] * (n + 10)
    for a_ in a:
        e_ = compress[a_]
        add(e_, 1)
        cnt[a_] += 1

    for e_ in e:
        a_ = rev[e_]
        c = cnt[a_]

        smaller_eq = get(e_)
        ser = n - smaller_eq

        cnt_s = 0
        for x in range(1, min(k, c) + 1):
            cnt_s = (cnt_s + cmb(ser, k - x) * cmb(c, x)) % MOD

        larger_eq = n - get(e_ - 1)
        ler = n - larger_eq

        cnt_l = 0
        for x in range(1, min(k, c) + 1):
            cnt_l = (cnt_l + cmb(ler, k - x) * cmb(c, x)) % MOD

        ret = (ret + (cnt_l - cnt_s) * a_) % MOD

    print(ret % MOD)


if __name__ == '__main__':
    main()

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

# int(input())
# map(int, input().split())
Problem p02814 (python)

Fixed submission:
# https://atcoder.jp/contests/abc150/submissions/9395610

def main():
    from functools import reduce

    def count_two(x):
        ret = 0
        while x % 2 == 0:
            x //= 2
            ret += 1
        return ret

    def lcm(a, b):
        def _gcd(a, b):
            return a if b == 0 else _gcd(b, a % b)

        return a * b // _gcd(a, b)

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

    a = [x >> 1 for x in a]

    e = len(set(map(count_two, a)))
    if e != 1:
        print(0)
        return

    # x=(ai/2)*(2p+1)と変形する
    # 2p+1は奇数だから、
    # すべてのiについて,xと(ai/2)は,2で割れる回数が等しい必要がある

    x = reduce(lcm, a)
    ret = (m // x) - (m // (x + x))
    print(ret)
    # xは(ai/2)の最小公倍数の奇数倍
    # (ai/2)の最小公倍数の倍数全体から
    # (ai/2)の最小公倍数の偶数倍を引いた残り


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from functools import reduce
    from math import gcd

    def lcm(a, b):
        return (a // gcd(a, b)) * b

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

    p = -1
    b = []
    for x in a:
        cnt = 0
        while x % 2 == 0:
            x //= 2
            cnt += 1
        if ~p and p != cnt:
            print(0)
            return
        p = cnt
        b.append(x)

    if p == 0:
        print(0)
        return

    t = pow(2, p - 1) * reduce(lcm, b)
    ans = (M // t) - (M // (t * 2))

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
Problem p02845 (python)

Fixed submission:
def solve():
    mod = 10 ** 9 + 7

    n = int(input())
    a = tuple(map(int, input().split()))

    ret = 1
    cnt = [0] * (n + 10)
    cnt[0] = 3

    for x in a:
        cnt[x + 1] += 1
        ret = (ret * cnt[x]) % mod
        cnt[x] -= 1

    print(ret)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

ret = 1
cnt = [0] * n
zero = 0
for x in a:
    if x:
        ret = ret * cnt[x - 1] % mod
        cnt[x - 1] -= 1
    else:
        zero += 1
    cnt[x] += 1

if zero == 1:
    ret = ret * 3 % mod
elif 2 <= zero <= 3:
    ret = ret * 6 % mod
else:
    raise ValueError

print(ret)
Problem p02900 (python)

Fixed submission:
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


def factorize(n):
    res = set()

    diviser = 2
    exponent = 0
    while n % diviser == 0:
        exponent += 1
        n //= diviser
    if exponent > 0:
        res.add((diviser, exponent))
    # 2の冪数を先に調べることで、
    # diviserを奇数に限定できる

    to = int(pow(n, 0.5))
    for diviser in range(3, to + 1, 2):
        exponent = 0
        while n % diviser == 0:
            exponent += 1
            n //= diviser
        if exponent > 0:
            res.add((diviser, exponent))

    if n > 1:
        res.add((n, 1))
        # n:素数の場合

    return res


def main():
    a, b = map(int, input().split())
    g = gcd(a, b)
    e = factorize(g)

    ans = len(e) + 1
    # factorizeで、素数の種類数が分かる
    # 1で割る分を +1 で加算する
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    def prime_table(n):
        list = [True for _ in range(n + 1)]
        list[0] = False

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

    def is_prime(n):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                return False
        return True

    a, b = map(int, input().split())
    m = max(a, b)
    mx = int(m ** 0.5)

    tbl = prime_table(mx)

    ans = set()

    for p, bl in enumerate(tbl, 1):
        if a % p == 0 and b % p == 0:
            if bl:
                ans.add(p)

        qa = a // p
        if b % qa == 0 and is_prime(qa):
            ans.add(qa)

        qb = b // p
        if a % qb == 0 and is_prime(qb):
            ans.add(qb)

    print(len(ans))
    # print(*ans)


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

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)


def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)

Buggy submission (verdict: Runtime Error):
def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1
if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)
Problem p02975 (python)

Fixed submission:
from collections import defaultdict

n = int(input())
a = tuple(map(int, input().split()))

if n == 3:
    if a[0] ^ a[2] == a[1] and a[1] ^ a[2] == a[0] and a[0] ^ a[1] == a[2]:
        print('Yes')
    else:
        print('No')
elif n % 3 == 0:
    d = defaultdict(int)
    for aa in a:
        d[aa] += 1
    m = n // 3
    bl = True
    t = []
    for k, v in d.items():
        if v % m != 0:
            bl = False
            break
        else:
            q = v // m
            t.append((k, q))

    if len(t) == 3:
        if t[0][0] ^ t[1][0] == t[2][0] and t[1][0] ^ t[2][0] == t[0][0] and t[2][0] ^ t[0][0] == t[1][0]:
            pass
        else:
            bl = False
    elif len(t) == 2:
        if t[0][1] > t[1][1]:
            if t[0][0] ^ t[0][0] == t[1][0] and t[0][0] ^ t[1][0] == t[0][0]:
                pass
            else:
                bl = False
        else:
            if t[1][0] ^ t[1][0] == t[0][0] and t[0][0] ^ t[1][0] == t[1][0]:
                pass
            else:
                bl = False


    elif len(t) == 1:
        if t[0][0] != 0:
            bl = False

    print('Yes' if bl else 'No')

else:
    if all(aa == 0 for aa in a):
        print('Yes')
    else:
        print('No')

Buggy submission (verdict: Runtime Error):
def main():
    from collections import Counter

    n = int(input())
    *a, = map(int, input().split())

    if n % 3 == 0:
        ctr = Counter(a)
        if (len(ctr) == 1) and (0 in Counter):
            print('Yes')
            return
        elif len(ctr) == 3:
            it = iter(ctr.keys())
            x = next(it)
            y = next(it)
            z = next(it)
            print('Yes' if x ^ y == z else 'No')
            return
    else:
        print('Yes' if all(map(lambda x: x == 0, a)) else 'No')
        return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

n = int(input())
a = tuple(map(int, input().split()))

can = True
if n % 3 == 0:
    d = defaultdict(int)
    for aa in a:
        d[aa] += 1
    m = n // 3

    t = []
    for number, cnt in d.items():
        if cnt % m != 0:
            can = False
            break
        else:
            for _ in range(cnt // m):
                t.append(number)
    # print(t)
    if any(t[(0 + i) % 3] ^ t[(1 + i) % 3] != t[(2 + i) % 3] for i in range(3)):
        can = False

else:
    if any(aa != 0 for aa in a):
        can = False

print('Yes' if can else 'No')
Problem p02976 (python)

Fixed submission:
from collections import deque
import sys

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 6)

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

if m & 1:
    print(-1)
    exit()

g = [set() for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

seen = [False] * (n + 1)
seen[1] = True

mst = [set() for _ in range(n + 1)]

dq = deque()
dq.append(1)

while dq:
    v = dq.popleft()

    for u in g[v]:
        if seen[u]:
            continue
        seen[u] = True

        mst[u].add(v)
        mst[v].add(u)

        dq.append(u)

ans = set()
deg = [0] * (n + 1)
for v in range(1, n + 1):
    for u in g[v]:
        if v > u: continue
        if u not in mst[v]:
            ans.add((u, v))
            deg[u] += 1


def dfs(v, pr):
    for u in mst[v]:
        if u == pr:
            continue
        dfs(u, v)

    if pr == -1:
        return

    if deg[v] % 2 == 0:
        ans.add((pr, v))
        deg[pr] += 1
    else:
        ans.add((v, pr))
        deg[v] += 1


dfs(1, -1)

for aa in ans:
    print(*aa)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

if m & 1:
    print(-1)
    exit()

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

ans = []
deg = [0] * n

depth = [-1] * n
depth[0] = 0

dq = deque()
dq.append((0, -1))
mst = [[] for _ in range(n)]
while dq:
    v, pr = dq.popleft()
    for u in g[v]:
        if u == pr: continue
        if depth[u] != -1:
            if depth[u] < depth[v]:
                ans.append((v, u))
                deg[v] += 1
            continue
        depth[u] = depth[v] + 1
        dq.append((u, v))
        mst[u].append(v)
        mst[v].append(u)
# print(ans)

seen = [False] * n
seen[0] = True


def dfs(v, pr):
    for u in mst[v]:
        if seen[u]: continue
        seen[u] = True
        dfs(u, v)

    if pr == -1:
        return

    if deg[v] % 2 == 0:
        ans.append((pr, v))
        deg[pr] += 1
    else:
        ans.append((v, pr))
        deg[v] += 1


dfs(0, -1)

for aa in ans:
    print(*map(lambda x: x + 1, aa))