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



class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

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

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] == self.r[y]:
            self.r[x] += 1
        elif self.r[x] > self.r[y]:
            x, y = y, x
        self.p[x] = y

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

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###



class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

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

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] < self.r[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.r[x] == self.r[y]:
                self.r[x] += 1

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


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

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from math import gcd
from fractions import Fraction as Fc

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        f = Fc(a,b)
        cnd[f] = cnd.get(f,0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod

#print(cnd)
for k,item in cnd.items():
#    print(k)
    if k>0:
        m = cnd.get(Fc(-1,k),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get(Fc(-1,k),False)
#        print(m,k,Fc(-1,k))
        if not m:
            noreg += item
#    print(ans,noreg)
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

### FIXED CODE ###

def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from fractions import Fraction
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] = cnd.get((a,b),0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod
#print('ans block')
#print(ans,noreg)
#print(cnd)
for k,item in cnd.items():
    a,b = k
    if b>0:
        m = cnd.get((b,-a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))
### BUGGY CODE ###

import bisect

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

count = 0
for i in range(n):
    b = bisect.bisect(B,A[i])
    for j in range(b,n):
        c = bisect.bisect(C,B[j])
        count += n-c

print(count)

### FIXED CODE ###

import bisect

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

count = 0

for i in range(n):
    a = bisect.bisect_left(A,B[i])
    c = bisect.bisect_right(C,B[i])
    count += a*(n-c)
    
print(count)
### BUGGY CODE ###

import math
import queue

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = input()

ai = [0]*len(s)
si = [0]*len(s)

p = 2019

for i in range(len(s)):
	ai[i] = (int(s[-1*i-1])*pow(10,i))%p
for i in range(len(ai)):
	si[i] = sum(ai[:i+1])%p
	#print(ai[:i+1],1)
countarr = [0]*2019
for i in si:
	countarr[i]+=1

res = si.count(0)
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)

### FIXED CODE ###

import math

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()

s = reversed(input())

ai = 0
si = 0

p = 2019
countarr = [0]*2019

for i, j in enumerate(s):
	ai = (int(j)*pow(10,i,p))%p
	si = (si+ai)%p
	countarr[si]+=1

res = countarr[0]
for i in range(p):
	c = countarr[i]
	res += c*(c-1)//2

print(res)
### BUGGY CODE ###

s = input()
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s = c + s
    else:
        s = s + c
        
if f:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))
### BUGGY CODE ###

import sys
import heapq
import copy

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

for _ in range(n):
	a.append(-1 * int(input()))

for i in range(n):
	b = copy.deepcopy(a)
	b.remove(a[i])
	heapq.heapify(b)
	print(heapq.heappop(b) * (-1))


### FIXED CODE ###

import sys
import heapq
import copy

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

for _ in range(n):
	a.append(-1 * int(input()))

b = copy.deepcopy(a)
heapq.heapify(b)

for i in range(n):
	maximum = heapq.heappop(b)
	if maximum == a[i]:
		tmp = maximum
		maximum = heapq.heappop(b)
		print(maximum * (-1))
		heapq.heappush(b,tmp)
	else:
		print(maximum * (-1))
	heapq.heappush(b,maximum)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            if c in color_used[j]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

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

n = int(input())
list_a = []
list_b = []
su = 0
for i in range(n):
  a,b = map(int,input().split())
  list_a.append(a)
  list_b.append(b)
list_a = list_a[::-1]
list_b = list_b[::-1]
for i in range(n):
  if list_a[i]%list_b[i]==0:
    continue
  else:
    x = list_b[i]-(list_a[i]%list_b[i])
    su += x
    for j in range(i,n):
      list_a[j] += x
 # print(list_a)
print(su)


### FIXED CODE ###

n = int(input())
list_a = []
list_b = []
su = 0
for i in range(n):
  a,b = map(int,input().split())
  list_a.append(a)
  list_b.append(b)
list_a = list_a[::-1]
list_b = list_b[::-1]
for i in range(n):
  list_a[i] += su
  if list_a[i]%list_b[i]==0:
    continue
  else:
    x = list_b[i]-(list_a[i]%list_b[i])
    su += x
#  print(list_a)
print(su)
### BUGGY CODE ###

#!/usr/bin/env python3
import collections

H, W, M = map(int, input().split())
tate = []
yoko = []
S = []

for i in range(M):
    h, w = map(int, input().split())
    tate.append(h-1)
    yoko.append(w-1)
    S.append([h-1, w-1])

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in range(len(yoko_index)):
    for j in range(len(tate_index)):
        if [tate_index[j], yoko_index[i]] in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)


### FIXED CODE ###

#!/usr/bin/env python3
import collections

H, W, M = map(int, input().split())
tate = []
yoko = []
S = set()

for i in range(M):
    h, w = map(int, input().split())
    tate.append(h-1)
    yoko.append(w-1)
    S.add((h-1, w-1))

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in yoko_index:
    for j in tate_index:
        if (j, i) in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)
### BUGGY CODE ###

n = int(input()) #1行目のNを取得する
list = [input() for i in range(n)] #複数行の数値の入力を取得
lint = [int(s) for s in list]

for i in range(n):
    s = lint.pop(0)
    lints = sorted(lint, reverse=True)
    ans = lints[0]
    print(ans)
    lint.append(s)

### FIXED CODE ###

n = int(input()) #1行目のNを取得する
list = [input() for i in range(n)] #複数行の数値の入力を取得
lint = [int(s) for s in list]

ans = max(lint)
index = lint.index(max(lint))
lint.remove(max(lint))
ans2 = max(lint)

if ans == ans2:
    for i in range(n):
        print(ans)
else:
    for i in range(0, index):
        print(ans)
    print(ans2)
    for i in range(index+1, n):
        print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
mx = 10**10
for i in range(n):
    if a[i] < mx:
        mx = a[i]
        mi =  i
a = a[i:]+a[:i]
for v in range(0,2*(a[0]+1),2):
    mou[0] = v
    for i in range(1,n):
        mou[i] = (a[i-1]-mou[i-1]//2)*2
    if (mou[-1]+mou[0])//2 == a[-1]:
        ans = mou[n-i:]+mou[:n-i]
        break
print(" ".join(map(str,ans))) 

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mou = [0]*n
for i in range(1,n):
  mou[i*2%n] =  mou[(i-1)*2%n] + (a[i*2%n-1]-a[(i-1)*2%n])*2
mous = 0
for i in range(n):
  mous += a[i]-mou[i]
p = mous//n
for i in range(n):
  mou[i] += p
print(" ".join(map(str,mou)))
### BUGGY CODE ###

import sys

H,W=map(int,sys.stdin.readline().split())
A=[[None]*(W+2)]+\
  [[None] + [i=="." for i in sys.stdin.readline()] + [None] for _ in range(H)] + \
  [[None]*(W+2)]
 
cnt=0
q,r=[],[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==False:
            q.append((i,j))
if len(q)==H*W:
    print(0)
    sys.exit()
for k in range(2000):
    for i,j in q:
        if A[i-1][j]:
            A[i-1][j]=False
            r.append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=False
            r.append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=False
            r.append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=False
            r.append((i,j+1))
    q=[i for i in r]
    r=[]
    if q==[]:
        break
    cnt+=1
print(cnt)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
N = int(sys.stdin.readline()[:-1])
sum = 0
for i in range(N):
    sum += i
print(sum)


### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

a,b,q=map(int,input().split())
s=[]
for _ in range(a):
    s.append(int(input()))
t=[]
for _ in range(b):
    t.append(int(input()))
import bisect
for _ in range(q):
    x=int(input())
    sb=bisect.bisect_left(s,x)
    tb=bisect.bisect_left(t,x)
    ss=[x-s[max(sb-1,0)],x-s[min(sb,a-1)]]
    tt=[x-t[max(tb-1,0)],x-t[min(tb,b-1)]]
    l=[]
    for i in ss:
        for j in tt:
            if i*j>=0:
                l.append(max(abs(i),abs(j)))
            else:
                l.append(max(abs(i),abs(j))+2*min(abs(i),abs(j)))
    print(min(l))


### FIXED CODE ###

a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
import bisect
for _ in range(q):
    x=int(input())
    sb=bisect.bisect_left(s,x)
    tb=bisect.bisect_left(t,x)
    ss=[x-s[max(sb-1,0)],x-s[min(sb,a-1)]]
    tt=[x-t[max(tb-1,0)],x-t[min(tb,b-1)]]
    l=[]
    for i in ss:
        for j in tt:
            if i*j>=0:
                l.append(max(abs(i),abs(j)))
            else:
                l.append(max(abs(i),abs(j))+2*min(abs(i),abs(j)))
    print(min(l))
### BUGGY CODE ###

N, M, R = [int(_) for _ in input().split()]
r = [int(_) for _ in input().split()]

from collections import defaultdict
from itertools import permutations

INF = 10**10

D = defaultdict(lambda:INF)

for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    D[a, b] = c
    D[b, a] = c

result = INF

# warshall_floyd
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            D[j, k] = min(D[j, k], D[j, i] + D[i, k])

for xs in permutations(r):
    r = 0
    for i in range(R - 1):
        st, ed = xs[i], xs[i + 1]
        r += D[st, ed]
    result = min(result, r)

print(result)


### FIXED CODE ###

N, M, R = [int(_) for _ in input().split()]
r = [int(_) - 1 for _ in input().split()]

from collections import defaultdict
from itertools import permutations

INF = 10**10

D = [[INF] * N for _ in range(N)]

for i in range(M):
    a, b, c = [int(_) for _ in input().split()]
    D[a-1][b-1] = c
    D[b-1][a-1] = c

result = INF

# warshall_floyd
for i in range(N):
    for j in range(N):
        for k in range(N):
            D[j][k] = min(D[j][k], D[j][i] + D[i][k])

for xs in permutations(r):
    r = 0
    for i in range(R - 1):
        st, ed = xs[i], xs[i + 1]
        r += D[st][ed]
    result = min(result, r)

print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    map = [[0 for _ in range(W)] for _ in range(H)]
    que = []
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.pop(0)
        # 左
        if xw - 1 >= 0:
            if Sn[xh][xw] != Sn[xh][xw-1] and map[xh][xw-1] == 0:
                que.append((xh, xw-1))
                map[xh][xw-1] = Sn[xh][xw-1]
        # 上
        if xh - 1 >= 0:
            if Sn[xh][xw] != Sn[xh-1][xw] and map[xh-1][xw] == 0:
                que.append((xh-1, xw))
                map[xh-1][xw] = Sn[xh-1][xw]
        # 右
        if xw + 1 < W:
            if Sn[xh][xw] != Sn[xh][xw+1] and map[xh][xw+1] == 0:
                que.append((xh, xw+1))
                map[xh][xw+1] = Sn[xh][xw+1]
        # 下
        if xh + 1 < H:
            if Sn[xh][xw] != Sn[xh+1][xw] and map[xh+1][xw] == 0:
                que.append((xh+1, xw))
                map[xh+1][xw] = Sn[xh+1][xw]

    return map
    # cnt = 0
    # for i in range(H):
    #     for j in range(W):
    #         if map[i][j] == ".":
    #             cnt += 1
    # return cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            ret = func(i,j)
            b_cnt = 0
            w_cnt = 0
            for i2 in range(H):
                for j2 in range(W):
                    if ret[i2][j2] == "#":
                        b_cnt += 1
                        visited[i2][j2] = 1
                    elif ret[i2][j2] == ".":
                        w_cnt += 1
            
            cnt += b_cnt*w_cnt
            
print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
H, W = list(map(int, input().split()))
Sn = [input() for _ in range(H)]

def func(h,w): # 黒のみ
    move = [(0,-1),(-1,0),(0,1),(1,0)]
    w_cnt = 0
    b_cnt = 0
    que = deque()
    que.append((h,w))
    while len(que) > 0:
        xh,xw = que.popleft()
        if visited[xh][xw] == 0:
            visited[xh][xw] = 1
            if Sn[xh][xw] == "#":
                b_cnt += 1
            else:
                w_cnt += 1
        else:
            continue
            
        for mh, mw in move:
            if 0 <= xh + mh < H and 0 <= xw + mw < W:
                if Sn[xh][xw] != Sn[xh + mh][xw + mw] and visited[xh + mh][xw + mw] == 0:
                    que.append((xh + mh, xw + mw))

    return b_cnt, w_cnt

cnt = 0
visited = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if Sn[i][j] == "#" and visited[i][j]==0:
            b_cnt, w_cnt = func(i, j)
            cnt += b_cnt*w_cnt
            
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = [int(x) for x in input().split()]

    answer = set()
    for i in range(M):
        L, R = [int(x) for x in input().split()]
        if i == 0:
            answer = {x for x in range(L, R + 1)}
        else:
            s = {x for x in range(L, R + 1)}
            answer &= s

    print(len(answer))




if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = [int(x) for x in input().split()]

    A = []
    for i in range(M):
        A.append([int(x) for x in input().split()])

    answer = A[0]
    for i in range(1, M):
        if max(answer) < min(A[i]) or max(A[i]) < min(answer):
            print(0)
            exit()

        total = []
        total.extend(answer)
        total.extend(A[i])
        s_total = sorted(total)
        answer = s_total[1:3]

    print(answer[1] - answer[0] + 1)




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

import sys
from itertools import accumulate

input = lambda: sys.stdin.readline().rstrip()
n, m, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [0] + a
b = [0] + b
# 累積和を利用
a_accum = list(accumulate(a))
b_accum = list(accumulate(b))

ans = 0
for i in range(len(a_accum)):
    for j in range(len(b_accum)):
        if (a_accum[i] + b_accum[j] <= k):
            ans = max(ans, i + j)
print(ans)


### FIXED CODE ###

import sys
from itertools import accumulate
import bisect

input = lambda: sys.stdin.readline().rstrip()
n, m, k = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = [0] + a
b = [0] + b
# 累積和を利用
a_accum = list(accumulate(a))
b_accum = list(accumulate(b))

# print(a_accum, b_accum)

ans = 0
for i in range(len(a_accum)):
    nokori = k - a_accum[i]
    if nokori < 0:
        break
    # にぶたん
    b_pos = bisect.bisect(b_accum, nokori) - 1
    ans = max(ans, i + b_pos)
    # print(nokori,ans,b_pos)
print(ans)