Harryxun/testdata huggingface dataset:
Buggy python 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)


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 python submission (verdict: Runtime Error):
def solve():
    mod = 10 ** 9 + 7

    x, y = map(int, input().split())

    sum_ = x + y

    q, r = divmod(sum_, 3)
    if r != 0:
        return 0

    a = (x * 2 - y) // 3

    # b = (y * 2 - x) // 3

    def cmb(n, r):
        return (f[n] * invs[r] * invs[n - r]) % mod

    f = [-1] * (q + 1)
    f[0] = 1
    t = 1
    for i in range(1, q + 1):
        t *= i
        t %= mod
        f[i] = t

    inv = pow(t, mod - 2, mod)
    invs = [-1] * (q + 1)
    invs[q] = inv
    for i in range(q - 1, 0, -1):
        inv *= (i + 1)  # <-直した
        inv %= mod
        invs[i] = inv

    return cmb(q, a)


print(solve())


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

    x, y = map(int, input().split())

    sum_ = x + y

    q, r = divmod(sum_, 3)
    if r != 0:
        return 0

    a = (x * 2 - y) // 3

    b = (y * 2 - x) // 3

    if a < 0 or b < 0:
        return 0

    def cmb(n, r):
        return (fact[n] * finv_t[r] * finv_t[n - r]) % mod

    fact = [1, 1]
    inv_t = [0, 1]
    finv_t = [1, 1]
    for i in range(2, q + 1):
        fact.append((fact[-1] * i) % mod)
        inv_t.append((-inv_t[mod % i] * (mod // i)) % mod)
        finv_t.append((finv_t[-1] * inv_t[-1]) % mod)

    return cmb(q, a)


print(solve())

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

    x, y = map(int, input().split())

    sum_ = x + y

    q, r = divmod(sum_, 3)
    if r != 0:
        return 0

    a = (x * 2 - y) // 3

    # b = (y * 2 - x) // 3

    def cmb(n, r):
        return (fact[n] * finv_t[r] * finv_t[n - r]) % mod

    fact = [1, 1]
    inv_t = [0, 1]
    finv_t = [1, 1]
    for i in range(2, q + 1):
        fact.append((fact[-1] * i) % mod)
        inv_t.append((-inv_t[mod % i] * (mod // i)) % mod)
        finv_t.append((finv_t[-1] * inv_t[-1]) % mod)

    return cmb(q, a)


print(solve())


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

    x, y = map(int, input().split())

    sum_ = x + y

    q, r = divmod(sum_, 3)
    if r != 0:
        return 0

    a = (x * 2 - y) // 3

    b = (y * 2 - x) // 3

    if a < 0 or b < 0:
        return 0

    def cmb(n, r):
        return (fact[n] * finv_t[r] * finv_t[n - r]) % mod

    fact = [1, 1]
    inv_t = [0, 1]
    finv_t = [1, 1]
    for i in range(2, q + 1):
        fact.append((fact[-1] * i) % mod)
        inv_t.append((-inv_t[mod % i] * (mod // i)) % mod)
        finv_t.append((finv_t[-1] * inv_t[-1]) % mod)

    return cmb(q, a)


print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
def binary_search(*, ok, ng, func):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if func(mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    N, K = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    *F, = sorted(map(int, input().split()), reverse=True)

    def is_ok(score):
        rest = K
        for a, f in zip(A, F):
            exceed = max(0, a * f - score)
            if exceed:
                need = (exceed + f - 1) // f
                if need > a or need > rest:
                    return False
                rest -= need
        return True

    ans = binary_search(ok=10 ** 12, ng=-1, func=is_ok)
    print(ans)


if __name__ == '__main__':
    main()


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

# int(input())
# map(int, input().split())


from math import ceil


def is_ok(mid):
    remain = k
    for ff, aa in zip(f, a):
        if ff * aa > mid:
            x = ceil(aa - (mid / ff))
            if x <= aa and x <= remain:
                remain -= x
            else:
                return False
    return True


def bs():
    ng, ok = -1, 10 ** 12
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok


n, k = map(int, input().split())
a = tuple(sorted(map(int, input().split())))
f = tuple(sorted(map(int, input().split()), reverse=True))
print(bs())
Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/agc039/submissions/7877660
from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    # bipartite = False
    return True
    # bipartite = True


def warshall_floyd(n, g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        # 隣接頂点間: 1
        # 同一頂点間: 0
        # その他: INF
    # print(es)
    # print(g)

    # 二部グラフ判定
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    # 最遠点対間距離を求める
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


if __name__ == '__main__':
    print(solve())


Fixed submission:
# https://atcoder.jp/contests/agc039/submissions/7877660
from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    # bipartite = False
    return True
    # bipartite = True


def warshall_floyd(n, g):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        # 隣接頂点間: 1
        # 同一頂点間: 0
        # その他: INF
    # print(es)
    # print(g)

    # 二部グラフ判定
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    # 最遠点対間距離を求める
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


if __name__ == '__main__':
    print(solve())
Buggy python 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()


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 python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
import sys

input = sys.stdin.readline

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

pos = [[] for _ in range(n + 1)]
for ind, pp in enumerate(p):
    for j in range(pp + 1):
        pos[j].append(ind)

ans = 0
for i, pp in enumerate(p):
    ind = bisect_left(pos[pp], i)

    left = 1
    if ind - 1 >= 0:
        left = i - pos[pp][ind - 1]
    else:
        left = i + 1
    right = 0
    if ind + 1 < len(pos[pp]):
        i_right = pos[pp][ind + 1]
        right = 1
        if ind + 2 < len(pos[pp]):
            right = pos[pp][ind + 2] - i_right
        else:
            right = n - i_right

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

    left = 0
    if ind - 1 >= 0:
        i_left = pos[pp][ind - 1]
        left = 1
        if ind - 2 >= 0:
            left = i_left - pos[pp][ind - 2]
        else:
            left = i_left + 1
    right = 1
    if ind + 1 < len(pos[pp]):
        right = pos[pp][ind + 1] - i
    else:
        right = n - i

    # print(i, pp, left * right, left, right)
    ans += left * right * pp

print(ans)


Fixed submission:
# https://atcoder.jp/contests/abc140/submissions/7411285
# 写経

def main():
    N = int(input())
    *p, = map(int, input().split())

    xtoi = [-1] * (N + 1)
    for i, x in enumerate(p):
        xtoi[x] = i

    L = [-1] * (N + 2)
    R = [N] * (N + 2)
    for i in range(N):
        L[i] = i - 1
        R[i] = i + 1

    iter_inds = iter(xtoi)
    next(iter_inds)

    ans = 0
    for x, ind in enumerate(iter_inds, start=1):
        # l2, ..., l1, ..., x, ..., r1, ..., r2
        # (l2,r1) or (l1,r2)
        l1 = L[ind]
        l2 = L[l1]
        r1 = R[ind]
        r2 = R[r1]
        ans += x * ((l1 - l2) * (r1 - ind) + (r2 - r1) * (ind - l1))
        L[r1] = l1
        R[l1] = r1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python 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)


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 python 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)


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 python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/abc138/submissions/7971841

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

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

ctr = [0] * n
for _ in range(q):
    it = map(int, input().split())
    p = next(it) - 1
    x = next(it)
    ctr[p] += x

st = [0]
par = [-1] * n
while st:
    v = st.pop()
    for u in g[v]:
        if u == par[v]: continue
        par[u] = v
        ctr[u] += ctr[v]
        st.append(u)
print(*ctr)


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

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

ctr = [0] * n
for _ in range(q):
    it = map(int, input().split())
    p = next(it) - 1
    x = next(it)
    ctr[p] += x

st = [(0, -1)]
while st:
    v, par = st.pop()
    for u in g[v]:
        if u == par: continue
        ctr[u] += ctr[v]
        st.append((u, v))
print(*ctr)

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

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


def dfs(cur, pls):
    pls += to_add[cur]
    ans[cur] = pls
    for u in e[cur]:
        if visited[u]:
            continue
        visited[u] = True
        dfs(u, pls)


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

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

to_add = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    to_add[p] += x

ans = [0] * n
visited = [False] * n
visited[0] = True

dfs(0, 0)

print(*ans)


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

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

ctr = [0] * n
for _ in range(q):
    it = map(int, input().split())
    p = next(it) - 1
    x = next(it)
    ctr[p] += x

st = [(0, -1)]
while st:
    v, par = st.pop()
    for u in g[v]:
        if u == par: continue
        ctr[u] += ctr[v]
        st.append((u, v))
print(*ctr)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10 ** 7)

    s = input()

    @lru_cache(maxsize=None)
    def cut(cur, t):
        if cur >= len(s):
            return 0

        ret = -1 << 30
        if t != s[cur]:
            ret = max(ret, cut(cur + 1, s[cur]) + 1)
        if t != s[cur:cur + 2]:
            ret = max(ret, cut(cur + 2, s[cur:cur + 2]) + 1)
        return ret

    ans = cut(0, '')

    print(ans)


if __name__ == '__main__':
    main()

# 一文字か二文字


Fixed submission:
s = input()
n = len(s)

a = []
cont = 0
c = ''
for ss in s:
    if c != ss:
        a.append(cont)
        c = ss
        cont = 1
    else:
        cont += 1
a.append(cont)

ans = 0
minus_flg = False
for aa in a[1:]:
    if minus_flg:
        aa -= 1
        minus_flg = False
    q, r = divmod(aa, 3)
    # print(aa, ans, q, r)
    if r == 0:
        ans += q * 2
    elif r == 1:
        ans += ((aa - 1) // 3) * 2 + 1
    else:
        ans += ((aa + 1) // 3) * 2
        minus_flg = True
if minus_flg:
    ans -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    s = input()

    def cut(cur, t):
        if cur >= len(s):
            return 0

        ret = -1 << 30
        if t != s[cur]:
            ret = max(ret, cut(cur + 1, s[cur]) + 1)
        if t != s[cur:cur + 2]:
            ret = max(ret, cut(cur + 2, s[cur:cur + 2]) + 1)
        return ret

    ans = cut(0, '')

    print(ans)


if __name__ == '__main__':
    main()

# 一文字か二文字


Fixed submission:
s = input()
n = len(s)

a = []
cont = 0
c = ''
for ss in s:
    if c != ss:
        a.append(cont)
        c = ss
        cont = 1
    else:
        cont += 1
a.append(cont)

ans = 0
minus_flg = False
for aa in a[1:]:
    if minus_flg:
        aa -= 1
        minus_flg = False
    q, r = divmod(aa, 3)
    # print(aa, ans, q, r)
    if r == 0:
        ans += q * 2
    elif r == 1:
        ans += ((aa - 1) // 3) * 2 + 1
    else:
        ans += ((aa + 1) // 3) * 2
        minus_flg = True
if minus_flg:
    ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

s = input()
n = len(s)

ans = [0] * n
p = []
for i in range(n - 1):
    if s[i:i + 2] == 'RL':
        p.append(i)
        ans[i] += 1
        ans[i + 1] += 1

for i in range(n):
    if s[i] == 'L':
        if i - 1 in p:
            continue
        to = bisect_left(p, i) - 1
    else:
        if i in p:
            continue
        to = bisect_left(p, i)
    dist = abs(i - p[to])
    # print(p[to], dist)
    if dist % 2 == 0:
        ans[p[to]] += 1
    else:
        ans[p[to] + 1] += 1
print(*ans)


Fixed submission:
from bisect import bisect_left

s = input()
n = len(s)

p = []
st = set()
for i, (sl, sr) in enumerate(zip(s, s[1:])):
    if sl == 'R' and sr == 'L':
        st.add(i)
        st.add(i + 1)
        p.append(i)

ans = [0] * n
for i, ss in enumerate(s):
    if i in st:
        ans[i] += 1
    else:
        idx = bisect_left(p, i)
        if ss == 'R':
            # p[idx]まで移動して、その後ループ
            loop_start_pos = p[idx]
            if (loop_start_pos - i) % 2 == 0:
                ans[loop_start_pos] += 1
            else:
                ans[loop_start_pos + 1] += 1
        else:
            # p[idx-1]まで移動して、その後ループ
            loop_start_pos = p[idx - 1]
            if (i - loop_start_pos) % 2 == 0:
                ans[loop_start_pos] += 1
            else:
                ans[loop_start_pos + 1] += 1

print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = int(input())

t = int(pow(s, 0.5))
for i in range(t, 0, -1):
    if s % i == 0:
        x = i
        y = s // i
        break

ans = [0, 0, 0, y, x, 0]
print(*ans)


Fixed submission:
s = int(input())
a = [0, 0]

a.append(10 ** 9)
a.append(1)

q, r = divmod(s, 10 ** 9)
if r > 0:
    q += 1
    r -= 10 ** 9
    r *= -1

a.append(r)
a.append(q)

print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
a = [None] + a

ans = set()
cnt = [0] * (n + 1)

for i in range(n, 0, -1):
    if cnt[i] % 2 != a[i] % 2:
        ans.add(i)

        st = set()
        j = 1
        while j * j <= i:
            if i % j == 0:
                st.add(j)
                st.add(i // j)
            j += 1
        for d in st:
            cnt[d] += 1

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


Fixed submission:
import sys

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a = [None] + a
a = tuple(a)

ans = set()
cnt = [0] * (n + 1)

for i in range(n, 0, -1):
    if cnt[i] % 2 != a[i] % 2:
        ans.add(i)

        st = set()
        j = 1
        while j * j <= i:
            if i % j == 0:
                st.add(j)
                st.add(i // j)
            j += 1
        for d in st:
            cnt[d] += 1

print(len(ans))
print(*ans)
Buggy python 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))


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)