# ライブラリインポート------------------------------------------ import math import collections #import statistics from copy import deepcopy from collections import defaultdict,deque from sys import exit,setrecursionlimit from heapq import heapify,heappush,heappop from bisect import bisect_left,bisect_right,insort from itertools import product,permutations,combinations,accumulate,combinations_with_replacement from decimal import Decimal #from numpy import array,matrix,dot,T from functools import lru_cache from typing import Generic, Iterable, Iterator, TypeVar, Union, List from string import ascii_uppercase, ascii_lowercase # お決まり------------------------------------------------ INF=10**18 # まれに足りない場合もある MOD=10**9+7 mod=998244353 def YesNo(b): print("Yes") if b else print("No") def YESNO(b): print("YES") if b else print("NO") dxy4=[(1,0),(-1,0),(0,1),(0,-1)] dxy8=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)] ALPHA=ascii_uppercase alpha=ascii_lowercase setrecursionlimit(2*10**5) def PrintHW(array,hight,width): for i in range(hight): print(*array[i][:width]) def sortx(array,num): return sorted(array, key=lambda x:x[num]) def sortxr(array,num): return sorted(array, key=lambda x:x[num], reverse=True) def LL(h,w,e=0): return [[e for i in range(w)] for j in range(h)] def LLL(a,b,c,e=0): return [LL(b,c,e) for _ in range(a)] def LLLL(a,b,c,d,e=0): return [LLL(b,c,d,e) for _ in range(a)] def DD(): return defaultdict(int) # 初期値指定ならdefaultdict(lambda: 1)などとする def LB(n): return [[] for _ in range(n)] def Dc(x): return Decimal(str(x)) #@lru_cache(maxsize=2*10**5) # 入力---------------------------------------------------- def II(): return int(input()) def MI(): return map(int, input().split()) def TI(): return tuple(map(int, input().split())) def LI(): return list(MI()) def SLI(): return sorted(LI()) def MS(): return map(str, input().split()) def LS(): return list(MS()) def LLI(rows): return [LI() for _ in range(rows)] def LLS(rows): return [list(input()) for _ in range(rows)] def Graph0(vertex,edge,LLI): ret=[[] for _ in range(vertex)] for [u,v] in LLI: u-=1; v-=1; # 消す場合もあり ret[u].append(v); ret[v].append(u); return ret def Banhei(hight,width,LLS,wall='#'): # 01マップなら0 ret=[[wall]*(width+2)] for i in range(hight): ret.append([wall]+LLS[i]+[wall]) ret.append([wall]*(width+2)) return ret def MLI(n): # [A,B] = MLI(N)のように使う arr=LLI(n); l=len(arr[0]) ret=[[] for _ in range(l)] for i in range(n): for j in range(l): ret[j].append(arr[i][j]) return ret def ALLI(): # 何個与えられるかわからないとき res=[] while True: try: res.append(LI()) except: break return res # 出力カンペ-------------------------------------------- """ print(''.join(['a', 'b', 'c'])) # abc print("{:b}".format(b)) # 1100101010 2進数表記 print("{:o}".format(b)) # 1452 8進数表記 print("{:x}".format(b)) # 32a 16進数小文字表記 print("{:X}".format(b)) # 32A 16進数大文字表記 print("python".ljust(15,'-')) # 左詰め python--------- print("python".center(15,'-'))# 中寄せ -----python---- print("python".rjust(15,'-')) # 右詰め ---------python print(str(29).rjust(10,'0')) # 10桁ゼロ埋め 0000000029 print("{:.8f}".format(a/b)) # 小数点以下の桁数指定表示 N='aiueokakikukeko' N=N.translate(str.maketrans({'a':'A'})) #N = AiueokAkikukeko """ # 頻出ツール------------------------------------------ def acc(A): # 配列Aの累積和、最初に0を追加する。 return [0] + list(accumulate(A)) def acc2d(A,H,W): # サイズH*Wの2次元配列Aの2次元累積和。先頭に0を挿入。 B=LL(H+1,W+1) for x in range(H): for y in range(W): B[x+1][y+1]=A[x][y] for x in range(H+1): for y in range(1,W+1): B[x][y] += B[x][y-1] for x in range(1,H+1): for y in range(W+1): B[x][y] += B[x-1][y] return B def fac(n, m=0): # nの階乗 | m:mod(デフォなし) if(n<=0): return 0 P = 1 for i in range(1,n+1): P *= i if(m>0): P %= m return P def nCmMOD(A,B,Mod): # a conb b を Mod で割った余り 1絡みの挙動に注意する。 # 大量にほしいときは階乗逆元を使うやつを持ってくる。 num,den=1,1 for i in range(B): num*=(A-i) den*=(i+1) num%=Mod den%=Mod return (num*pow(den,Mod-2,Mod))%Mod def comb_table(N): # nCkのテーブルを作る, nCk = C[n][k] C = [[0 for i in range(N+1)] for j in range(N+1)] C[0][0] = 1 for n in range(1,N+1): for k in range(n+1): C[n][k] = C[n-1][k-1] + C[n-1][k] return C def nHk(A,B,Mod): # 重複組合せ:1~nの中から重複を許してk個のものを選ぶ組合せ return nCmMOD(A-1+B,A-1,Mod) def factorization(n): # 素因数分解、1に注意 arr = []; temp = n for i in range(2, int(-(-n**0.5//1))+1): if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr.append([i, cnt]) if temp!=1: arr.append([temp, 1]) if arr==[]: arr.append([n, 1]) return arr def get_primes(n: int) -> list: # n以下の素数表 sieve=[1]*n for i in range(3,int(n**0.5)+1,2): if sieve[i]: sieve[i*i::2*i] = [0] * ((n-i*i-1)//(2*i)+1) return [2] + [i for i in range(3,n,2) if sieve[i]] #@lru_cache(maxsize=2*10**5) def division(a, b, m): # a÷bをmod mで求める 大量に使うときはメモ化 return (a * pow(b, m - 2, m)) % m memod=defaultdict(lambda:-1) def gcd(a,b): # 最大公約数 while b!=0: a,b = b,a%b return a def lcm(a,b): # 最小公倍数 return(a*b // gcd(a,b)) def make_divisors(n): # nの約数列挙 divisors = [] for i in range(1, int(n**0.5)+1): if n % i == 0: divisors.append(i) if i != n // i: divisors.append(n//i) #divisors.sort() return(divisors) def ran(A): # ランレングス圧縮 L = list(A); T = [] for i in range(len(L)): if i==0: T.append([L[0],1]) else: if L[i]==L[i-1]: T[-1][1]+=1 else: T.append([L[i],1]) #return T ans1,ans2=[],[] for i in range(len(T)): ans1.append(T[i][0]) #種目 ans2.append(T[i][1]) #個数 return ans1,ans2 def dot(P,Q,a,b,c): # P(a,b), Q(b,c) の行列積, abcに1が入るときは注意 ret = LL(a,c) for i in range(a): for j in range(c): for k in range(b): ret[i][j] += P[i][k] * Q[k][j] return ret def Trans(arr,h,w): # 配列の転置 ret=LL(w,h) for i in range(h): for j in range(w): ret[j][i] = arr[i][j] return ret # Union-Find--------------------------------------- #Root=list(range(N)) #Size=[1]*N def find_root(root,x): y = root[x] if x == y: return x z = find_root(root,y) root[x] = z return z def merge(root,size,x,y): x = find_root(root,x) y = find_root(root,y) if x == y: return sx,sy = size[x],size[y] if sx < sy: sx,sy = sy,sx x,y = y,x root[y] = x size[x] += sy def getValue(root,size,x): return size[find_root(root,x)] def same(root,x,y): return (find_root(root,x)==find_root(root,y)) # itertools """ array=[1,2,3] PMT = permutations(array) #順列 #123,132,213,231,312,321 PMT2 = permutations(array,2) #12,13,21,23,31,32 CMB1 = combinations(array,2) #組合せ #12,13,23 CMB2 = combinations_with_replacement(array,2) #重複組合せ #11,12,13,22,23,33 def all_comb(array): #全組合せ(個数1~N) ret=[] for i in range(len(array)+1): ret+=list(combinations(array,i)) return ret #-,1,2,3,12,13,23,123 array2=[0,1] PRD1 = product(array2,repeat=3) #直積 #000,001,010,011,100,101,110,111 """ """ #A N=II() print(5*(3+math.sqrt(5))*N**3/12) """ """ #B N=II() A=LI() """ """ def sft(x): return x//2 + (2**15 * (x%2)) for S in range(3): print(S) for i in range(4): print(S, sft(S), "{:b}".format(sft(S))) S=sft(S) """ """ 2**16まで、どのような変化をたどるのかを見る """ #C N,M=MI() G=LB(N) E=[] for i in range(M): u,v=MI() u-=1 v-=1 u,v=min(u,v),max(u,v) G.append((u,i)) G.append((v,i)) E.append((u,v)) # 多分逆にやるUFのやつ # 辺xがi番目の操作によって取り除かれているのかのiを探す。 Root=list(range(N)) Size=[1]*N SCORE=[0]*N for x in range(M)[::-1]: (u,v)=E[x] if same(Root,u,v): U,V=find_root(Root,u), find_root(Root,v) #print('a') new = SCORE[U] + 1 SCORE[U] = new SCORE[V] = new else: #print('b') U,V=find_root(Root,u), find_root(Root,v) merge(Root, Size, u, v) new = max(SCORE[U], SCORE[V]) + 1 SCORE[U] = new SCORE[V] = new #print(u,v,SCORE) print(max(SCORE))