Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
data = [tuple(map(int, input().split())) for _ in range(N)]
data.sort(key=lambda x: x[2])
for cx in range(101):
    for cy in range(101):
        h0 = None
        for x, y, h in data:
            if h:
                h_tmp = h + abs(cx - x) + abs(cy - y)
                if h_tmp != h0 and h0 is not None:
                    break
                h0 = h_tmp
            else:
                if abs(cx - x) + abs(cy - y) < h0:
                    break
        else:
            print(cx, cy, h0)
            exit()


Fixed submission:
N = int(input())
data = [tuple(map(int, input().split())) for _ in range(N)]
data.sort(key=lambda x: -x[2])
for cx in range(101):
    for cy in range(101):
        h0 = None
        for x, y, h in data:
            if h:
                h_tmp = h + abs(cx - x) + abs(cy - y)
                if h_tmp != h0 and h0 is not None:
                    break
                h0 = h_tmp
            else:
                if abs(cx - x) + abs(cy - y) < h0:
                    break
        else:
            print(cx, cy, h0)
            exit()

Buggy python submission (verdict: Runtime Error):
N = int(input())
data = [tuple(map(int, input().split())) for _ in range(N)]
data.sort(key=lambda x: x[2])
for cx in range(101):
    for cy in range(101):
        h0 = None
        for x, y, h in data:
            if h:
                if (h_tmp := h + abs(cx - x) + abs(cy - y)) != h0 and h0 is not None:
                    break
                h0 = h_tmp
            else:
                if abs(cx - x) + abs(cy - y) < h0:
                    break
        else:
            print(cx, cy, h0)
            exit()


Fixed submission:
N = int(input())
data = [tuple(map(int, input().split())) for _ in range(N)]
data.sort(key=lambda x: -x[2])
for cx in range(101):
    for cy in range(101):
        h0 = None
        for x, y, h in data:
            if h:
                h_tmp = h + abs(cx - x) + abs(cy - y)
                if h_tmp != h0 and h0 is not None:
                    break
                h0 = h_tmp
            else:
                if abs(cx - x) + abs(cy - y) < h0:
                    break
        else:
            print(cx, cy, h0)
            exit()
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

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

lst = [[0] * 3 for _ in range(C)]
for y in range(N):
    for x in range(N):
        for c in range(C):
            lst[c][(x + y) % 3] += D[L[y][x] - 1][c]

ans = float('inf')
for t in itertools.permutations(range(C),3):
    ans = min(ans, sum(lst[t[i]][i] for i in range(3)))
print(ans)


Fixed submission:
import itertools

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

lst = [[0] * 3 for _ in range(C)]
for y in range(N):
    for x in range(N):
        for c in range(C):
            lst[c][(x + y) % 3] += D[L[y][x] - 1][c]

ans = float('inf')
for t in itertools.permutations(range(C), 3):
    ans = min(ans, sum(lst[t[i]][i] for i in range(3)))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N = int(input())
edge = np.array([tuple(map(int, input().split())) for _ in range(N - 1)]).T
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

matr = csr_matrix((edge[2], (edge[0] - 1, edge[1] - 1)), (N, N))
way = tuple(dijkstra(matr, indices=K - 1, directed=False).astype(np.int64))
for x, y in query:
    print(way[x - 1] + way[y - 1])

Fixed submission:
from collections import deque

N = int(input())

T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))
Q, K = map(int, input().split())

# dfs
table = [0] * N
D = deque([K - 1])
visited = set()
while D:
    v = D.pop()
    visited.add(v)
    for x, d in T[v]:
        if x not in visited:
            table[x] = table[v] + d
            D.append(x)

for _ in range(Q):
    x, y = map(int, input().split())
    print(table[x - 1] + table[y - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N = int(input())
edge = np.array([tuple(map(int, input().split())) for _ in range(N - 1)]).T
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

matr = csr_matrix((edge[2], (edge[0] - 1, edge[1] - 1)), (N, N))
way = dijkstra(matr, indices=K - 1, directed=False).astype(np.int64)
for x, y in query:
    print(way[x - 1] + way[y - 1])

Fixed submission:
from collections import deque

N = int(input())

T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))
Q, K = map(int, input().split())

# dfs
table = [0] * N
D = deque([K - 1])
visited = set()
while D:
    v = D.pop()
    visited.add(v)
    for x, d in T[v]:
        if x not in visited:
            table[x] = table[v] + d
            D.append(x)

for _ in range(Q):
    x, y = map(int, input().split())
    print(table[x - 1] + table[y - 1])
Buggy python submission (verdict: Runtime Error):
K = int(input())
N = 50
while not K % N:
    N -= 1
ans = [K // N + N] * (K % N) + [K // N + N - K % N - 1] * (N - K % N)
print(N)
print(*ans)

Fixed submission:
K = int(input())

N = 50
ans = [K // N + N] * (K % N) + [K // N + N - K % N - 1] * (N - K % N)
print(N)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx

G = nx.DiGraph()

N, M = map(int, input().split())
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, weight=-c)

rev = G.reverse(copy=False)
c = nx.unweighted.single_source_shortest_path(rev, N).keys()
sG = G.subgraph(c)

try:
    print(-nx.bellman_ford_path_length(sG, 1, N))
except nx.NetworkXUnbounded:
    print('inf')


Fixed submission:
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
frm, to, length = [], [], []
for _ in range(M):
    a, b, c = map(int, input().split())
    frm.append(a - 1)
    to.append(b - 1)
    length.append(-c)

# N-1→0の辺を追加してから卿連結判定⇒ゴールにたどり着けない閉路を除外
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')

Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx

G = nx.DiGraph()

N, M = map(int, input().split())
G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, weight=-c)

cG = G.copy()
cG.add_edge(N, 1)
for c in nx.strongly_connected_components(cG):
    if 1 in c:
        sG = G.subgraph(c)
        break
try:
    print(-nx.bellman_ford_path_length(sG, 1, N))
except nx.NetworkXUnbounded:
    print('inf')


Fixed submission:
from scipy.sparse.csgraph import connected_components, bellman_ford, NegativeCycleError
from scipy.sparse import csr_matrix

N, M = map(int, input().split())
frm, to, length = [], [], []
for _ in range(M):
    a, b, c = map(int, input().split())
    frm.append(a - 1)
    to.append(b - 1)
    length.append(-c)

# N-1→0の辺を追加してから卿連結判定⇒ゴールにたどり着けない閉路を除外
connect_check = csr_matrix(([1] * (M + 1), (frm + [N - 1], to + [0])), shape=(N, N))
_, labels = connected_components(connect_check, connection='strong')
label_num = labels[0]
frm_c, to_c, length_c = [], [], []
for i in range(M):
    if labels[frm[i]] == labels[to[i]] == label_num:
        frm_c.append(frm[i])
        to_c.append(to[i])
        length_c.append(length[i])

matr = csr_matrix((length_c, (frm_c, to_c)), shape=(N, N))

try:
    ans = -int(bellman_ford(matr, indices=0)[N - 1])
    print(ans)
except NegativeCycleError:
    print('inf')
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
tmp = math.isqrt(N)
while N % tmp:
    tmp -= 1
print(len(str(N // tmp)))


Fixed submission:
import math

N = int(input())

tmp = math.floor(math.sqrt(N))
while N % tmp:
    tmp -= 1
print(len(str(N // tmp)))
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 5)

N = int(input())
T = [[] for _ in range(N)]
for i in range(1, N):
    x = int(input()) - 1
    T[x].append(i)


def f(x):
    candidates = sorted([f(y) for y in T[x]], reverse=True)
    return max((c + i for i, c in enumerate(candidates, 1)), default=0)


print(f(0))


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)

N = int(input())
T = [[] for _ in range(N)]
for i in range(1, N):
    x = int(input()) - 1
    T[x].append(i)


def f(x):
    candidates = sorted([f(y) for y in T[x]], reverse=True)
    return max((c + i for i, c in enumerate(candidates, 1)), default=0)


print(f(0))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

int1 = lambda x: int(x) - 1

H, W, N = map(int, input().split())
B = set(tuple(map(int1, input().split())) for _ in range(N))

adj = (-1, 0, 1)
visited = set()
ans = [0] * 10
for a, b in B:
    for dy, dx in itertools.product(adj, repeat=2):
        if not (1 <= a + dy < H - 1 and 1 <= b + dx < W - 1):
            continue
        elif (a + dy, b + dx) in visited:
            continue
        visited.add((a + dy, b + dx))
        c = 0
        for ddy, ddx in itertools.product(adj, repeat=2):
            if (a + dy + ddy, b + dx + ddx) in B:
                c += 1
        ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
for x in ans:
    print(x)


Fixed submission:
import itertools

int1 = lambda x: int(x) - 1

H, W, N = map(int, input().split())
B = set(tuple(map(int1, input().split())) for _ in range(N))

adj = (-1, 0, 1)
visited = set()
ans = [0] * 10
for a, b in B:
    for dy, dx in itertools.product(adj, repeat=2):
        if not (1 <= a + dy < H - 1 and 1 <= b + dx < W - 1):
            continue
        elif (a + dy, b + dx) in visited:
            continue
        visited.add((a + dy, b + dx))
        c = 0
        for ddy, ddx in itertools.product(adj, repeat=2):
            if (a + dy + ddy, b + dx + ddx) in B:
                c += 1
        ans[c] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans[1:])
for x in ans:
    print(x)
Buggy python submission (verdict: Runtime Error):
s,w = map(input().split(), int)
print("unsafe" if w >= s else "safe")

Fixed submission:
s,w = map(int, input().split())
print("unsafe" if w >= s else "safe")

Buggy python submission (verdict: Runtime Error):
s = int(input())
w = int(input())
print "unsafe" if w>=s else "safe"

Fixed submission:
s,w = map(int, input().split())
print("unsafe" if w >= s else "safe")
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = sorted([a + b for a in A for b in B])[-1:-K-1:-1]
ABC = sorted([ab + c for ab in AB for c in C])[-1:-K-1:-1]
print('\n'.join(map(str, ABC)))


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

AB = sorted([a + b for a in A for b in B])[-1:-K-1:-1]
ABC = sorted([ab + c for ab in AB for c in C])[-1:-K-1:-1]
print('\n'.join(map(str, ABC)))
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 * 18]*n for j in range(n)]
for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = 10**18
for p in itertools.permutations(t):
    now = 0
    for i in range(r-1):
        now += d[p[i]-1][p[i + 1]-1]
    ans = min(ans, now)
print(ans)


Fixed submission:
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 ** 18]*n for j in range(n)]
for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = 10**18
for p in itertools.permutations(t):
    now = 0
    for i in range(r-1):
        now += d[p[i]-1][p[i + 1]-1]
    ans = min(ans, now)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
for i in range(r):
    t[i] -= 1
d = [[10 * 18 for i in range(n)] for j in range(n)]
for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

perm = []
for i in range(r):
    perm.append(i)
ans = 10**18
for p in itertools.permutations(perm):
    now = 0
    for i in range(r-1):
        now += d[t[p[i]]][t[p[i + 1]]]
    ans = min(ans, now)
print(ans)


Fixed submission:
import itertools
n, m, r = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
d = [[10 ** 18]*n for j in range(n)]
for i in range(n):
    d[i][i] = 0

for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])


ans = 10**18
for p in itertools.permutations(t):
    now = 0
    for i in range(r-1):
        now += d[p[i]-1][p[i + 1]-1]
    ans = min(ans, now)
print(ans)
Buggy python submission (verdict: Runtime Error):
# import math
# import statistics
a=input()
b=input()
#b,c=int(input()),int(input())
c,d=[],[]
for i in a:
    c.append(i)
for i in b:
    d.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))
ma=[]
if b in a:
    print(0)
else:
    for i in range(len(c)-len(d)+1):
        count=0
        for k in range(len(d)):
            if c[i:len(d)+i][k]!=d[k]:
                count+=1
        ma.append(count)

print(min(ma))

Fixed submission:
# import math
# import statistics
a=input()
b=input()
#b,c=int(input()),int(input())
c,d=[],[]
for i in a:
    c.append(i)
for i in b:
    d.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))
ma=[]
if b in a:
    print(0)
else:
    for i in range(len(c)-len(d)+1):
        count=0
        for k in range(len(d)):
            if c[i:len(d)+i][k]!=d[k]:
                count+=1
        ma.append(count)
    print(min(ma))
Buggy python submission (verdict: Time Limit Exceeded):
# import math
# import statistics
# import itertools
# a=int(input())
# b=input()
# c=[]
# for i in a:
#     c.append(int(i))
N,K= map(int,input().split())
# f = list(map(int,input().split()))
# g = [int(input()) for _ in range(N)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen
mi=N
count=0
while True:
    if N%K==0:
        print(0)
        exit()
    N=abs(N-K)
    if N<=mi:
        mi=min(mi,N)
        count+=1
    else :
        print(mi)
        exit()




Fixed submission:
# import math
# import statistics
# import itertools
# a=int(input())
# b=input()
# c=[]
# for i in a:
#     c.append(int(i))
N,K= map(int,input().split())
# f = list(map(int,input().split()))
# g = [int(input()) for _ in range(N)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen

if N%K==0:
    print(0)
else:
    et=N//K
    a1=et*K
    a2=(et+1)*K
    mi = min(abs(a1-N),abs(a2-N))
    print(mi)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import statistics
a=int(input())
#b,c=int(input()),int(input())
# c=[]
# for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
j = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))
s=set(j)
s2=list(s)
s2.sort()
an = []
for i in s2:
    an.append(j.count(i))
s4=[i for i, v in enumerate(an) if v == max(an)]
for i in s4:
    print(s2[i])

Fixed submission:
import math
import statistics
import collections
a=int(input())
#b,c=int(input()),int(input())
# c=[]
#  for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
g = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))

g.sort()

ma=0
count=1
#最大値求める
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        ma=max(ma,count)
        count=1

ma=max(ma,count)
count=1
ans=[]
#最大値の位置
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        if count==ma:
            ans.append(g[i])
        count=1
if count==ma:
    ans.append(g[-1])

for i in ans:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
import math
import statistics
a=int(input())
#b,c=int(input()),int(input())
# c=[]
# for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
j = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))
s=set(j)
s2=list(s)
s3=sorted(s2)
an = []
for i in s3:
    an.append(j.count(i))
s4=[i for i, v in enumerate(an) if v == max(an)]
for i in s4:
    print(s3[i])

Fixed submission:
import math
import statistics
import collections
a=int(input())
#b,c=int(input()),int(input())
# c=[]
#  for i in b:
#     c.append(i)
#e1,e2 = map(int,input().split())
# f = list(map(int,input().split()))
g = [input() for _ in range(a)]
# h = []
# for i in range(e1):
#     h.append(list(map(int,input().split())))

g.sort()

ma=0
count=1
#最大値求める
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        ma=max(ma,count)
        count=1

ma=max(ma,count)
count=1
ans=[]
#最大値の位置
for i in range(a-1):
    if g[i]==g[i+1]:
        count+=1
    else:
        if count==ma:
            ans.append(g[i])
        count=1
if count==ma:
    ans.append(g[-1])

for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
a = list(map(int,input().split()))
#b = list(map(int,input().split()))
count=0
for i in range(s):
    for k in range(s):
        if  a[i]==a[k]:
            count+=1

if count<=s:
    print("YES")
else:
    print("NO")

Fixed submission:
s=int(input())
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
a = list(map(int,input().split()))
#b = list(map(int,input().split()))

c = {i for i in a}  

if len(a)==len(c):
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
b = list(map(int,input().split()))

b.sort(reverse=True)
for i in  range(a[1]):
    del b[0]
print(sum(b))


Fixed submission:
a = list(map(int,input().split()))
b = list(map(int,input().split()))

if len(b) <= a[1]:
    print("0")
elif a[1]==0:
    print(sum(b))
else:
    b.sort(reverse=True)
    print(sum(b[a[1]:]))

Buggy python submission (verdict: Runtime Error):
a = list(map(int,input().split()))
b = list(map(int,input().split()))

b.sort(reverse=True)
for i in  range(a[1]):
        del b[0]
    print(sum(b))

Fixed submission:
a = list(map(int,input().split()))
b = list(map(int,input().split()))

if len(b) <= a[1]:
    print("0")
elif a[1]==0:
    print(sum(b))
else:
    b.sort(reverse=True)
    print(sum(b[a[1]:]))

Buggy python submission (verdict: Time Limit Exceeded):
a = list(map(int,input().split()))
b = list(map(int,input().split()))

b.sort(reverse=True)

if len(b) <= a[1]:
    print("0")
else :
    for i in  range(a[1]):
        del b[0]
    print(sum(b))


Fixed submission:
a = list(map(int,input().split()))
b = list(map(int,input().split()))

if len(b) <= a[1]:
    print("0")
elif a[1]==0:
    print(sum(b))
else:
    b.sort(reverse=True)
    print(sum(b[a[1]:]))
Buggy python submission (verdict: Time Limit Exceeded):
import math
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
#a = list(map(int,input().split()))
#b = list(map(int,input().split()))
s=int(input())
count=0
for i in range(s):
	for k in range(i,s):
		if i+k==s and i!=k:
			count+=1
print(count)

Fixed submission:
import math
# b=input()
# c=[]
# for i in range(b):
#     c.append(a[i])
#a = list(map(int,input().split()))
#b = list(map(int,input().split()))
s=int(input())

a = math.ceil(s/2)
print(a-1)
Buggy python submission (verdict: Time Limit Exceeded):
# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))

ans=[]
ha1=[]
ha = [k for i in range(e2) for k in range(1,e1+1) if h[i][0]<=k<=h[i][1]]
sha=sorted(ha)

ma=0

count=1
#最大値求める
for i in range(len(sha)-1):
    if sha[i]==sha[i+1]:
        count+=1
    else:
        if count>=e2:
            ha1.append(count)
        count=1

if count>=e2:
    ha1.append(count)
print(len(ha1))



# for i in range(1,e1+1):
#     count=0
#     for k in range(e2):
#         if h[k][0]<=i<=h[k][1]:
#             count+=1
#     if count==e2:
#         ans.append(count)

# print(len(ans))
    




Fixed submission:
# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))
L=[]
R=[]
for i in range(len(h)):
    L.append(h[i][0])
for i in range(len(h)):
    R.append(h[i][1])

if min(R)>=max(L):
    print(min(R)-max(L)+1)
else:
    print(0)

Buggy python submission (verdict: Time Limit Exceeded):
# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))

ans=[]

for i in range(1,e1+1):
    count=0
    for k in range(e2):
        if h[k][0]<=i<=h[k][1]:
            count+=1
    if count==e2:
        ans.append(count)

print(len(ans))
    





Fixed submission:
# import math
# import statistics
# a=input()
#b,c=int(input()),int(input())
# c=[]
# for i in a:
#     c.append(i)
e1,e2 = map(int,input().split())
#f = list(map(int,input().split()))
#g = [input() for _ in range(a)]
h = []
for i in range(e2):
    h.append(list(map(int,input().split())))
L=[]
R=[]
for i in range(len(h)):
    L.append(h[i][0])
for i in range(len(h)):
    R.append(h[i][1])

if min(R)>=max(L):
    print(min(R)-max(L)+1)
else:
    print(0)