Harryxun/stf_run huggingface dataset:
n, m = map(int, input().split())
switch = [0] * n
for m_ in range(m):
    s = list(map(int, input().split()))
    for s_ in s[1:]:
        switch[m_] |= 1 << s_ - 1
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & switch[i]).count('1') % 2 != p[i]:
            break
    else:
        ans +=1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
switch = [0] * m
for i in range(m):
    s = list(map(int, input().split()))
    for j in s[1:]:
        switch[i] |= 1 << (j - 1)
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & switch[i]).count('1') % 2 != p[i]:
            break
    else:
        ans +=1
print(ans)
S = input()
Q = int(input())
reverse = False
front = ""
end = ""

for i in range(Q):
    print(end[::-1]+S[::-1]+front)
    inp = input()
    if inp[0] == "1":
        reverse = ~reverse
    else:
        _, F, C = inp.split()
        if (F == "1" and reverse == False) or (F == "2" and reverse == True):
            front = front+C
        else:
            end = end+C

if reverse:
    print(end[::-1]+S[::-1]+front)
else:
    print(front[::-1]+S+end)


### FIXED CODE ###

S = input()
Q = int(input())
reverse = False
front = ""
end = S

for _ in range(Q):
    I = input().split()
    if I[0] == "1":
        reverse = not reverse
    else:
        if (I[1] == "1") ^ reverse:
            front =front + I[2]
        else:
            end = end + I[2]


if reverse:
    print("".join(list(reversed(end)))+front)
else:
    print("".join(list(reversed(front)))+end)
N,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
dp = [False]*(N+1)
tele = 0
for i in range(10**5):
    if i == 0:
        tele = A[1]
        dp[1] = True
    else:
        tele = A[tele]
        if dp[tele] == False:
            dp[tele] = True
        else:
            finish = i+1
            tele1 = tele
            break
tele = 0
for i in range(10**5):
    if i == 0:
        tele = 1
        if tele == tele1:
            start = i
            break
    else:
        tele = A[tele]
        if tele == tele1:
            start = i+1
            break
ans = A[1]
if K<start:
    for _ in range(K-1):
        ans = A[ans]
else:
    ans = tele1
    for _ in range((K-start)%(finish-start)):
        ans = A[ans]
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
dp = [False]*(N+1)
tele = 0
for i in range(10**6):
    if i==0:
        tele = 1
        dp[tele]=True
    else:
        tele = A[tele]
        if dp[tele]==True:
            finish = i
            tele1 = tele
            break
        else:
            dp[tele]=True
#print(finish)
#print(tele)
tele = 0
for i in range(10**6):
    if i == 0:
        tele = 1
        if tele == tele1:
            start = i
            break
    else:
        tele = A[tele]
        if tele == tele1:
            start = i
            break
#print(start)
loop = finish-start
if K<=start:
    ans = 1
    for i in range(K):
        ans = A[ans]
    print(ans)
else:
    ans = 1
    for i in range(start+(K-start)%loop):
        ans = A[ans]
    print(ans)
def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N)
    num = len(primes)

    # N=1
    lst = [0] * N

    # N>=2

    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans)



#    for i in range(1,N+1):
#        k = k * i


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai




if __name__ == "__main__":
        main()


### FIXED CODE ###

def main():
    N = input()
    N = int(N)

    k = 1
    s = []
    #lst = list(range(1,N+1))
    primes = prime(N+1)
    num = len(primes)

    # N=1
    lst = [0] * N
    if N ==1:
        print(1)
        exit()

    # N>=2
    for i in range(2,N+1):
        b =[]
        b = bunkai(i)
        for i in b:
            lst[primes.index(i)] += 1

    ans = 1
    for i in lst:
        if i is not 0:
            ans = ans * (i+1)
    print(ans%1000000007)


def prime(n):
    primes = []
    for i in range(2,n):
        flag = True
        for j in range(2,i):
            if i%j == 0:
                flag = False
        if flag:
            primes.append(i)
    return primes

def bunkai(i):
    bunkai =[]
    s =0
    while s ==0:
        for j in range(2,i+1):
            if i % j ==0:
                bunkai.append(j)
                i = int(i/j)
                if i ==1:
                   s=1
                break
    return bunkai

if __name__ == "__main__":
        main()
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
  PY[i].append(i)

PY = sorted(PY)

ans = [0]*M
#print(PY)

for i in range(M):
  X = str(PY[i][0])
  if i >= 1:
    #print(PY)
    if PY[i][0] == PY[i-1][0]:
      Y = int(Y) + 1
    else:
      Y = 1
  else:
    Y = 1
  while len(str(X)) <= 5:
    X = "0" + X
  while len(str(Y)) <= 5:
    Y = "0" + str(Y)
  PY[i][1] = X + Y
#print(PY)
PY = sorted(PY, key = lambda x:x[2])

for i in range(M):
  print(PY[i][1])

### FIXED CODE ###

N, M = map(int, input().split())
PY = [list(map(int, input().split())) for i in range(M)]
for i in range(M):
  PY[i].append(i)

PY1 = sorted(PY)
#print(PY)

for i in range(M):
  X = str(PY1[i][0])#県の番号
  if i >= 1:#市の番号
    #print(PY)
    if PY1[i][0] == PY1[i-1][0]:
      Y = int(Y) + 1
    else:
      Y = 1
  else:
    Y = 1
  while len(str(X)) <= 5:#6桁にするための処理
    X = "0" + X
  while len(str(Y)) <= 5:
    Y = "0" + str(Y)
  PY1[i][1] = str(X) + str(Y) #文字列の結合
#print(PY)
PY2 = sorted(PY1, key = lambda x:x[2])

for i in range(M):
  print(PY2[i][1])
a, b, c, d = input().split()

operators = ["+", "-"]

for op1 in operators:
    for op2 in operators:
        for op3 in operators:
            equation = a+op1+b+op2+c+op3+d
            if eval(equation) == 7:
                print(equation+"=7")
                exit()

### FIXED CODE ###

a, b, c, d = list(input())

operators = ["+", "-"]

for op1 in operators:
    for op2 in operators:
        for op3 in operators:
            equation = a+op1+b+op2+c+op3+d
            if eval(equation) == 7:
                print(equation+"=7")
                exit()
a, b, c = map(int,input().split())
d = 0
for i in(range(a,b):
 if i % c == 0:
  d+=1
 else:
  pass
print(d)
 

### FIXED CODE ###

a, b, c = map(int,input().split())
d = 0
for i in(range(a,b+1)):
 if c % i == 0:
  d+=1
print(d)
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

try:
    listA = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

a=int(listA[0])
b=int(listA[1])

print(lcm(a, b))

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b

def lcm(x, y):
    return (x * y) // gcd(x, y)

try:
    listA = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

a=int(listA[0])
b=int(listA[1])

print(lcm(a, b))
10
ZABCDBABCQ
---
2
===
19
THREEONEFOURONEFIVE
---
0
===
33
ABCCABCBABCCABACBCBBABCBCBCBCABCB
---
5
===


### FIXED CODE ###

N= int(input())
S = input()
print(S.count('ABC'))
number = int(input())
if number * 2 = 0:
	odd_num = number // 2
	percent = odd_num / number
else:
	odd_num = number // 2 + 1
    percent = odd_num / number
  
print(percent)


### FIXED CODE ###

number = int(input())
if number % 2 == 0:
	odd_num = number // 2
	percent = odd_num / number
else:
	odd_num = number // 2 + 1
	percent = odd_num / number

print(percent)
import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1-1])].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
q=[]
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.append(key)
sub=[]
heapq.heapify(q)
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        for n in _to[x]:
            if conduct>=_from[n]:
                conduct.add(n)
                heapq.heappush(sub,n)
        if not q:
            q=sub
            sub=[]
            heapq.heapify(sub)
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)

### FIXED CODE ###

N=int(input())
A=[[] for i in range(0,N)]
nodes=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        nodes.append((i,j))

order={i:[0 for j in range(0,N)] for i in range(0,N)}
for i in range(0,N):
    A[i]=list(map(int,input().split()))
    for j in range(0,N-1):
        order[i][A[i][j]-1]=j
        #i番目の人がj番目の人と戦うのが何番目か


q=set([])
for battle in nodes:
    i,j=battle
    if order[i][j]==0 and order[j][i]==0:
        q.add(battle)

flag=[0 for i in range(0,N)]

day=0
sub=set([])
while q:
    while q:
        i,j=q.pop()
        flag[i]+=1
        flag[j]+=1
        if flag[i]!=N-1:
            s=A[i][order[i][j]+1]-1
            if flag[s]>=order[s][i]:
                sub.add((i,s))
        if flag[j]!=N-1:
            t=A[j][order[j][i]+1]-1
            if flag[t]>=order[t][j]:
                sub.add((j,t))

        if not q:
            day+=1
            q=sub
            sub=set([])
            break

able=True
for i in range(0,N):
    if flag[i]!=N-1:
        able=False

if able:
    print(day)
else:
    print(-1)
input()
lst = map(int, input().split())
print('Yes' if max(lst) < sum(lst) - max(lst) else 'No')

### FIXED CODE ###

input()
lst = list(map(int, input().split()))
print('Yes' if max(lst) < sum(lst) - max(lst) else 'No')
import math 

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

for i in range(1,n):
    monsters[i] = math.gcd(monsters[i],monsters[i-1])
print(monsters[n-1])

### FIXED CODE ###

import fractions 

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

for i in range(1,n):
    monsters[i] = fractions.gcd(monsters[i],monsters[i-1])
print(monsters[n-1])
N,K=map(int, input().split())
p = list(map(int, input().split()))

#p = [(n+1)/2 for n in p]
import numpy as np
s = np.cumsum(p)

e=s[K-1]
max_e=(K+e)/2
if N==1:
  print(max_e)
else:
for i in range(0,N-K-1):
    e=s[i+K]-s[i]
    #print(e)
    e=(K+e)/2
    #print(e)
    max_e = max(max_e, e)

  print(max_e)

### FIXED CODE ###

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

p = [(n+1)/2 for n in p]
import numpy as np
s = np.cumsum(p)

e=s[K-1]
max_e=e
for i in range(1,N-K):
  e=s[i+K]-s[i]
  max_e = max(max_e, e)
    
print(max_e)
a,b,c=map(int,input().split())
k=int(input())
print((max(a,b,c))*2*k+sum(a,b,c))

### FIXED CODE ###

a,b,c=map(int,input().split())
k=int(input())
print((max([a,b,c]))*(2**k-1)+sum([a,b,c]))
import math
while 1:
    e = int(input())
    if  e == 0 :break
    m = e
    for z in range(int(math.sqrt(e)) + 1):
        for y in range(int(math.sqrt(e))+ 1):
            x = e - y**2-z**3
            if  x < 0:continue
            if m > x+y+z: m = x+y+z
    print(m)



### FIXED CODE ###

import math
while 1:
    e = int(input().strip())
    if e ==0:break
    m=e
    z =0
    while z**3 <= e:
        y = int(math.sqrt(e-z**3))
        x = e - y**2- z**3 
        if x < 0:break
        if m > x+y+z: m = x+y+z    
        z+=1
    print(m)
a =list(map(int, input().split()))
print(a[0]*a[1], 2(a[0]+a[1]))


### FIXED CODE ###

a,b = [int(x) for x in input().split()]
print(a*b,2*(a+b))
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

def main():
	n = int(input())
	for i in range(n-1):
		a, b, w = map(int , input().split())
		adj[a].append((b, w))
		adj[b].append((a, w))

	q, k = map(int , input().split())
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		print(dis[x]+dis[y])

if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
import os
from collections import defaultdict
adj = defaultdict(list)
vis =[0 for i in range(1000000)]
dis =[0 for i in range(1000000)]
def dfs(u, p):
	for v, w in adj[u]:
		if v==p:
			continue
		dis[v]=dis[u]+w
		dfs(v, u)

def main():
	n = int(input())
	for i in range(n-1):
		a, b, w = map(int , input().split())
		adj[a].append((b, w))
		adj[b].append((a, w))

	q, k = map(int , input().split())
	sys.setrecursionlimit(1000000)
	dfs(k , 0)
	for i in range(q):
		x, y  =map(int , input().split())
		print(dis[x]+dis[y])
#	rec_limit= sys.getrecursionlimit()
#	print(rec_limit)


if __name__ == "__main__":
	main()
from math import sqrt
from itertools import permutations
N=int(input())
xy=[list(map(int,input().split())) for _ in range(N)]
ans=0
cnt=0
for i in permutations(range(3)):
  d=0
  for j in range(N-1):
    dx=xy[i[j+1]][0]-xy[i[j]][0]
    dy=xy[i[j+1]][1]-xy[i[j]][1]
    d+=sqrt(dx**2+dy**2)
  ans+=d
  cnt+=1
print(ans/cnt)

### FIXED CODE ###

import itertools
from math import *
n=int(input())
ps=[list(map(int,input().split())) for _ in range(n)]
perms = list(itertools.permutations(ps, n))
dists = []
for i in range(len(perms)):
  dist = 0
  cur = perms[i][0]
  for j in range(1,len(perms[i])):
    d = sqrt((perms[i][j][0]-cur[0]) ** 2 + (perms[i][j][1]-cur[1])**2)
    cur = perms[i][j]
    dist += d

  dists.append(dist)
print(sum(dists)/len(perms))
n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
dic = {}
def dfs(i):

    global dic
    if dic.get(i):
        return dic[i]

    if i == n:
        return 1

    k = 0
    if i+1 not in am and i+1 <= n:
        k += dfs(i+1)
    if i+2 not in am and i+2 <= n:
        k += dfs(i+2)

    k %= 1000000007
    dic[i] = k
    return k

print(dfs(0))

### FIXED CODE ###

n, m = map(int, input().split())
am = [int(input()) for _ in range(m)]
hole = [False]*(n+1)

for i in am:
    hole[i] = True

dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    for j in range(i+1, min(n, i+2)+1):
        if not hole[j]:
            dp[j] += dp[i]
            dp[j] %=1000000007
print(dp[n])
l = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
s = input()
flg = Flase
for i in l:
  if flg == True:
    print(i)
    exit()
  if s == i:
    flg = True


### FIXED CODE ###

l = ['Sunny', 'Cloudy', 'Rainy', 'Sunny']
s = input()
flg = False
for i in l:
  if flg == True:
    print(i)
    exit()
  if s == i:
    flg = True
a,b,c = input().split()
print(a,b,c)

### FIXED CODE ###

a,b,c = input().split(',')
print(a,b,c)
x,t = map(int,input())

print(x-t) if x > t else print(0)

### FIXED CODE ###

x, t = map(int, (input().split()))
print(x-t if x-t > 0 else 0)
s,w = map(inr, input().split())

if w >= s:
  print("unsafe")
else:
  print("safe")

### FIXED CODE ###

s,w = map(int, input().split())
 
if w >= s:
  print("unsafe")
else:
  print("safe")
strings = raw_input.split(',')
new_strings = ""
for string in strings:
  if string.islower():
    new_strings.append(string.upper()+',')
  else:
    new_strings.append(string.lower()+',')
print  new_strings

### FIXED CODE ###

print raw_input().swapcase()
n,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
ans=1
curr=0
ind=0
while(curr<=x):
    curr+=a[ind]
    ind+=1
    if(curr>x):
        break
    ans+=1
print(ans)


### FIXED CODE ###

n,x=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
ans=1
curr=0
ind=0
while(curr<=x):
    if(ind>=n):
        break
    curr+=a[ind]
    ind+=1
    if(curr>x):
        break
    ans+=1
print(ans)
n,m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
one = [0 for i in range(n)]
ans = "IMPOSSIBLE"
for i in a:
  if i[0] == 1:
    if one[i[1]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[1]] = 1
  elif i[1] == n:
    if one[i[0]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[0]] = 1
print(ans)

### FIXED CODE ###

n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
one=[0 for i in range(n)]
ans = "IMPOSSIBLE"
for i in a:
  if i[0] == 1:
    if one[i[1]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[1]] = 1
  elif i[1] == n:
    if one[i[0]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[0]] = 1
print(ans)
N=int(input())
A=[]
for j in range(N):
    a=[int(i) for i in input().split()]
    A.append(a)
for i in range(0,101):
    for j in range(0,101):
        HH=[]
        P=[]
        for k in range(N):
            if A[k][2]==0:
                if 1>abs(A[k][0]-i)+abs(A[k][1]-j):
                    break
                else:
                    Q=abs(A[k][0]-i)+abs(A[k][1]-j)
                    P.append(Q)
                    if k==N-1:
                        if len(P)==0:
                            print("{} {} {}".format(i,j,HH[0]))
                            break
                        elif H<=max(P):
                            print("{} {} {}".format(i,j,HH[0]))
                        else:
                            break
                    else:
                        continue
            else:
                H=A[k][2]+abs(A[k][0]-i)+abs(A[k][1]-j)
                if len(HH)==0:
                    HH.append(H)
                    continue
                if H in HH:
                    HH.append(H)
                    if k==N-1:
                        if len(P)==0:
                            print("{} {} {}".format(i,j,H))
                        elif H<=max(P):
                            print("{} {} {}".format(i,j,h))
                        else:
                            break
                    else:
                        continue
                else:
                    break

### FIXED CODE ###

N=int(input())
xyh=[]
for i in range(N):
    a=[int(i) for i in input().split()]
    xyh.append(a)
xyh.sort(key=lambda x:x[2],reverse=True)
flag2=True
for i in range(0,101):
    for j in range(0,101):
        flag=True
        H=xyh[0][2]+abs(xyh[0][0]-i)+abs(xyh[0][1]-j)
        for k in range(1,N):
            if xyh[k][2]!=max(0,H-abs(xyh[k][0]-i)-abs(xyh[k][1]-j)):
                flag=False
                break
        if flag==True:
            print("{} {} {}".format(i,j,H))
            flag2=False
            break
    if flag2==False:
        break
import math

N = 10
ARR = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

N = 10
ARR = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]

# N = 3
# ARR = [1, 2, 3]

# N = 5
# ARR = [3, 6, 8, 9, 10]

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


def calculate(n, arr):
    mathNum = math.ceil(math.log(max(arr), 2)) + 1
    result = 0
    for i in range(mathNum):

        oneSum = 0
        zeroSum = 0
        for j in range(n):
            if ((arr[j] >> i) & 1) == 0:
                zeroSum += 1
            else:
                oneSum += 1

        result += 2 ** i * (zeroSum * oneSum)

    print(result % (10**9 + 7))


calculate(N, ARR)


### FIXED CODE ###

import math
import numpy as np

N = 10
ARR = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]

N = 10
ARR = [3, 14, 159, 2653, 58979, 323846, 2643383, 27950288, 419716939, 9375105820]


# N = 3
# ARR = [1, 2, 3]

# N = 5
# ARR = [3, 6, 8, 9, 10]

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


def calculate(n, arr):
    if max(arr) == 0:
        mathNum = 1
    else:
        mathNum = math.ceil(math.log(max(arr), 2))

    oneArray =  [0] * mathNum
    zeroArray = [0] * mathNum

    result = 0
    arr = np.array(arr)
    for i in range(mathNum):
        s = (arr >> i) & 1

        oneCount = np.count_nonzero(s)
        zeroCount = n - oneCount
        oneArray[i] = oneCount
        zeroArray[i] = zeroCount

    for i in range(mathNum):
        result += (2 ** i) * (oneArray[i] * zeroArray[i])

    print(result % (10 ** 9 + 7))


calculate(N, ARR)
import numpy as np
n, m, q = input().split()
n, m, q = int(n), int(m), int(q)
s = np.zeros((501, 501))

for _ in range(m):
    l, r = input().split()
    l, r = int(l), int(r)
    s[l, r] += 1
    
"""
     1 2 3
    --------
1 | 1 2 3
2 | 1 0 1
"""
    
for i in range(1, n+1):
    for j in range(1, n+1):
        s[i, j] += s[i, j-1]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 1 1 2
"""
        
for j in range(1, n+1):
    for i in range(1, n+1):
        s[i, j] += s[i-1, j]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 2 4 8
"""

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

### FIXED CODE ###

import numpy as np
n, m, q = input().split()
n, m, q = int(n), int(m), int(q)
s = np.zeros((501, 501))
 
for _ in range(m):
    l, r = input().split()
    l, r = int(l), int(r)
    s[l, r] += 1
    
"""
     1 2 3
    --------
1 | 1 2 3
2 | 1 0 1
"""
    
for i in range(1, n+1):
    for j in range(1, n+1):
        s[i, j] += s[i, j-1]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 1 1 2
"""
        
for j in range(1, n+1):
    for i in range(1, n+1):
        s[i, j] += s[i-1, j]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 2 4 8
"""
 
for _ in range(q):
    l, r = input().split()
    l, r = int(l), int(r)
    print(int(s[r, r] - s[r, l-1] - s[l-1, r] + s[l-1, l-1]))
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append((b, i))
    E[b].append((a, i))

K = max(len(e) for e in E)
print(K)

Ans = [-1] * (N-1)
def dfs(v, pc=-1, p=-1):
    c = 1
    for u, idx in E[v]:
        if (u == p):
            continue
        if (c == pc): 
            c += 1
        Ans[idx] = c
        c += 1
        dfs(u, c, v)
        
dfs(1)
print("\n".join(map(str, Ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

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

K = max(len(e) for e in E)
print(K)

Ans = [-1] * (N-1)
def dfs(v, pc=-1, p=-1):
    c = 1
    for u, idx in E[v]:
        if (u == p):
            continue
        if (c == pc): 
            c += 1
        Ans[idx] = c
        dfs(u, c, v)
        c += 1

dfs(1)
print("\n".join(map(str, Ans)))