Problem:


Score : 600 points

Problem Statement

Given is a directed graph G with N vertices and M edges.

The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.

It is guaranteed that the graph contains no self-loops or multiple edges.

Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.

Here the null graph is not considered as a subgraph.

Notes

For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:

V' is a (non-empty) subset of V.

E' is the set of all the edges in E that have both endpoints in V'.

Constraints

1 \leq N \leq 1000

0 \leq M \leq 2000

1 \leq A_i,B_i \leq N

A_i \neq B_i

All pairs (A_i, B_i) are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

If there is no induced subgraph of G that satisfies the condition, print -1.
Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:

K
v_1
v_2
:
v_K

This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.)
If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

Sample Input 1

4 5
1 2
2 3
2 4
4 1
4 3

Sample Output 1

3
1
2
4

The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.

Sample Input 2

4 5
1 2
2 3
2 4
1 4
4 3

Sample Output 2

-1

There is no induced subgraph of G that satisfies the condition.

Sample Input 3

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2

Sample Output 3

4
2
3
4
5



Sample input:
4 5
1 2
2 3
2 4
4 1
4 3


Sample output:
3
1
2
4

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m = map(int,input().split())

edge = [[] for _ in [0]*n]
back = [[] for _ in [0]*n]

for _ in [0]*m:
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    back[b-1].append(a-1)


res = [None]*(n+1)

for end in range(n):
    for start in edge[end]:
        cost = [-1]*n
        cost[start] = 0
        new = [start]
        tank = []
        judge = True

        while len(new) > 0 and judge:
            tank = []
            for fr in new:
                for go in edge[fr]:
                    if cost[go] < 0:
                        cost[go] = cost[fr] + 1
                        tank.append(go)
                        if go == end:
                            judge = False
            new = tank

        
        if cost[end] >= 0 and cost[end] < len(res):
            p = end
            res = [p+1]
            while p != start:
                for e in back[p]:
                    if cost[p] == cost[e]+1:
                        p = e
                        res.append(p+1)
                        break
if res[0] == None:
    print(-1)
else:                      
    print(len(res))
    for e in res:
        print(e)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline        

def main():

    def loopfind():
        for i in range(N):
            if USE[i]==1:
                break
        else:
            return []
        
        Q=deque()
        Q.append(i)
        USESET={i}
        ANS=[i]

        while True:
            for to in EOUTLIST[ANS[-1]]:
                if USE[to]==1:
                    nextv=to
                    break

            if nextv in USESET:
                break
            else:
                ANS.append(nextv)
                USESET.add(nextv)

        x=ANS.index(nextv)
        return ANS[x:]

    def shortcut(ANS):
        #print(ANS)

        ANSSET=set(ANS)
        LEN=len(ANS)
        flag=0

        for i in range(LEN):
            for to in EOUTLIST[ANS[i]]:
                if to in ANSSET and ANS[(i+1)%LEN]!=to:
                    flag=1
                    x=ANS.index(to)

                    #print(ANS,i,x)

                    break
            if flag:
                break
        #print(flag)

        if flag:
            if x<i:
                return shortcut(ANS[x:i+1])
            else:
                return shortcut(ANS[x:]+ANS[:i+1])

        else:
            return ANS
    
    N,M=map(int,input().split())

    EIN=[0]*N
    EOUT=[0]*N

    EINLIST=[[] for i in range(N)]
    EOUTLIST=[[] for i in range(N)]

    for i in range(M):
        x,y=map(int,input().split())
        x-=1
        y-=1

        EOUT[x]+=1
        EIN[y]+=1

        EOUTLIST[x].append(y)
        EINLIST[y].append(x)

    Q=deque()
    USE=[1]*N

    for i in range(N):
        if EIN[i]==0 or EOUT[i]==0:
            Q.append(i)
            USE[i]=0

    while Q:
        x=Q.pop()

        for to in EOUTLIST[x]:
            if USE[to]==0:
                continue
            EIN[to]-=1
            if EIN[to]==0:
                Q.append(to)
                USE[to]=0

        for fr in EINLIST[x]:
            if USE[fr]==0:
                continue
            EOUT[fr]-=1
            if EOUT[fr]==0:
                Q.append(fr)
                USE[fr]=0

    ANS=shortcut(loopfind())
    if len(ANS)==0:
        print(-1)
    else:
        print(len(ANS))
        for ans in ANS:
            print(ans+1)

main()

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print(-1)
    exit()
X={i for i in range(N)}
for st in range(N):
    before=[-1 for i in range(N)]
    q=deque([st])
    flag=0
    while(q):
        r=q.popleft()
        for p in G[r]:
            if before[p]==-1:
                before[p]=r
                q.append(p)
            if before[st]!=-1:
                Y={st}
                tmp=before[st]
                while(tmp!=st):
                    Y.add(tmp)
                    tmp=before[tmp]
                if len(Y)<len(X):
                    X={i for i in Y}
                flag=1
                break
        if flag:
            break
print(len(X))
for i in X:
    print(i+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,M=map(int,input().split())

EIN=[0]*N
EOUT=[0]*N

EINLIST=[[] for i in range(N)]
EOUTLIST=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1

    EOUT[x]+=1
    EIN[y]+=1

    EOUTLIST[x].append(y)
    EINLIST[y].append(x)

from collections import deque

Q=deque()
USE=[1]*N

for i in range(N):
    if EIN[i]==0 or EOUT[i]==0:
        Q.append(i)
        USE[i]=0

while Q:
    x=Q.pop()

    for to in EOUTLIST[x]:
        if USE[to]==0:
            continue
        EIN[to]-=1
        if EIN[to]==0:
            Q.append(to)
            USE[to]=0

    for fr in EINLIST[x]:
        if USE[fr]==0:
            continue
        EOUT[fr]-=1
        if EOUT[fr]==0:
            Q.append(fr)
            USE[fr]=0
            
def loopfind():
    for i in range(N):
        if USE[i]==1:
            break
    else:
        return []
    
    Q=deque()
    Q.append(i)
    USESET={i}
    ANS=[i]

    while True:
        for to in EOUTLIST[ANS[-1]]:
            if USE[to]==1:
                nextv=to
                break

        if nextv in USESET:
            break
        else:
            ANS.append(nextv)
            USESET.add(nextv)

    x=ANS.index(nextv)
    return ANS[x:]
        

def shortcut(ANS):
    #print(ANS)

    ANSSET=set(ANS)
    LEN=len(ANS)
    flag=0

    for i in range(LEN):
        for to in EOUTLIST[ANS[i]]:
            if to in ANSSET and ANS[(i+1)%LEN]!=to:
                flag=1
                x=ANS.index(to)

                #print(ANS,i,x)

                break
        if flag:
            break
    #print(flag)

    if flag:
        if x<i:
            return shortcut(ANS[x:i+1])
        else:
            return shortcut(ANS[x:]+ANS[:i+1])

    else:
        return ANS

ANS=shortcut(loopfind())
if len(ANS)==0:
    print(-1)
else:
    print(len(ANS))
    for ans in ANS:
        print(ans+1)

Submission status: Accepted

Solution code:
def f_pure():
    # 参考: http://drken1215.hatenablog.com/entry/2019/09/29/012000
    from collections import deque
    N, M = [int(i) for i in input().split()]

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

    shortest = N + 1
    ans = []
    for s in range(N):
        # 頂点sから他の辺へ行くには何個の頂点を辿る必要があるか計算する
        dist = [-1] * N
        previous = [-1] * N  # [n]: 頂点nへはどこから来たか
        queue = deque([s])
        dist[s] = 0
        while queue:
            v = queue.pop()
            for next_node in graph[v]:
                if dist[next_node] == -1:
                    dist[next_node] = dist[v] + 1
                    previous[next_node] = v
                    queue.appendleft(next_node)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue  # 頂点tは始点と同じ、または、始点から到達不可能
            for next_node in graph[t]:
                if next_node == s:  # ループ完成
                    ans_tmp = [s]  # 解になりうる頂点集合
                    current_node = t
                    # 頂点tからsまで巻き戻していく
                    while current_node != s:
                        ans_tmp.append(current_node)
                        current_node = previous[current_node]
                    # 頂点集合の濃度が減少した
                    if shortest > len(ans_tmp):
                        shortest = len(ans_tmp)
                        ans = ans_tmp

    if shortest == N + 1:
        return -1  # 閉路がなかった。条件を満たす頂点集合はない
    return ' '.join(map(str, [len(ans)] + sorted(v + 1 for v in ans)))

print(f_pure())

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
	a,b=map(int,input().split())
	G[a-1].append(b-1)
deg=[0 for i in range(N)]
for i in range(N):
	for p in G[i]:
		deg[p]+=1
q=deque(i for i in range(N) if deg[i]==0)
res=[]
while q:
	u=q.popleft()
	res.append(u)
	for v in G[u]:
		deg[v]-=1
		if deg[v]==0:
			q.append(v)
if len(res)==N:
	print(-1)
	exit()
X={i for i in range(N)}
for st in range(N):
	pre=[-1 for i in range(N)]
	q=deque([st])
	flag=0
	while(q):
		r=q.popleft()
		for p in G[r]:
			if pre[p]==-1:
				pre[p]=r
				q.append(p)
			if pre[st]!=-1:
				Y={st}
				tmp=pre[st]
				while(tmp!=st):
					Y.add(tmp)
					tmp=pre[tmp]
				if len(Y)<len(X):
					X={i for i in Y}
				flag=1
				break
		if flag:
			break
print(len(X))
for i in X:
	print(i+1)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

n, m = map(int, input().split())
xy = [tuple(int(x)-1 for x in input().split()) for _ in range(m)]

R = [[] for _ in range(n)]
h = [0] * n

for x, y in xy:
    R[x].append(y)
    h[y] += 1

S = []

st = []

for i in range(n):
    if h[i] == 0:
        heappush(st, i)

while len(st) > 0:
    temp = heappop(st)
    S.append(temp)
    for x in R[temp]:
        h[x] -= 1
        if h[x] == 0:
            heappush(st, x)

if len(S) != n:
    print(-99999)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
e = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    e[a-1].append(b-1)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print(-1)
    exit()
X={i for i in range(N)}
for st in range(N):
    before=[-1 for i in range(N)]
    q=deque([st])
    flag=0
    while(q):
        r=q.popleft()
        for p in G[r]:
            if before[p]==-1:
                before[p]=r
                q.append(p)
            if before[st]!=-1:
                Y={st}
                tmp=before[st]
                while(tmp!=st):
                    Y.add(tmp)
                    tmp=before[tmp]
                if len(Y)<len(X):
                    X={i for i in Y}
                flag=1
                break
        if flag:
            break
print(len(X))
for i in X:
    print(i+1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


sys.setrecursionlimit(1000000)


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, M, E):
    G = [set() for _ in range(N)]
    for a, b in E:
        G[a].add(b)

    visited = set()
    stk = []
    stki = {}

    def dfs(i):
        if i in visited:
            return

        stki[i] = len(stk)
        stk.append(i)

        for j in G[i]:
            if j in visited:
                continue
            if j in stki:
                si = stki[j]
                vset = set(stk[si:])
                loopd = {}
                for k in range(si, len(stk) - 1):
                    loopd[stk[k]] = stk[k + 1]
                loopd[stk[-1]] = stk[si]
                return slim_loop(vset, loopd)
            result = dfs(j)
            if result:
                return result

        stk.pop()
        del stki[i]
        visited.add(i)
        return None

    def slim_loop(vset, loopd):
        i = next(iter(vset))
        endi = i
        while True:
            jset = G[i] & vset
            if len(jset) > 1:
                oj = loopd[i]
                for j in jset:
                    if j == oj or j not in vset:
                        continue
                    k = loopd[i]
                    while k != j:
                        vset.remove(k)
                        k = loopd[k]
                    loopd[i] = j
                endi = i

            i = loopd[i]
            if i == endi:
                break

        return vset

    for i in range(N):
        if i not in visited:
            result = dfs(i)
            if result:
                return result

    return None


def main():
    N, M = [int(e) for e in inp().split()]
    E = []
    for _ in range(M):
        a, b = [int(e) - 1 for e in inp().split()]
        E.append((a, b))

    result = solve(N, M, E)
    if not result:
        print('-1')
    else:
        print(len(result))
        for v in result:
            print(v + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l,L=[],[]
  for x in h:
   l=[x]+l
   if x in d[v]:break
  while v!=x:
   for y in l:
    if v in d[y]:
     L,v=[v]+L,y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L));sys.exit()
 for u in d[v]:f(u,[u]+h,q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l=[]
  for x in h:
   l=[x]+l
   if x in d[v]:break
  L=[]
  while v!=x:
   for y in l:
    if v in d[y]:
     L=[v]+L
     v=y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L));sys.exit()
 for u in d[v]:f(u,[u]+h,q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Submission status: Accepted

Solution code:
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l=[]
  for x in h[::-1]:
   l=[x]+l
   if x in d[v]:break
  L=[]
  while v!=x:
   for y in l:
    if v in d[y]:
     L=[v]+L
     v=y
     break
  print("\n".join(str(x)for x in[len(L)+1,x]+L[::-1]));sys.exit()
 for u in d[v]:f(u,h+[u],q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

rflag = False
for s in range(N):
	pre = [-1]*N
	start = s
	queue = [start]
	while len(queue)>0:
		nq = []
		for i in queue:
			for j in neighbor[i]:
				if pre[j]==-1:
					pre[j] = i
					nq.append(j)
					if j==start:
						rflag = True
						break
				# else:
				# 	pre[j] = i
				# 	print(pre)
				# 	break

			if rflag: break
		if rflag: break
		queue = nq
	if rflag: break

if not rflag:
	print(-1)
else:
	v = [0]*N
	v[j] = 1
	roop = [j]
	i = j
	while pre[i]!=j:
		pret = pre[i]
		roop.append(pret)
		v[pret] = 1
		i = pret
	roop = roop+[j]
	roop = roop[::-1]

	update = True
	while update:
		update = False
		for i,vi in enumerate(roop):
			if i==len(roop)-1: break
			for ni in neighbor[vi]:
				if ni!=roop[i+1] and v[ni]==1:
					pre[ni] = vi

					v = [0]*N
					v[ni] = 1
					roopn = [ni]
					j = ni
					while pre[j]!=ni:
						pret = pre[j]
						roopn.append(pret)
						v[pret] = 1
						j = pret
					roopn = roopn+[ni]
					update = True
					roop = roopn[::-1]
					break

			if update: break

	K = len(roop)-1
	print(K)
	print(*map(lambda x:x+1,roop[:-1]), sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def find_cycle(graph, vst):
    que = deque([vst])
    dist = [-1] * n
    pre = [-1] * n
    dist[vst] = 0
    flag = False
    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
        # 無向グラフでは祖父の所にいかない工夫が必要。
            if nxt == vst:
                flag = True
                break
            if dist[nxt] != -1:
                continue
            pre[nxt] = cur
            dist[nxt] = dist[cur] + 1
            que += [nxt]
        if flag:
            v = cur
            cycle = []
            while v != -1:
                cycle += [v]
                v = pre[v]
            return cycle


ret_len = INF
n, m = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a - 1] += [b - 1]


min_cycle = 0
for vst in range(n):
    cycle = find_cycle(graph, vst)
    if cycle and len(cycle) < ret_len:
        min_cycle = cycle
        ret_len = len(cycle)


if min_cycle:
    print(ret_len)
    for i in min_cycle:
        print(i + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
vs=set()
def dfs(v,path,pvs):
    lp=l=N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        vs.add(u)
        nl, nlp = dfs(u,path+[u],pvs|{u})
        if nl < l:
            lp, l = nlp, nl
    return l,lp
d = [set() for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    d[a].add(b)
for i in range(N):
    v=i+1
    l,lp=dfs(i+1,[v],{v})
    if l<=N:
        print("\n".join(str(x) for x in[l]+lp))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]
vs=set()

def dfs(v, path):
    lp = 0
    l = N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        pvs.add(u)
        vs.add(u)
        nl, nlp = dfs(u,path+[u])
        if nl < l:
            lp, l = nlp, nl
        pvs.remove(u)
    return l, lp

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int,input().split(" "))
    d[a].add(b)
for i in range(N):
    v=i+1
    pvs = set([v])
    l, lp = dfs(i+1, [v])
    if l != N+1:
        print(l)
        for l in lp:
            print(l)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)


def cycle_size(from_v):
    """
    from_v に戻ってくるまでのステップ数
    :param from_v:
    :return:
    """
    parents = [None] * len(graph)
    seen = [False] * len(graph)
    que = deque([(from_v, 0)])
    while que:
        v, d = que.pop()
        for u in graph[v]:
            if seen[u]:
                continue
            seen[u] = True
            que.appendleft((u, d + 1))
            parents[u] = v
            if u == from_v:
                return d + 1, parents
    return INF, parents


min_v = None
min_size = INF
min_parents = None
for v in range(1, N + 1):
    size, parents = cycle_size(v)
    if size < min_size:
        min_v = v
        min_size = size
        min_parents = parents

if min_size < INF:
    print(min_size)
    print(min_v)
    v = min_parents[min_v]
    while v != min_v:
        print(v)
        v = min_parents[v]
else:
    print(-1)

Submission status: Accepted

Solution code:
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)


def cycle_size(from_v):
    """

    :param from_v:
    :return:
    """
    parents = [None] * len(graph)
    seen = [False] * len(graph)
    que = deque([(from_v, 0)])
    while que:
        v, d = que.pop()
        for u in graph[v]:
            if seen[u]:
                continue
            seen[u] = True
            que.appendleft((u, d + 1))
            parents[u] = v
            if u == from_v:
                return d + 1, parents
    return INF, parents


min_v = None
min_size = INF
min_parents = None
for v in range(1, N + 1):
    size, parents = cycle_size(v)
    if size < min_size:
        min_v = v
        min_size = size
        min_parents = parents

if min_size < INF:
    print(min_size)
    print(min_v)
    v = min_parents[min_v]
    while v != min_v:
        print(v)
        v = min_parents[v]
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a-1, b-1))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    sys.exit()
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle and prev[b] != a:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
        prev[b] = a
print(len(circle))
for i in circle:
    print(i+1)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

vs = set()
def dfs_w(v, d):
    # dfs while版 
    pvs = set([])
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                stack += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Accepted

Solution code:
from collections import deque


def shortest_cycle_path(graph, start):
    """重み無し有向グラフgraphに対して、startから出発してstartに帰るサイクルの最短経路を求める
    サイクルが存在しないときは空のリスト [] を返す
    例) start = 0 のときの最短サイクルが 0 -> 3 -> 1 -> 0 のとき、
        [0, 3, 1, 0] を返す
    """
    n = len(graph)
    dist = [-1] * n
    prev_pos = [-1] * n
    q = deque([start])
    dist[start] = 0
    while q:
        pos = q.pop()
        for next_pos in graph[pos]:
            if dist[next_pos] == -1:
                dist[next_pos] += dist[pos] + 1
                prev_pos[next_pos] = pos
                q.append(next_pos)

    # path := サイクル経路の頂点, path_len := サイクル長
    # サイクル長 = len(path) - 1 となることに注意
    path = []
    path_len = 10**9 + 7
    for goal in range(n):
        if start == goal or dist[goal] == -1:
            continue
        for next_pos in graph[goal]:
            # goalからstartへのパスが存在するとき(つまりサイクルが存在するとき)
            if next_pos == start:
                tmp_path = []
                pos = goal
                while True:
                    tmp_path.append(pos)
                    if pos == start:
                        break
                    pos = prev_pos[pos]
                if len(tmp_path) < path_len:
                    path_len = len(tmp_path)
                    path = [start] + tmp_path[0:]
    path = path[::-1]
    return path


n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for i in range(m):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)

len_ans = 10**9 + 7
ans = []
for i in range(n):
    tmp = shortest_cycle_path(graph, i)
    if len(tmp) != 0 and len(tmp) < len_ans:
        len_ans = len(tmp)
        ans = tmp
if ans:
    print(len(ans) - 1)
    for i in range(len(ans) - 1):
        print(ans[i] + 1)
else:
    print(-1)