Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    fin = []
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        if ans == "AC":
            if q_no not in fin:
                fin.append(q_no)
                ac += 1
                wa += wa_count.get(q_no, 0)
        else:
            wa_count[q_no] += 1
    
    print(ac, wa)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    a = [input().split() for _ in range(M)]
    ac_count = [0] * (N + 1)
    wa_count = defaultdict(lambda:0)
    ac, wa = 0, 0

    for q_no, ans in a:
        q_no = int(q_no)
        if ac_count[q_no] == 0:
            if ans == "AC":
                ac_count[q_no] = 1
                ac += 1
                wa += wa_count.get(q_no, 0)
            else:
                wa_count[q_no] += 1
    
    print(ac, wa)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
dic = {}

for word in range(n):
    word = input()
    if not word in dic:
        dic[word] = 1
    
    else:
        dic[word] += 1

ans = [k for k, v in dic.items() if v == max(dic.values())]
ans.sort()
for i in ans:
    print(i)

### FIXED CODE ###

n = int(input())
dic = {}

for word in range(n):
    word = input()
    if not word in dic:
        dic[word] = 1
    else:
        dic[word] += 1
max_v = max(dic.values())
ans = [kv[0] for kv in dic.items() if kv[1] == max_v]

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
s = input()
s = s.replace('LR', 'L,R')
s = s.replace('RL', 'R,L')
s = s.split(',')
s = list(map(len, s))
l = 2*k+1
ans = -1

if l >= len(s):
    ans = sum(s)-1
else:
    for i in range(len(s)-l+1):
        cnt = 0
        cnt += sum(np.array(s[:i])-1)
        cnt += sum(s[i:l+i])-1
        cnt += sum(np.array(s[l+i:])-1)
        ans = max(ans, cnt)
        
print(ans)

### FIXED CODE ###

n, k = map(int,input().split())
s = input()
ans=0
for i in range(n-1):
    if s[i] == s[i+1]:
        ans += 1

ans += k*2
if ans > n-1:
    ans = n-1
    
print(ans)
### BUGGY CODE ###

n=list(map(int,input()))
d={}
d[0]=1
a=0
b=len(n)
for i in reversed(range(b)):
    a+=(n[i]*pow(10,(b-i-1)))
    a%=2019
    if not a in d:
        d[a]=1
    else:
        d[a]+=1

ans=0

for s,v in d.items():
    if v>=2:
        ans+=v*(v-1)//2
        
print(ans)

### FIXED CODE ###

n=list(map(int,input()))
d=[0]*2019
d[0]=1
a=0
b=len(n)
for i in reversed(range(b)):
    a+=(n[i]*pow(10,(b-i-1),2019))
    a%=2019
    d[a]+=1

ans=0

for i in range(2019):
    c=d[i]
    ans+=c*(c-1)//2
        
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0] * 30
t = [1] * 30
for i in range(29):
    t[i + 1] = t[i] * 2
for i in range(N):
    aa = a[i]
    for j in range(30):
        s[j] = (s[j] + aa)%2
        aa = aa//2
for i in range(N):
    ans = a[i]
    b = a[i]
    for j in range(30):
        ans1 = b%2
        b = b//2
        if s[j] == 1:
            if ans1 == 1:
                ans -= t[j] 
            else:
                ans += t[j]
    print(ans,end = " ")
print()

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0] * 30
t = [1] * 30
for i in range(29):
    t[i + 1] = t[i] * 2
ss = a[0]
for j in range(N - 1):
    ss = ss ^ a[j + 1]
for j in range(N):
    print(a[j] ^ ss,end = " ")
print()
### BUGGY CODE ###

import math


def resolve():
    A, B, N = map(int, input().split())

    ans = 0
    for i in range(min(N, B), 1, -1):
        tmp = math.floor(A * i / B) - A * math.floor(i / B)
        ans = max(tmp, ans)

    print(ans)


resolve()

### FIXED CODE ###

def resolve():
    A, B, N = map(int, input().split())
    print(A * min(N, B - 1) // B)


resolve()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        point[c] += point[v]
        dfs(G, c, v, point)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    point = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        point[p] += x

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

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


def dfs(G, v, p, point):
    """G: graph, v: vertex, p: parent"""
    # Loop for each child
    for c in G[v]:
        if c == p:
            continue
        point[c] += point[v]
        dfs(G, c, v, point)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)

    point = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        point[p] += x

    dfs(G, 0, -1, point)
    print(" ".join(map(str, point)))


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
Number=[0]*n
Numstr=""
for i in range(n):
    Number[a[i]-1]=i+1
for j in range(n):
    if j!=n:
        Numstr=Numstr+str(Number[j])+" "
    else:
        Numstr=Numstr+str(Number[j])
print(Numstr)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
Number=[0]*n
for i in range(n):
    Number[a[i]-1]=i+1

print(" ".join(map(str,Number)))
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0

for i in range(K + 1):
    for j in range(K + 1):
        for k in range(K + 1):
            s = i + j + k
            if S < s:
                break
            elif S == s:
                ans += 1

print(ans)

### FIXED CODE ###

K, S = map(int, input().split())
ans = 0

for i in range(K + 1):
    s = i
    if s > S:
        break
    for j in range(K + 1):
        s = i + j
        if s > S:
            break
        Z = S - s
        if 0 <= Z <= K:
            ans += 1

print(ans)
### BUGGY CODE ###

import collections

n=int(input())
ans=[0]*(n+1)
s=set()
u,v,w=map(int,input().split())
s.add(u)
s.add(v)
if w%2==0:
  ans[u]=1
  ans[v]=1
elif w%2==1:
  ans[u]=1
  ans[v]=0
q=collections.deque()
cnt=1
cnt2=1
while 1:
  if cnt==n-1:
    break
  else:
    if cnt2<n-1:
      u,v,w=map(int,input().split())
    else:
      tmp=q.popleft()
      u,v,w=tmp[0],tmp[1],tmp[2]
    cnt2+=1
    if u in s:
      s.add(v)
      cnt+=1
      if w%2==0:
        ans[v]=ans[u]
      else:
        ans[v]=abs(ans[u]-1)
    elif v in s:
      s.add(u)
      cnt+=1
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=abs(ans[v]-1)
    else:
      q.append([u,v,w])
for i in range(1,n+1):
  print(ans[i])

### FIXED CODE ###

import collections

n=int(input())
ans=[0]*(n+1)
tree=[[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
q=collections.deque([1])
check=[False]*(n+1)
check[1]=True
tmp=tree[1][0]
if tmp[1]%2==0:
  ans[1]=1
  ans[tmp[0]]=1
else:
  ans[1]=1
  ans[tmp[0]]=0
while 1:
  if len(q)==0:
    break
  tmp=q.popleft()
  for i in range(len(tree[tmp])):
    v,w=tree[tmp][i][0],tree[tmp][i][1]
    if check[v]:
      continue
    else:
      check[v]=True
      if w%2==0:
        ans[v]=ans[tmp]
      else:
        ans[v]=abs(1-ans[tmp])
      q.append(v)
for i in range(1,n+1):
  print(ans[i])
### BUGGY CODE ###

import math

a, b, h, m = map(int, input().split())


def choshin_angle(m):
    return 6 * m

def tanshin_angle(h, m):
    return 0.5 * (60 * h + m)

theta = abs(tanshin_angle(h, m) - choshin_angle(m))

while (theta >= 180.):
    theta = 360 - theta

theta = math.radians(theta)

x2 = a**2 + b**2 - 2 * a * b * math.cos(theta)

x = math.sqrt(x2)

print(x)



### FIXED CODE ###

import math

a, b, h, m = map(int, input().split())


def choshin_angle(m):
    return 6 * m

def tanshin_angle(h, m):
    return 0.5 * (60 * h + m)

theta = abs(tanshin_angle(h, m) - choshin_angle(m))

if (theta >= 180.):
    theta = 360 - theta

theta = math.radians(theta)

x2 = a**2 + b**2 - 2 * a * b * math.cos(theta)

x = math.sqrt(x2)

print(x)
### BUGGY CODE ###

# abc171_d.py
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)

Q = int(input())
for i in range(Q):
    b ,c = map(int,input().split())
    C[c] += C[b]
    C[b] = 0
    ans = 0
    for i,v in C.items():
        ans+=(i*v)
    print(ans)


### FIXED CODE ###

# abc171_d.py
import collections

N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
sums = sum(A)
Q = int(input())
for i in range(Q):
    b ,c = map(int,input().split())
    sums += C[b]*c
    sums -= C[b]*b
    C[c] += C[b]
    C[b] = 0
    print(sums)
### BUGGY CODE ###

import os, sys, re, math

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

cards = [int(s) for s in input().split(' ')]
cards.sort()

for i in range(M):
    b, c = [int(s) for s in input().split(' ')]
    idx = 0
    while idx < b and cards[idx] < c:
        cards[idx] = c
        idx += 1
    cards.sort()

print(sum(cards))


### FIXED CODE ###

import os, sys, re, math, heapq

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

dic = {}
cards =  [int(s) for s in input().split(' ')]
for c in cards:
    if c in dic:
        dic[c] += 1
    else:
        dic[c] = 1

for i in range(M):
    b,c = [int(s) for s in input().split(' ')]
    if c in dic:
        dic[c] += b
    else:
        dic[c] = b

keys = sorted(list(dic.keys()), reverse=True)

ret = 0
for k in keys:
    ret += min(N, dic[k]) * k
    N = N - dic[k]
    if N <= 0:
        break

print(ret)
### BUGGY CODE ###

X = int(input())

count = []
if X == 1:
    print(1)
else:
    for i in range(1,X):
        for b in range(2,X):
            factorial = i**b
            if factorial <= X:
                count.append(factorial)

    print(max(count))


### FIXED CODE ###

X = int(input())

count = []
if X == 1:
    print(1)
else:
    for i in range(1,X):
        for b in range(2,10):
            factorial = i**b
            if factorial <= X:
                count.append(factorial)

    print(max(count))
### BUGGY CODE ###

n, p = map(int,input().split())
D = input()
count = [0] * p
out = 0

if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    ten = 1
    count[0] = 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        count[mod] += 1
        ten *= 10 % p
    for c in count:
        out += (c * (c - 1)) // 2
print(out)

### FIXED CODE ###

n, p = map(int,input().split())
D = input()
out = 0


if 10 % p == 0:
    for i in range(n):
        if int(D[i]) % p == 0:
            out += i + 1
else:
    mod = 0
    count = [0] * p
    ten = 1
    count[mod] += 1
    for i in range(n):
        mod = (mod + int(D[n-i-1]) * ten) % p
        ten = ten * 10 % p
        count[mod] += 1
    for c in count:
        out += (c * (c - 1)) // 2
print(out)
### BUGGY CODE ###

card_count, rewrite_count = map(int, input().split(" "))
cards = list(map(int, input().split(" ")))

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    cards.extend((rewrite_number,) * stock_count)

cards.sort()

print(sum(cards[-card_count:]))


### FIXED CODE ###

import bisect

card_count, rewrite_count = map(int, input().split(" "))

cards = {}
for card in list(map(int, input().split(" "))):
    count = cards.get(card, 0)
    cards[card] = count + 1

for _ in range(rewrite_count):
    stock_count, rewrite_number = map(int, input().split(" "))
    count = cards.get(rewrite_number, 0)
    cards[rewrite_number] = count + stock_count

number_list = list(cards.keys())
number_list.sort(reverse=True)

total = 0
for number in number_list:
    if cards[number] < card_count:
        total += number * cards[number]
    else:
        total += number * card_count
        break
    card_count -= cards[number]

print(total)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit, prange
input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**9, N)

dp = np.zeros((n, 10**5+1), np.int64)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit(parallel = True, cache = True)
def func(vws_choose, L):
    bits = np.arange(1 << len(vws_choose))
    values = np.zeros_like(bits, np.int64)
    weights = np.zeros_like(bits, np.int64)
    for i in prange(len(vws_choose)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vws_choose[i][0]
        weights[indices] += vws_choose[i][1]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2

        func(np.array(vws_choose), L)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

def sol():
    n=int(input())
    a=[int(i) for i in input().split()]
    ans=chk=0
    for i in range(min(a[0],a[-1])*2,-1,-2):
        ans=[0]*n
        ans[0]=i
        f=1
        for j in range(1,n):
            t=(a[j-1]-ans[j-1]//2)*2
            if t>=0 and (t+ans[j-1])//2==a[j-1]:
                ans[j]=t
            else:
                f=0
                break
        if f and ans[-1]//2+ans[-2]//2==a[-2] and ans[-1]//2+ans[0]//2==a[-1]:
            print(*ans)

if __name__=="__main__":
    sol()


### FIXED CODE ###

# from https://atcoder.jp/contests/abc133/submissions/6272850
n=int(input())
a=[int(i) for i in input().split()]
c=[0]
s=sum(a)

for i in range(2*n):
    c.append(c[-1]+a[(i*2+1)%n])
ans=[0]*n
for i in range(n):
    ans[i*2%n]=s-2*(c[i+n//2]-c[i])
print(*ans)
### BUGGY CODE ###

def read():
	return [int(i) for i in input().split(' ')]
N, T = read()
A = read()
expect = 0
route = set()
length = len(A)
for i in range(length):
	buy = A[i]
	for j in range(i + 1, length):
		benefit = A[j] - buy
		if(benefit > expect):
			expect = benefit
			route = set([i, j])
		elif(benefit == expect):
			if(i not in route and j not in route):
				route.add(i)
				route.add(j)
cost = len(route) >> 1
print(cost)


### FIXED CODE ###

def read():
	return [int(i) for i in input().split(' ')]
N, T = read()
A = read()
t_min = A[0]
cost = 1
profit = 0

for p in A:
	if(p < t_min):
		t_min = p
	elif(p - t_min == profit):
		cost += 1
	elif(p - t_min > profit):
		cost = 1
		profit = p - t_min
print(cost)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for i in range(60):
  if i ==0:
    A =[divmod(x,2) for x in A]
    n = sum(y for x,y in A)
    res += n*(N-n)
  else:
    A = [divmod(x,2) for x,y in A]
    n = sum(y for x,y in A)
    t = t*2
    res += n*(N-n)*t
    if all(x==0 for x in A):
      break
print(res%(7+10**9))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)
### BUGGY CODE ###

# # Educational DP Contest E
# 方針：dp[i][v] := i-1番目までの物の中から，価値v以上を達成するように選んだ時の重さの最小値

# 入力
N, W = map(int, input().split())
weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i] = w
    value[i] = v

# DPテーブル
max_v = sum(value)
dp = [[float("inf")] * (max_v + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(max_v+1):
        if v >= value[i]:       # i番目の物を選ぶ時
            dp[i+1][v] = min(dp[i][v - value[i]] + weight[i], dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for v in range(max_v, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)

### FIXED CODE ###

# # Educational DP Contest E
# 方針：dp[i][v] := i-1番目までの物の中から，価値v以上を達成するように選んだ時の重さの最小値

# 入力
N, W = map(int, input().split())
weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i] = w
    value[i] = v

# DPテーブル
max_v = sum(value)
dp = [[float("inf")] * (max_v + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for v in range(max_v+1):
        if v >= value[i]:       # i番目の物を選ぶ時
            dp[i+1][v] = min(dp[i][v - value[i]] + weight[i], dp[i][v])
        else:
            dp[i+1][v] = dp[i][v]

for v in range(max_v, -1, -1):
    if dp[N][v] <= W:
        ans = v
        break
print(ans)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
yoso=list(set(a))
count=0
for i in range(0,len(yoso)):
    acount=a.count(yoso[i])
    if yoso[i]>acount:
        count+=acount
    elif yoso[i]<acount:
        count+=(acount-yoso[i])
print(count)

### FIXED CODE ###

import collections
N=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
c=list(set(a))
count=0
for i in range(0,len(c)):
    if b[c[i]]>=c[i]:
        count+=b[c[i]]-c[i]
    else:
        count+=b[c[i]]
print(count)
### BUGGY CODE ###

import math
K = int(input())
sumgcd = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sumgcd += math.gcd(math.gcd(a, b), c)
print(sumgcd)


### FIXED CODE ###

import math
K = int(input())
sumgcd = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sumgcd += math.gcd(math.gcd(a, b), c)
print(sumgcd)
### BUGGY CODE ###

import sys 

N, M = list(map(int, input().split()))
a_list = list()
b_list = list()
c_list = list()

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf for _ in range(N)]
dist[0] = 0

for _ in range(N-1):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]

ans = dist[N-1]
negative = [False for _ in range(N)]

for _ in range(N):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]
            negative[b_list[i]-1] = True
        if negative[a_list[i]-1]:
            negative[b_list[i]-1] = True

if negative[N-1]:
    print('inf')
else:
    print(str(-ans))



### FIXED CODE ###

import sys 

N, M = list(map(int, input().split()))
a_list = list()
b_list = list()
c_list = list()

for _ in range(M):
    a, b, c = list(map(int, input().split()))
    a_list.append(a)
    b_list.append(b)
    c_list.append(-c)

inf = sys.maxsize
dist = [inf] * N
dist[0] = 0

for loop in range(N):
    for i in range(M):
        if dist[a_list[i]-1] == inf:
            continue
        if dist[b_list[i]-1] > dist[a_list[i]-1] + c_list[i]:
            dist[b_list[i]-1] = dist[a_list[i]-1] + c_list[i]
            if loop == N - 1 and b_list[i] == N:
                print('inf')
                sys.exit()

print(-dist[N-1])
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
n, m = map(int, input().split())

if m%2==1:
  print(-1)
  exit()

graph = defaultdict(set)
grapht = defaultdict(set)
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  graph[a].add(b)
  graph[b].add(a)
  grapht[a].add(b)
  grapht[b].add(a)

graph2 = defaultdict(set)
visited = [0]*n
num = [1]*n

def dfs(x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(nx)

  t = []
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.append(e)
  elif num[x]==-1 and len(grapht[x])%2==0:
    for j, e in enumerate(grapht[x]):
      if j==len(grapht[x])-1:
        graph2[e].add(x)
        num[e] *= -1
      else:
        graph2[x].add(e)
      t.append(e)
  elif num[x]==1 and len(grapht[x])%2==1:
    for j, e in enumerate(grapht[x]):
      if j==len(grapht[x])-1:
        graph2[e].add(x)
        num[e] *= -1
      else:
        graph2[x].add(e)
      t.append(e)
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.append(e)
  for e in t:
    grapht[x].remove(e)
    grapht[e].remove(x)

dfs(0)

for i in range(n):
  if len(graph2[i])%2==1:
    print(-1)
    exit()

for i in range(n):
  for e in graph2[i]:
    print(i+1, e+1)

### FIXED CODE ###

from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, nx)

  t = set()
  if num[x]==1 and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  elif num[x]==-1 and len(grapht[x]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].add(b)
    graph[b].add(a)
    grapht[a].add(b)
    grapht[b].add(a)

  graph2 = defaultdict(set)
  visited = [0]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 0)

  for i in range(n):
    if len(graph2[i])%2==1:
      print(-1)
      exit()

  for i in range(n):
    for e in graph2[i]:
      print(i+1, e+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:x[1])
bridge=[True]*(n-1)
for a,b in AB:
  if bridge[a-1:b-1].count(False)==0:
    bridge[b-2]=False
print(bridge.count(False))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:(x[1],x[0]))
end=AB[0][1]
ans=1
for a,b in AB[1:]:
  if end<=a:
    end=b
    ans+=1
print(ans)