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

def main():
  import sys
  read = sys.stdin.read
  
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  m = map(lambda x:int(x)-1, read().split())
  *pqc, = zip(m, m, m)
  del m

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for v in range(N):
    if len(to1d[v])<=1: continue
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

### FIXED CODE ###

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

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

import math
import itertools

n=int(input())
L=[int(i) for i in input().split()]
L.sort()

ans=0
for i in range(2,n):
  c=list(itertools.combinations(L[:i],2))
  for j in range(len(c)):
     if  math.floor(c[j][0]-c[j][1])<L[i]<c[j][0]+c[j][1]:
        ans+=1
print(ans)

### FIXED CODE ###

from bisect import bisect_right
n=int(input())
L=[int(i) for i in input().split()]
L.sort()


ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    c=L[i]+L[j]-1
    ans+=bisect_right(L,c)-j-1
    
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])

### FIXED CODE ###

N,W=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,N+1):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j-w>=0:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

from itertools import accumulate
from operator import add

N,K,*A = map(int,open(0).read().split())

for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        left = max(0, i-x)
        right = min(N-1, i+x)
        B[left] += 1
        if right+1 != N:
            B[right+1] -= 1
    A = list(accumulate(B,add))    
print(*A,sep=" ")

### FIXED CODE ###

from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        L = max(0, i-x)
        R = min(N-1, i+x)
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)
### BUGGY CODE ###

X,K,D=map(int,input().split())
X=abs(X)
if X-K*D>0:
    print(X-K*D)
else:
    i=0
    while X-D*i>0:
        i=i+1
    if (K-i)%2==1:
        print(abs(X-D*(i-1)))
    else:
        print(abs(X-D*i))

### FIXED CODE ###

X,K,D=map(int,input().split())
X=abs(X)
if X-K*D>0:
    print(X-K*D)
elif (K-X//D)%2==1:
    print(abs(X%D-D))
else:
    print(X%D)
### BUGGY CODE ###

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

### FIXED CODE ###

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

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 組み合わせ
L = [0]
for i in range(0,N+1):
    L.append(i*(i+1)//2)

# 各数字の個数を求める
Cn = [An.count(i) for i in range(1,N+1)]
 
# 全部の組み合わせ
Dn = [L[Cn[i-1]] for i in range(1,N+1)]
s = sum(Dn)
 
for i in range(1,N+1):
    print(s - (Cn[An[i-1]-1] - 1))

### FIXED CODE ###

import collections as c

# 入力
N = int(input())
An = [int(x) for x in input().split()]
 
# 各数字の個数を求める
Cn = c.Counter(An)
 
# 全部の組み合わせ
s = 0
for v in Cn.values():
    s += int(v*(v-1) / 2)

for i in range(0,N):
    print(s - (Cn[An[i]] - 1))
### BUGGY CODE ###

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

s = [0]
for i in range(n):
    s.append(sum(l[:i+1]))

s = [j%m for j in s]
s.sort()

ans = 0
mae = s[0]
cnt = 1
for k in range(1, n+1):
    if s[k]==mae:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        mae = s[k]
        cnt = 1
    if k==n:
        ans += cnt*(cnt-1)//2

print(ans)

### FIXED CODE ###

from collections import Counter

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

s = [0]
for i in range(n):
    s.append((s[-1]+l[i])%m)

c = Counter(s)

ans = 0
for x in c.values():
    ans += x*(x-1)//2

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

import  re
s = input().replace("BC", "X")
cnt = 0
while "AX" in s:
  if "AXAX" in s:
    tmp = re.subn("AXAX", "XXAA", s)
    s = tmp[0]
    cnt += tmp[1] * 3

  tmp = re.subn("AX", "XA", s)
  s = tmp[0]
  cnt += tmp[1]
print(cnt)

### FIXED CODE ###

cnt, tmp = 0, 0
for c in input().replace("BC", "X"):
  if c == "A":
    tmp += 1
  elif c == "X":
    cnt += tmp
  else:
    tmp = 0
print(cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans=0
for j in range(N):
    for i in range(N):
        if A[i]>=B[j]:
            a=i
            break
    else:
        a=N
    for k in range(N):
        if C[k]>B[j]:
            c=N-k
            break
    else:
        c=0
    ans+=a*c
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans=0
for j in range(N):
    a=bisect_left(A, B[j])
    c=bisect_right(C, B[j])
    ans+=a*(N-c)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

INF = 10**12
dp = [[INF] * (N+1) for i in range(N+1)]
dp[0][0] = 0

for x in range(1, N+1):
  dp[x][0] = 0
  dp[x][1] = H[x]
  for y in range(2, x+1):
    for i in range(x):
      dp[x][y] = min(dp[x][y], dp[i][y-1]+max(0, H[x]-H[i]))

ans = INF
for i in range(N+1):
  ans = min(ans, dp[i][N-K])

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = [0] + list(map(int, input().split()))

INF = 10**12
dp = [[INF] * (N+1) for i in range(N+1)]
dp[0][0] = 0

for x in range(1, N+1):
  dp[x][0] = 0
  dp[x][1] = H[x]
  for y in range(2, x+1):
    for i in range(x):
      dp[x][y] = min(dp[x][y], dp[i][y-1]+max(0, H[x]-H[i]))

ans = INF
for i in range(N+1):
  ans = min(ans, dp[i][N-K])

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

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    while parent[i] != i:
        i = parent[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()


### FIXED CODE ###

N,M,K = list(map(int,input().split(' ')))

friend_list = [0]*(N+1)
bad_list = [0]*(N+1)
group = {}

parent = [i for i in range(N+1)]

def find(i):
    rireki = []
    while parent[i] != i:
        rireki.append(i)
        i = parent[i]
    for r in rireki:
        parent[r]=i
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    parent[j] = i



for i in range(M):
    A,B = list(map(int,input().split(' ')))
    friend_list[A]+=1
    friend_list[B]+=1
    
    union(A,B)

for i in range(1,N+1):
    oya = find(i)
    parent[i] = oya
    #print(oya)
    if oya in group:
        group[oya] = group[oya]+1
    else:
        group[oya]=1

for i in range(K):
    A,B = list(map(int,input().split(' ')))
    if find(A)==find(B):
        bad_list[A]+=1
        bad_list[B]+=1
    
    #union(A,B)



#print(parent)
#print('parent')

#print('friend')
#print(friend_list)
#print('bad')
#print(bad_list) 
#print(group)

kouho = [0]*N

for i in range(1,N+1):
    oya = find(i)
    abc = group[oya]-friend_list[i]-bad_list[i]-1
    kouho[i-1] = abc

for k in kouho:
    print(k,end=" ")
print()

#print(parent)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = (a[i]+1)/2
ans = 0
for i in range(n-k+1):
    tmp = sum(a[i:i+k])
    if tmp > ans:
        ans = tmp
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = (a[i]+1)/2
ans = sum(a[0:0+k])
tmp = sum(a[0:0+k])
for i in range(n-k):
    tmp -= a[i]
    tmp += a[i+k]
    if tmp > ans:
        ans = tmp
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
while n >= abs(n-k):
    n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
if n > k:
    a = n // k
    n = n - a * k
while n >= abs(n-k):
    n = abs(n-k)
print(n)
### BUGGY CODE ###

S = input().split(" ")

n = int(S[0])
blue = int(S[1])
countB = 0
red = int(S[2])
countR = 0
shuki = blue + red
sh = 0
for i in range(1,n+1):
  amari = i % shuki
  if amari >=1 and amari <= blue:
    countB = countB +1
  else:
    countR = countR + 1
print(countB)

### FIXED CODE ###

N, A, B = map(int, input().split())
an = N // (A+B) * A
rem = N % (A+B)
an += min(rem,A)
print(an)
### BUGGY CODE ###

N, Q = map(int, input().split())
K = ['NUL' for i in range(N)]
for i in range(N):
        K[i] = list(map(int, input().split()))
K.sort(key=lambda x: x[2]) # 通行止め座標が小さい順にソート

for i in range(Q):
        D = int(input())
        okvalue = 0
        i = 0
        while i < N and okvalue == 0:
                collision_time = D + K[i][2]
                if K[i][0] - 0.5 < collision_time < K[i][1] - 0.5:
                        okvalue = 1
                else:
                        i += 1
        
        if i < N:
                print(K[i][2])
        else:
                print(-1)

### FIXED CODE ###

import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    """
    計算量の落とし方が全くわからんので以下のコードを参考に写経。。。
    https://atcoder.jp/contests/abc128/submissions/7712981
    """
    N, Q = map(int, input().split())
    work = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        work.append((x, s - x, t - x))
    work.sort(key=lambda x: (x[0], x[1]))
    start = [int(input()) for _ in range(Q)]

    """
    工事箇所を原点にスライドさせる事で考察を易化しておく。
    各工事(x, s, t)に対して（既にs, tは原点への移動を考慮済み）s<=d<tなるdの個数を求めたい
    startは既に昇順に並んでいるので二分探索でs<=d_i<d_{i+1}<...<d_{j-1}<tなるi=left, j=rightを求める。

    そのあと[left, right)をxで埋めていくが、愚直に(right-left)回xを代入していくとO(Q)かかってTLEするので
    skip[left]=(以前に[left, right)を埋めたときのright)を格納しておく。
    これによりansの表を毎度全走査しなくてもよくなり書き込み範囲のオーバーラップがだいぶ削減される。

    しかしskipを使っても飛んだ先がまたskip命令入ってる可能性もあるから、AC出来るのはやや偶然感あり。。。
    """

    ans = [-1] * Q
    skip = [-1] * Q
    for x, s, t in work:
        left = bisect_left(start, s)
        right = bisect_left(start, t)
        while left < right:
            if skip[left] == -1:
                ans[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    for i in range(Q):
        print(ans[i])




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

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*(10**(i-1))%2019)%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

import itertools
n=int(input())
x=[int(input()) for i in range(n)]
listX = list(itertools.permutations(x, n))

listY = []
for j in range(len(listX)):
  y = 0
  for i in range(n-1):
    y = y + abs(listX[j][i]-listX[j][i+1])
  listY.append(y)

print(max(listY))



### FIXED CODE ###

import itertools
import numpy as np
data_num = int(input()) 
data = [int(input()) for i in range(data_num)] 
#data_num=5
#data=[6,8,1,2,3]

data.sort()
npdata=np.array(data)

parts1=[1]
parts2=[2 for i in range(data_num-2)]
parts1.extend(parts2)
parts1.append(1)
npparts1=np.array(parts1)

parts0=[(-1)**(i+1) for i in range(data_num)]
npparts0=np.array(parts0)

y=npparts1*npparts0

y=y.tolist()
y.sort()

y=np.array(y)
z1=sum(data*y)

parts01=[(-1)**i for i in range(data_num)]
npparts0=np.array(parts01)

y=npparts1*npparts0

y=y.tolist()
y.sort()
y=np.array(y)
z2=sum(data*y)

print(max(z1,z2))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
SC = [0] * (N - 1)
for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i] = 1

for i in range(Q):
    l, r = map(int, input().split())
    print(SC[l - 1:r - 1].count(1))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
SC = [0] * N

for i in range(N - 1):
    if S[i:i + 2] == "AC":
        SC[i + 1] = SC[i] + 1
    else:
        SC[i + 1] = SC[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(SC[r - 1] - SC[l - 1])
### BUGGY CODE ###

n = int(raw_input())
A = map(int, raw_input().strip().split(' '))
q = int(raw_input())
M = map(int, raw_input().strip().split(' '))

def solve(i,m):
    if m == 0: return True
    elif i >= n: return False
    else:
        return solve(i+1,m) | solve(i+1,m-A[i])

for m in M:
    if solve(0,m): print "yes"
    else: print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int, raw_input().strip().split(' '))
q = int(raw_input())
M = map(int, raw_input().strip().split(' '))

memo = []
for i in range(len(A)+1):
    memo.append([None]*2000)

def solve(i,m):
    if memo[i][m] != None: return memo[i][m]
    if m == 0:
        memo[i][m] = True
        return True
    elif i >= n:
        memo[i][m] = False
        return False
    else:
        ret = solve(i+1,m) | solve(i+1,m-A[i])
        memo[i][m] = ret
        return ret

for m in M:
    if solve(0,m): print "yes"
    else: print "no"
### BUGGY CODE ###

def D_Lamp():
    h, w = map(int, input().split())
    S = [[] for j in range(h)]
    L = [[0 for i in range(w)] for j in range(h)]
    R = [[0 for i in range(w)] for j in range(h)]
    U = [[0 for i in range(w)] for j in range(h)]
    D = [[0 for i in range(w)] for j in range(h)]
    for row in range(h):
        S[row] = input()
    for row in range(h):
        for col in range(w):
            if "#" == S[row][col]:
                L[row][col] = 0
            elif col == 0:
                L[row][col] = 1
            elif "." == S[row][col]:
                L[row][col] = L[row][col-1] + 1
    for row in range(h):
        for col in range(w):
            tmp = w-col-1
            if "#" == S[row][tmp]:
                R[row][tmp] = 0
            elif col == 0:
                R[row][tmp] = 1
            elif "." == S[row][tmp]:
                R[row][tmp] = R[row][tmp+1] + 1
    for col in range(w):
        for row in range(h):
            if "#" == S[row][col]:
                U[row][col] = 0
            elif row == 0:
                U[row][col] = 1
            elif "." == S[row][col]:
                U[row][col] = U[row-1][col] + 1
    for col in range(w):
        for row in range(h):
            tmp = h-row-1
            if "#" == S[tmp][col]:
                D[tmp][col] = 0
            elif row == 0:
                D[tmp][col] = 1
            elif "." == S[tmp][col]:
                D[tmp][col] = D[tmp+1][col] + 1
    
    num_max = 0
    for row in range(h):
        for col in range(w):
            s_num = L[row][col] + R[row][col] + U[row][col] + D[row][col] - 3
            num_max = max(num_max, s_num)
    print(num_max)

if __name__ == "__main__":
    D_Lamp()

### FIXED CODE ###

def D_Lamp():
    import numpy as np
    # input & init
    h, w = map(int, input().split())
    S = np.array([list(input()) for _ in range(h)]) == "."
    L = np.zeros((h,w), dtype=int)
    R = np.zeros((h,w), dtype=int)
    U = np.zeros((h,w), dtype=int)
    D = np.zeros((h,w), dtype=int)
    # calc row
    for row in range(h):
        D[row] =(D[row - 1] + 1) * S[row]
        U[-row - 1] = (U[-row] + 1) * S[-row -1]
    # calc col
    for col in range(w):
        R[:, col] = (R[:, col - 1] + 1) * S[:, col]
        L[:, -col - 1] = (L[:, -col] + 1) * S[:, -col-1]
    num_max = 0
    print(np.max(L+R+U+D) - 3)

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

import sys
input=sys.stdin.readline
from bisect import bisect_left 
from collections import deque

def count_edge(a,b):
    if a>b:
        a,b=b,a
    edge[bisect_left(AB,(a,b))]+=1

N,M=map(int,input().split())
data=[[] for i in range(N+1)]
AB=[]
edge=[0]*M
count=[0]*(N+1)
for i in range(M):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    AB.append((A,B))
    data[A].append(B)
    data[B].append(A)
    count[A]+=1
AB.sort()

if M%2==1:
    print(-1)
    sys.exit()

parent=[0]*(N+1)
que=[1]
flag=[0]*(N+1)
flag[1]=1
parent[1]=1
lsls=deque([])
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                parent[v]=u
                h.append(v)
                if count[v]%2==1:
                    lsls.appendleft(v)
    que=h

for i in lsls:
    if count[i]%2==0:
        continue
    else:
        count[i]+=1
        while True:
            j=parent[i]
            if i==j:
                break
            count_edge(i,j)
            if count[j]%2==1:
                count[j]+=1
                break
            i=j
            
for i in range(M):
    if edge[i]%2==0:
        print(*AB[i])
    else:
        print(*AB[i][::-1])

### FIXED CODE ###

import sys
input=sys.stdin.readline
from bisect import bisect_left 
from collections import deque

def count_edge(a,b):
    global edge,AB
    if a>b:
        a,b=b,a
    edge[bisect_left(AB,(a,b))]+=1

def main():
    global edge,AB
    N,M=map(int,input().split())
    data=[[] for i in range(N+1)]
    AB=[]
    edge=[0]*M
    count=[0]*(N+1)
    for i in range(M):
        A,B=map(int,input().split())
        if A>B:
            A,B=B,A
        AB.append((A,B))
        data[A].append(B)
        data[B].append(A)
        count[A]^=1
    AB.sort()

    if M%2==1:
        print(-1)
        sys.exit()

    parent=[0]*(N+1)
    que=[1]
    parent[1]=1
    lsls=deque([])
    while que:
        h=[]
        for u in que:
            for v in data[u]:
                if parent[v]==0:
                    parent[v]=u
                    h.append(v)
                    if count[v]%2==1:
                        lsls.appendleft(v)
        que=h

    for i in lsls:
        if count[i]==0:
            continue
        else:
            count[i]=0
            while True:
                j=parent[i]
                if i==j:
                    break
                count_edge(i,j)
                if count[j]==1:
                    count[j]=0
                    break
                i=j
            
    for i in range(M):
        if edge[i]%2==0:
            print(*AB[i])
        else:
            print(*AB[i][::-1])
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = [input() for i in range(N)]
ans = 0
for i in range(N):
    wk = A[:]
    wk.pop(i)
    wk.sort()
    ans = wk[-1]
    print(ans)

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
Max1 = max(A)
indexes = [i for i, x in enumerate(A) if x == Max1]
if len(A) == len(indexes):
    for i in A:
        print(i)
else:
    Max2 = sorted(set(A))[-2]
    if len(indexes) >= 2:
        for i in range(N):
            print(Max1)
    else:
        for i in range(N):
            ans = Max2 if A[i] == Max1 else Max1
            print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
lst=[i for i in range(a,b+1) if a<=i<=a+k-1 or b-k+1<=i<=b]
for j in range(len(lst)):
  print(lst[j])

### FIXED CODE ###

a,b,k=map(int,input().split())
lst=[]
for i in range(a,min(a+k, b)):
  lst.append(i)
  print(i)
for j in range(max(a, b-k+1),b+1):
  if j not in lst:
    print(j)
### BUGGY CODE ###

n, k, q = map(int, input().split())
answerer = []
for i in range(q):
    answerer.append(int(input()))
for i in range(1,n+1):
    count_ans = answerer.count(i)
    last_point = count_ans + k - q
    if last_point > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
point = [k-q]*n
for i in range(q):
    answerer = int(input())-1
    point[answerer] += 1
for i in range(n):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")