Harryxun/sft_time huggingface dataset:
### 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()
b_ceil = [n]*len(b)
b_floor = [n]*len(b)
count = 0
for i in range(len(b)):
    for j in range(len(a)):
        if a[j] >= b[i]:
            b_ceil[i] = j
            break
    for k in range(len(c)):
        if b[i] < c[k]:
            b_floor[i] = n-k
            break
    count += b_ceil[i] * b_floor[i]

print(count)

### FIXED 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()
b_ceil = [n]*len(b)
b_ceil.insert(0, 0)
b_floor = [n]*len(b)
b_floor.insert(0, 0)
count = 0
for i in range(len(b)):
    for j in range(b_ceil[i], len(a)):
        if a[j] >= b[i]:
            b_ceil[i+1] = j
            break
    for k in range(b_floor[i], len(c)):
        if b[i] < c[k]:
            b_floor[i+1] = k
            break
    count += b_ceil[i+1] * (n - b_floor[i+1])

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

from collections import Counter

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

for k in range(N):
    ans = 0
    res = c.copy()
    res[A[k]] -= 1
    for ri in res.values():
        n = ri
        ans += n * (n-1) // 2
    print(ans)


### FIXED CODE ###

from collections import Counter

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

# 先にk番目を抜かない場合を求めておく
ans = 0
for n in c.values():
    ans += n*(n-1)//2

# k番目を抜く場合の差分を加える
for k in range(N):
    m = c[A[k]]
    print(ans - (m-1))  # -m*(m-1)//2 + (m-1)*(m-2)//2
### BUGGY CODE ###

# coding: utf-8

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

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	start = 0
	ans = []
	x = []
	while True:
		k = kmp.search(start)
		if k == -1 or k == len(a):
			break
		ans.append(k)
		start = k + 1
		x.append(a[0 + k] ^ b[0])

	for i in range(len(ans)):
		print(str(ans[i]) + " " + str(x[i]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def search(self, start=0):
		if len(self.pattern) > len(self.target):
			return -1

		i = start
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					return i - p
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return -1

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

if __name__ == "__main__":
	main()

### FIXED CODE ###

# coding: utf-8

def main():

	# N = 0
	# a = []
	# b = []
	# with open("C:/Users/admin/Downloads/random_05") as f:
	# 	N = int(f.readline())
	# 	a = [int(x) for x in f.readline().split()]
	# 	b = [int(x) for x in f.readline().split()]

	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	ans = kmp.full_search()
	for k in ans:
		if k == len(a):
			break
		print(str(k) + " " + str(a[0 + k] ^ b[0]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def full_search(self):
		if len(self.pattern) > len(self.target):
			return -1

		res = []
		i = 0
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					res.append(i-p)
					i -= 1
					p = self.__table[p-1]
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return res

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

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

n = int(input())
l = list(map(int, input().split()))
s = 0
for i in range(n):
    P = l[i]
    J = l[:i+1]
    if min(J) >= P:
        s += 1
print(s)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
s = 0
m = l[0]
for i in range(n):
    if m >= l[i]:
        m = l[i]
        s += 1
print(s)
### BUGGY CODE ###

S = input()
mod = 13
amari = 5
import numpy as np
dp_temp = np.zeros((mod),dtype="uint64")
dp_temp[0] = 1

def nadd(x_array,y_array,i,mod):
    for n in range(10):
        y_array += np.roll(x_array,n*(10**i)%mod)
    return y_array


for i,s in enumerate(S[::-1]):
    if s == "?":
        dp = np.zeros((mod),dtype="uint64")
        dp = nadd(dp_temp,dp,i,mod)
    else:
        dp = np.roll(dp_temp,int(s)*(10**i)%mod)
    dp = dp%(10**9+7)
    dp_temp = dp
print(dp[amari])

### FIXED CODE ###

rotate = lambda x,y: x[-y:] + x[:-y]
S = input()
mod = 13
amari = 5
dp_tmp = [0]*13
dp_tmp[0] = 1
mul = 1
for s in S[::-1]:
    dp = [0]*13
    if s == "?":
        for n in range(10):
            dp_tmp_roll = rotate(dp_tmp,n*mul%mod)
            for k in range(13):
                dp[k] += dp_tmp_roll[k]
    else:
        dp_tmp_roll = rotate(dp_tmp,int(s)*mul%mod)
        for k in range(13):
            dp[k] += dp_tmp_roll[k]
    for n in range(13):
        dp[n] = dp[n]%(10**9+7)
    dp_tmp = dp
    mul = mul*10%13
print(dp[amari])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 18:42:44 2018
ABC084D
@author: maezawa
"""

n = int(10**5)
is_prime = [True]*(n+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, n//2):
    if is_prime[i] == True:
        for j in range(2*i,n+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(n+1) if is_prime[i]]
similar = []

for i in prime_numbers:
    if (i+1) // 2 in prime_numbers:
        similar.append(i)
        
sim = [0]*(n+1)    
cnt = 0    
for i in range(n+1):
    if i in similar:
        cnt += 1
    sim[i]=cnt  

q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    print(sim[r]-sim[l-1])
        
        
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 18:42:44 2018
ABC084D
@author: maezawa
"""

n = int(10**5)
is_prime = [True]*(n+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, n//2):
    if is_prime[i] == True:
        for j in range(2*i,n+1,i):
            is_prime[j] = False

prime_numbers = set([i for i in range(n+1) if is_prime[i]])
similar = set([])

for i in prime_numbers:
    if (i+1) // 2 in prime_numbers:
        similar.add(i)
        
sim = [0]*(n+1)    
cnt = 0    
for i in range(n+1):
    if i in similar:
        cnt += 1
    sim[i]=cnt  

q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    print(sim[r]-sim[l-1])
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    s=min(k,i)+1
    ans=999999999
    for j in range(1,s):
        ans=min(ans,dp[i-j]+abs(l[i]-l[i-j]))
    dp[i]=ans
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    s=min(k,i)+1
    ans=dp[i-1]+abs(l[i]-l[i-1])
    for j in range(2,s):
        ans=min(ans,dp[i-j]+abs(l[i]-l[i-j]))
    dp[i]=ans
print(dp[n-1])
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    #while True:
    for _ in range(K):
        inc = [0] * N
        dec = [0] * N
        for i in range(N):
            s = max(0, i - A[i])
            e = min(N - 1, i + A[i])
            inc[s] += 1
            dec[e] += 1
        nexts = []
        cur = 0
        for i in range(N):
            cur += inc[i]
            nexts.append(cur)
            cur -= dec[i]
        A = nexts
    print(*A, sep=' ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, A: "List[int]"):
    #while True:
    for _ in range(K):
        inc = [0] * N
        dec = [0] * N
        for i in range(N):
            s = max(0, i - A[i])
            e = min(N - 1, i + A[i])
            inc[s] += 1
            dec[e] += 1
        nexts = []
        cur = 0
        found = False
        for i in range(N):
            cur += inc[i]
            if cur < N:
                found = True
            nexts.append(cur)
            cur -= dec[i]
        A = nexts
        if not found:
            break
    print(*A, sep=' ')
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

import heapq

N = int(input())
A = list(map(int, input().split()))
Temp = input().split()
B = []
for i in range(N):
    heapq.heappush(B, (-int(Temp[i]), i))
now = list(map(int, Temp))
complete = [False]*N
fin = [True]*N
ans = 0
while True:
    v, i = heapq.heappop(B)
    if A[i] == now[i]:
        complete[i] = True

    if not complete[i]:
        if i == 0:
            nv = v + now[-1] + now[1]
        elif i == N-1:
            nv = v + now[0] + now[-2]
        else:
            nv = v + now[i-1] + now[i+1]
        if nv <= -A[i]:
            heapq.heappush(B, (nv, i))
            now[i] = -nv
            ans += 1
    if not B:
        if complete == fin:
            break
        else:
            print(-1)
            exit()
print(ans)

### FIXED CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
B = input().split()
C = []
for i in range(N):
    heapq.heappush(C, (A[i] - int(B[i]), i))
B = list(map(int, B))
ans = 0
while True:
    v, i = heapq.heappop(C)
    if v == 0:
        break

    nv = B[i-1] + B[(i+1) % N]
    n = -v // nv
    if n <= 0:
        print(-1)
        exit()
    v += n * nv
    B[i] -= n * nv
    heapq.heappush(C, (v, i))
    ans += n
print(ans)
### BUGGY CODE ###

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

sum_p = []

for i in range(N - K + 1):
    sum_p.append(sum(p[i:i+K]))
    

ex = sum(list(range(1,max(sum_p)-K+2))) / (max(sum_p)-K+1)

print(ex + K - 1)

### FIXED CODE ###

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

sum_p = 0

for i in range(K):
    sum_p += p[i]

max_p = sum_p

for j in range(K,N):
    sum_p -= p[j - K]
    sum_p += p[j]
    max_p = max(max_p,sum_p)

ex = (max_p - K + 2)/2

print(ex + K - 1)
### BUGGY CODE ###

n,p=map(int, input().split())
ans=1
m=int(pow(p,1/n))+1
i=2
c=0
while(i<=p):
    if p % i == 0:
        p=p/i
        c=c+1
        if p % i != 0:
            #print('i**(c//n)=',i**(c//n))
            ans = ans * ( i**(c//n) )
            i=i+1
            c=0

print(ans)


### FIXED CODE ###

n,p=map(int, input().split())
ans=1
m=int(pow(p,1/n))+1
if n==1:
    print(p)
else:
    m=int(pow(p,1/n))+1
    i=2
    c=0
    while(i<=p and i<=m):
        #print('i,p=',i,p)
        if p % i == 0:
            p=p/i
            c=c+1
            if p % i != 0:
                #print('i**(c//n)=',i**(c//n))
                ans = ans * ( i**(c//n) )
                i=i+1
                c=0
        else:
            i=i+1
    print(ans)
### BUGGY CODE ###

li = list(map(int, input().split()))
new_li = []
n = 0
while True:
  li[0] = abs(li[0]-li[1])
  new_li.append(li[0])
  
  if n>=2:
    if new_li[n] == new_li[n-2]:
      print(min(new_li))
      break
  n += 1

### FIXED CODE ###

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

n = x%k

if n < abs(n-k):
  print(n)
else:
  print(abs(n-k))
### BUGGY CODE ###

import math
N = int(input())
A = list(map(int, input().split()))

B=sorted(set(A))
sa = []
su = [0]*(N+1)
gokei = 0
for i in range(len(B)):
    x = A.count(B[i])
    if x == 1:
        gokei += 0
        sa.append(0)
    elif x ==2:
        gokei += 1
        sa.append(1)
    else:
        if su[x] == 0:
            z = math.factorial(x)//(math.factorial(x-2)*math.factorial(2))
        else:
            z = su[x]
        gokei += z
        sa.append(z-z*(x-2)//x)

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    if ans[z] == 0:
        e = gokei - sa[B.index(z)]
        ans.append(e)
        print(e)
    else:
        print(ans[z])

### FIXED CODE ###

import collections

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

gokei = 0
counter = collections.Counter(A)
for i in counter.values():
    gokei += i * (i - 1) // 2

ans = [0]*(N+1)
for i in range(N):
    z = A[i]
    d = counter[z]
    if ans[z] == 0:
        e = gokei - (d * (d - 1) // 2 - (d-1) * (d - 2) // 2)
        ans.append(e)
        print(e)
    else:
        print(ans[z])
### BUGGY CODE ###

n = int(input())
b = list(map(int,input().split()))

q = []
for i in range(1,n+1):
    q.append([b[i-1],i])
ans = []
def solve(q,i):
    if i == 0:
        return True
    for j in range(i):
        if q[j][0] == j+1:
            p = q[:j] + q[j+1:]
            if solve(p,i-1):
                ans.append(j+1)
                return True


    return

solve(q,n)
if len(ans) == n:
    for i in range(n):
        print(ans[i])
else:
    print(-1)

### FIXED CODE ###

n = int(input())
b = list(map(int,input().split()))

ans = []
def solve(b,i):
    if i == 0:
        return True
    for j in range(i-1,-1,-1):
        if b[j] > j+1:
            return False
        if b[j] == j+1:
            p = b[:j] + b[j+1:]
            if solve(p,i-1):
                ans.append(j+1)
                return True

    return False

solve(b,n)
if len(ans) == n:
    for i in range(n):
        print(ans[i])
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
mod = 10**9+7
if n == 3:
  print(61)
  exit()
  
st = ['AGC','GAC','ACG','AGTC','AGGC','ATGC']
from collections import deque
st = deque(st)
l = 3
cnt = 0
e = n-3

while st:
  if cnt == l:
    st = set(st)
    l = len(st)
    cnt = 0
    e -= 1
    st = deque(st)
  j = st.popleft()
  if e == 0:
    a = l%mod
    break
  else:
    st.append('A'+j)
    st.append('G'+j)
    st.append('C'+j)
    st.append('T'+j)
    st.append(j+'A')
    st.append(j+'C')
    st.append(j+'G')
    st.append(j+'T')
  cnt += 1
  
print(pow(4,n,mod)-a)

### FIXED CODE ###

n = int(input())
mod = 10**9+7
  
dp = [[0]*4 for i in range(n)]
for i in range(4):
  dp[0][i] = 1
  dp[1][i] = 4
  dp[2][i] = 16
  
dp[2][1] -= 2
dp[2][2] -= 1
  
for i in range(3,n):
  for j in range(4):
    dp[i][j] = sum(dp[i-1])%mod
  dp[i][1] -= dp[i-2][0] #AGC
  dp[i][1] -= dp[i-2][2] #GAC
  dp[i][1] -= dp[i-3][0]*3 #AGTC,AGGC,ATGC
  dp[i][2] -= dp[i-2][0] #ACG
  dp[i][2] += dp[i-3][2] #GACG
  
print(sum(dp[n-1])%mod)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0

m = k + 1
for x in range(m):
    for y in range(m):
        for z in range(m):
            xyz = x + y + z
            if xyz == s:
                ans += 1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0

s3 = s // 3
m = max(k, s3)
for x in range(0, m + 1):
    # print(x)
    for y in range(0, m + 1):
        ad = s - x - y
        if ad <= k and ad >= 0:
            ans += 1

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

N = int(input())
A = N
S = [input() for _ in range(N)]
for i in range(N):
    for k in range(i):
        if S[k] == S[i]:
            A -= 1
            break
print(A)


### FIXED CODE ###

N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
### BUGGY CODE ###

import itertools
N=int(input())
A=[int(x) for x in input().split()]
bit= [bin(x ^ y) for x in A for y in A]
B=sorted(set(bit))[1:]
AA=[]
for a in A:
  AA.append(bin(a))
if all(a in B for a in AA):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import collections
N=int(input())
A=[int(x) for x in input().split()]
AA=sorted(A)
c=collections.Counter(A)
third=N//3
answer="No"

#文字が全部0
if all(a==0 for a in A):
  answer="Yes"

#0aa0aaという並びに出来る
#0がN/3個,aが2N/3個で数字は二種類
elif len(c)==2 and N%3==0:
  if all(a==0 for a in AA[:third]):
    answer="Yes"
     
#abc,abc...,abcという並びに出来る
#aがN/3個,bがN/3個,cがN/3個で数字は三種類
elif len(c)==3 and N%3==0:
  if A.count(AA[0])==third and \
  A.count(AA[third])==third and \
  A.count(AA[2*third])==third:
    if bin(AA[0]^AA[third])==bin(AA[2*third]) and \
    bin(AA[third]^AA[2*third])==bin(AA[0]) and \
    bin(AA[2*third]^AA[0])==bin(AA[third]):
      answer="Yes"
    
print(answer)
### BUGGY CODE ###

def dist(p1,p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

points = []
N = int(input())
for i in range(N):
    x, y = map(int, input().split())
    points.append((x,y))

cand = []
for i in (-1,0,1):
    for j in (-1,0,1):
        points.sort(key = lambda x: i*x[0] + j*x[1])
        cand.append(points[0])
outs = []
for i in cand:
    for p in points:
        outs.append(dist(i,p))
print(max(outs))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dist(p1,p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

points = []
N = int(input())
for i in range(N):
    x, y = map(int, input().split())
    points.append((x,y))

cand = []
for i in (-1,0,1):
    for j in (-1,0,1):
        best = -10 ** 9
        bestP = (0,0)
        for p in points:
            val = i * p[0] + j * p[1]
            if val > best:
                best = val
                bestP = p
        cand.append(bestP)
                
best = 0
for i in cand:
    for p in points:
       best = max(best,dist(i,p))
print(best)
### BUGGY CODE ###

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

for i in range(len(a)):
    a[i]-=i+1

import math
#import statistics
#b=statistics.median(a)
b=math.floor(sum(a)/n)


def p(b,k):
  s=0
  for i in a:
      s+=abs(i-b)
  t=0
  for i in a:
      t+=abs(i-b-1) 
  if s>t:
    if k==-1:
      print(t)
    else:
      return p(b+1,1)
  elif s==t:
    print(s)
  else:
    if k==1:
      print(s)
    else:
      return p(b-1,-1)
  
p(b,0)



### FIXED CODE ###

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

for i in range(len(a)):
    a[i]-=i+1

aa=sorted(a)
if n%2==0:
  b=(aa[int(n/2-1)]+aa[int(n/2)])/2
else:
  b=aa[int((n-1)/2)]

s=0
for i in aa:
  s+=abs(i-b)
print(int(s))
### BUGGY CODE ###

n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
#print(l)
k = [[] for i in range(n)]
for j,h in l:
  k[j-1].append(h)
k_so = [[] for i in range(n)]
for i in range(n):
  a = k[i]
  k_so[i] = sorted(a)
#print(k_so)
for j,h in l:
  first = "{:0=6}".format(j)
  second = "{:0=6}".format(k_so[j-1].index(h)+1)
  print(first+second)

### FIXED CODE ###

from bisect import bisect_left 
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
#print(l)
k = [[] for i in range(n)]
for j,h in l:
  k[j-1].append(h)
k_so = [[] for i in range(n)]
for i in range(n):
  a = k[i]
  k_so[i] = sorted(a)
#print(k_so)
for j,h in l:
  first = "{:0=6}".format(j)
  t = bisect_left(k_so[j-1], h)
  second = "{:0=6}".format(t+1)
  print(first+second)
### BUGGY CODE ###



N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]
colors = [set() for i in range(N+1)]

for i in range(N-1):
  a, b = map(int, input().split())
  E.append((a,b))
  edges[a].append(b)
  edges[b].append(a)

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [(u, -1)]
  mcolor = -1

  while stack:
    u, p = stack.pop()
  
    for v in edges[u]:
      if v != p and v not in visited:
        c = colors[u] | colors[v]
        next = 1
        while next in c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        colors[u].add(next)
        colors[v].add(next)
        visited.add(v)
        stack.append((v, u))
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

### FIXED CODE ###


N = int(input())
edges = [[] for _ in range(N+1)]


for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a, i))

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

for a in ans:
  print(a)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
LR = []
for i in range(Q):
    LR.append(list(map(int, input().split())))

num_list = []
for i in range(N-1):
    if S[i:i+2] == 'AC':
        num_list.append(1)
    else:
        num_list.append(0)

for i in range(Q):
    print(sum(num_list[LR[i][0]-1:LR[i][1]-1]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
LR = []
for i in range(Q):
    LR.append(list(map(int, input().split())))

num_list = []
cnt = 0
for i in range(N-1):
    if S[i:i+2] == 'AC':
        cnt += 1
    num_list.append(cnt)

for i in range(Q):
    if LR[i][0] == 1:
        l = 0
    else:
        l = num_list[LR[i][0]-2]
    if LR[i][1] == N:
        r = num_list[N-2]
    else:
        r = num_list[LR[i][1]-2]
    print(r-l)
### BUGGY CODE ###

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.append(Li)
    R.append(Ri)

cards = set()
for i in range(len(L)):
    cards |= set(range(L[i], R[i]+1))

ng_cards = set()
for card in cards:
    for i in range(len(L)):
        if card < L[i] or card > R[i]:
            ng_cards.add(card)
            break

print(len(list(cards - ng_cards)))




### FIXED CODE ###

def i_input(): return int(input())
def s_input(): return map(int,input().split())
def l_input(): return list(map(int, input().split()))

N, M = s_input()
L, R = [], []

for i in range(M):
    Li, Ri = s_input()
    L.extend([Li])
    R.extend([Ri])

L_max = max(L)
R_min = min(R)

num = R_min - L_max

if num >= 0:
    print(num + 1)
else:
    print(0)