import sys input = sys.stdin.readline N,Q=map(int,input().split()) EDGE=[list(map(int,input().split())) for i in range(Q)] for i in range(Q): EDGE[i][0]-=1 EDGE[i][1]-=1 def calc(qind): E=[[] for i in range(N)] E_INV=[[] for i in range(N)] for i in range(qind): x,y=EDGE[i] E[x].append(y) E_INV[y].append(x) # DFSして帰り際にTOPに点を放り込んでいる。 # NOWで現在地点、USEINDで、どこの辺まで既に見たか、を調べている。 def Top_sort(E): Parent=[-1]*N USEIND=[0]*N TOP=[] for ROOT in range(N): if Parent[ROOT]!=-1: continue Parent[ROOT]=ROOT NOW=ROOT while NOW!=ROOT or USEIND[ROOT]!=len(E[ROOT]): if USEIND[NOW]==len(E[NOW]): TOP.append(NOW) NOW=Parent[NOW] elif E[NOW][USEIND[NOW]]==Parent[NOW]: USEIND[NOW]+=1 else: NEXT=E[NOW][USEIND[NOW]] USEIND[NOW]+=1 if Parent[NEXT]==-1: Parent[NEXT]=NOW NOW=NEXT TOP.append(ROOT) return TOP[::-1] USE=[0]*N SCC=[] # SCCを調べるための逆順DFS。 # やっていることはhttps://manabitimes.jp/math/1250 などと同じ。 def dfs2(x): Q=[x] USE[x]=1 ANS=[] while Q: x=Q.pop() ANS.append(x) for to in E_INV[x]: if USE[to]==0: USE[to]=1 Q.append(to) return ANS TOP_SORT=Top_sort(E) for x in TOP_SORT: if USE[x]==0: SCC.append(dfs2(x)) for i in range(len(SCC)): if len(SCC[i])>1: return True return False if calc(Q)==False: print(-1) else: OK=Q NG=1 while OK>NG+1: mid=(OK+NG)//2 if calc(mid)==True: OK=mid else: NG=mid print(OK)