import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random
#sys.setrecursionlimit(10**9)
#n = int(input())
#alist = list(map(int,input().split()))
#hen = collections.defaultdict(list)
#s = input()
#n,m = map(int,input().split())
#for i in range(n):
#    alist.append(list(map(int,input().split())))
#    u,v = map(int,input().split())
#    hen[u].append(v)
#    hen[v].append(u)
#dp = [[0]*n for i in range(m)]