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 = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

for i in range(m):
    a,b = map(int, input().split())
    ns[a-1].add(b-1)

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
def cycle(hist, pos):
    for i, u in enumerate(hist):
        if u==pos:
            break
    return hist[i:]

for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        hist = cycle(hist, pos)
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                pu = hist[(i-1)]
                if (ns[u]&us)-set([nu, pu]):
                    for v in (ns[u]&us)-set([nu, pu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

from collections import defaultdict, deque
g = defaultdict(list)
for a, b in ab:
    g[a-1].append(b - 1)

ans = None
for start in range(n):
    visited = [0] * n
    visited[start] = 1
    q = deque([start])
    prev = [None] * n

    f = False
    while q:
        cur = q.popleft()

        for target in g[cur]:
            if visited[target] == 0:
                visited[target] = 1
                q.append(target)
                prev[target] = cur

            if target == start:
                f = True
                break

        if f:
            break

    if f:
        loop = [target]
        while cur != None:
            loop.append(cur)
            cur = prev[cur]

        loop = loop[::-1]
        v = set(loop)

        f2 = True
        for i in range(len(loop) - 1):
            a, b = loop[i], loop[i+1]

            for target in g[a]:
                if target in v and target != b:
                    f2 = False
                    break

            if f2 == False:
                break

        if f2:
            ans = loop[:-1]
            break

if ans == None:
    print(-1)
else:
    print(len(ans))
    for _ans in ans:
        print(_ans + 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, M, AB):
    from collections import defaultdict, deque
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)

    def bfs(s):
        q = deque()
        q.append(s)
        prev = {}
        while q:
            u = q.popleft()
            for v in g[u]:
                if v in prev:
                    continue
                q.append(v)
                prev[v] = u
                if v == s:
                    break

        if s not in prev:
            return None

        cycle = [s]
        v = s
        while True:
            v = prev[v]
            if v == s:
                break
            cycle.append(v)
        return cycle

    ans = None
    for i in range(1, N+1):
        t = bfs(i)
        if t is not None:
            if ans is None:
                ans = t
            else:
                ans = t if len(t) < len(ans) else ans
    if ans is not None:
        return [len(ans)] + ans
    return [-1]


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(*slv(N, M, AB), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

graph=[set() for _ in range(N+1)]
for _ in range(M):
  A,B=map(int,input().split())
  graph[A].add(B)
#print(graph)

visited=[False]*(N+1)
def dfs(path):
  global cycle
  u=path[-1]
  
  visited[u]=True  
  for v in graph[u]:
    if visited[v]:
      cycle=list(path+[v])
      return
    else:
      dfs(path+[v])      
    if cycle:
      return    
  visited[u]=False
  
cycle=[]
for i in range(1,N+1):
  dfs([i])
  if cycle:
    break
else:
  print(-1)
  sys.exit(0)
    
#remove prefix  
for i in range(len(cycle)):
  if cycle[i]==cycle[-1]:
    cycle=cycle[i:]
    break
#print(cycle)

cycle_set=set(cycle)
subgraph=[set() for _ in range(N+1)]
for c in cycle_set:
  for v in graph[c]:
    if v in cycle_set:
      subgraph[c].add(v)
#print(subgraph)    

#visited=[False]*(N+1)
ex_path=[]
def dfs2(path,t):
  global ex_path
  u=path[-1]
  if u==t:
    ex_path=path
    return
  
  for v in graph[u]:
    dfs2(path+[v],t)
    if ex_path:
      return

graph=subgraph
while True:
  for i in range(len(cycle)-1):
    u=cycle[i]
    v=cycle[i+1]
    w=-1
    if len(graph[u])>1:
      for x in graph[u]:
        if x!=v:
          w=x
          break
      break
  else:
    print(len(cycle)-1)
    for i in range(len(cycle)-1):
      print(cycle[i])
    sys.exit(0)
    
  #print(u,v,w)
  #w->u
  dfs2([w],u)
  cycle=ex_path+[w]
  #print(cycle)
  cycle_set=set(cycle)
  subgraph=[set() for _ in range(N+1)]
  for c in cycle_set:
    for v in graph[c]:
      if v in cycle_set:
        subgraph[c].add(v)
        
  graph=subgraph

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
    def bfs(start):
        pre = [-1]*n
        d = deque([start])

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    return path

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return []
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if 0 < len(temp) < len(res):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 閉路検出を繰り返し, 閉路の長さを減らしていく

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)



    def bfs(start):
        pre = [-1]*n
        d = deque([start])

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    return path

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return -1
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp != -1 and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)



    def bfs(start):
        pre = [-1]*n
        d = deque([start])
        res = []

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                        res = path
                    break

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return res
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 閉路検出を繰り返し, 閉路の長さを減らしていく































def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)


    def bfs(start):
        pre = [-1]*n
        d = deque([start])
        res = []

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    if not res or len(res) > len(path):
                        res = path
                    break

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return res
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp and len(res) > len(temp):
            res = temp
    if len(res) <= n:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)

    # 始点, 今回見る点
    def dfs(s, v):
        for nv in adj[v]:
            if nv == s:
                return [v]
            if visited[nv] == 1:
                continue
            visited[nv] = 1
            res = dfs(s, nv)
            if res != -1:
                res.append(v)
                return res
        return -1


    for s in range(n):
        visited = [0]*n
        visited[s] = 1
        heiro = dfs(s, s)
        if heiro != -1:
            break
    else:
        print(-1)
        exit()
    heiro = heiro[::-1]

    def graph(s, g):
        res = [s]
        d = deque([s])
        for i in range(len(heiro)):
            if heiro[i] == s:
                idx = i
                break
        while d:
            v = d.popleft()
            for nv in adj[v]:
                if visited[nv] == 1 and nv == g:
                    res.append(nv)
                    return res
            d.append(heiro[idx+1])
            res.append(heiro[idx+1])
            idx += 1
            if idx == len(heiro)-2:
                idx = -1
            #ここ
            if res[-1] == heiro[heiro.index(s)-1]:
                return res

    while True:
        heiro.append(heiro[0])
        visited = [0]*n
        f = 0
        for i in heiro:
            visited[i] = 1
        new_heiro = [heiro[0]]
        for i in range(len(heiro)-1):
            for nv in adj[heiro[i]]:
                if visited[nv] == 1 and nv != heiro[i+1]:
                    new_heiro = graph(nv, heiro[i])
                    f = 1
                    break
            else:
                new_heiro.append(heiro[len(new_heiro)])
            if f:
                heiro = new_heiro
                break
        else:
            break

    print(len(heiro)-1)
    for i in heiro[:-1]:
        print(i+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = deque()
	Q.append(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	jud = "No"
	while Q:
		v = Q.popleft()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.append(i)
				if i == g:
					jud = "Yes"
					break
		if jud == "Yes":
			break

	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return dist[g], path[::-1]
	else:
		return INF, []

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)

	ans = 100000
	path = None
	for i in range(M):
		predis, prepath = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath

	if ans == 100000:
		print(-1)
	else:
		print(ans + 1)
		for i in path:
			print(i + 1)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from collections import deque
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, M, AB):

    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)

    def bfs(s):
        q = deque([s])
        done = {}
        done[s] = 0
        prev = {}
        goal = None
        while q:
            u = q.popleft()
            for v in g[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    prev[v] = u
                    q.append(v)
                if v == s:
                    goal = u
                    break
        if goal is None:
            return None
        v = goal
        ans = [s]
        while v in prev:
            ans.append(v)
            v = prev[v]
        return ans

    ans = [0] * (2*N)
    for i in range(1, N+1):
        a = bfs(i)
        if a and len(ans) > len(a):
            ans = a
    if len(ans) == (2*N):
        print(-1)
        return
    print(len(ans))
    print(*ans, sep='\n')


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv(N, M, AB):
    from collections import defaultdict

    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)

    def bfs(s):
        q = deque([s])
        done = {}
        done[s] = 0
        prev = {}
        goal = None
        while q:
            u = q.popleft()
            for v in g[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    prev[v] = u
                    q.append(v)
                if v == s:
                    goal = u
                    break
        if goal is  None:
            return None
        v = goal
        ans = [s]
        while v in prev:
            ans.append(v)
            v = prev[v]
        return ans

    from collections import deque
    ans = [0] * (2*N)
    for i in range(1, N+1):
        a = bfs(i)
        if a and len(ans) > len(a):
            ans = a
    if len(ans) == (2*N):
        print(-1)
        return
    print(len(ans))
    print(*ans, sep='\n')


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    slv(N, M, AB)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    l = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1].append(b-1)
    c = [0] * N
    loop = []
    def cyclic(n):
        if c[n] == 2:
            return False
        if c[n] == 1:
            loop.append(n)
            return True
        c[n] = 1
        for i in l[n]:
            if cyclic(i):
                loop.append(n)
                return True
        c[n] = 2
        return False
    for i in range(N):
        if cyclic(i):
            break
    if len(loop) == 0:
        print(-1)
        return
    loop.reverse()
    t = loop[-1]
    loop = loop[loop.index(t):]
    ll = set(loop)
    flag = True
    while flag:
        for i, v in enumerate(loop[:-1]):
            flag2 = False
            for j in l[v]:
                if j in ll and loop[i + 1] != j:
                    if loop.index(j) == 0:
                        loop = loop[:i+1] + [j]
                    elif loop.index(j) < i:
                        loop = loop[loop.index(j):i+1] + [j]
                    else:
                        loop = loop[:i+1] + loop[loop.index(j):]
                    ll = set(loop)
                    flag2 = True
                    break
            if flag2:
                break
        else:
            flag = False
    loop = set(loop)
    print(len(loop))
    for i in loop:
        print(i+1)
    return
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
    N, M = map(int, input().split())
    l = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1].append(b-1)
    c = [0] * N
    loop = []
    def cyclic(n):
        if c[n] == 2:
            return False
        if c[n] == 1:
            loop.append(n)
            return True
        c[n] = 1
        for i in l[n]:
            if cyclic(i):
                loop.append(n)
                return True
        c[n] = 2
        return False
    for i in range(N):
        if cyclic(i):
            break
    if len(loop) == 0:
        print(-1)
        return
    print(0)
    return
main()

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            return 0
    return -1
print(main())

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    V = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        V[a - 1].append(b - 1)
    C = [0] * N
    loop = []
    def dfs(n):
        if C[n] == 2:
            return False
        if C[n] == 1:
            loop.append(n)
            return True
        C[n] = 1
        for i in V[n]:
            if dfs(i):
                loop.append(n)
                return True
        C[n] = 2
        return False
    for i in range(N):
        if dfs(i):
            break
    if len(loop) == 0:
        print('-1')
        return
    for i in range(1, len(loop)):
        if loop[i] == loop[0]:
            break
    loop = loop[:i][::-1]

    def minimize(l):
        s = set(l)
        for i in range(len(l)):
            for j in V[l[i]]:
                if j == l[(i + 1) % len(l)]:
                    continue
                if j in s:
                    break
            else:
                continue
            break
        else:
            return l
        I = {m: k for k, m in enumerate(l)}
        j = I[j]
        if i < j:
            l = l[0:i + 1] + l[j:]
        else:
            l = l[j:i + 1]
        return l
    while True:
        t = len(loop)
        loop = minimize(loop)
        if len(loop) == t:
            break
    print(t)
    print('\n'.join(str(i + 1) for i in loop))
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)

def dfs(v, o):
    for c in G[v]:
        if c == o:
            return [v]
    for c in G[v]:
        if visited[c]:
            continue
        visited[c] = True
        ret = dfs(c, o)
        if ret:
            return [v] + ret

for v in range(1, N+1):
    visited = [False] * (N+1)
    cur = dfs(v, v)
    if cur:
        break
else:
    print(-1)
    exit()

while True:
    cur_set = set(cur)
    unused = None
    for i in range(len(cur)):
        u, v = cur[i], cur[(i+1) % len(cur)]
        for c in G[u]:
            if c == v:
                continue
            elif c in cur_set:
                unused = (i, cur.index(c))
                break

    if not unused:
        break
    else:
        t, s = unused
        nxt = []
        i = s
        while i != t:
            nxt.append(cur[i])
            i = (i + 1) % len(cur)
        nxt.append(cur[t])
        cur = nxt

print(len(cur))
print(*cur, sep='\n')

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
from collections import deque

links = [set() for _ in range(n+1)]
for _ in range(m):
    a,b = map(int, input().split())
    links[a].add(b)

def bfs(links, start):
    parent = [-1] * (n+1)
    selfdepth = 10**6
    d = deque()
    done = {start}
    d.append((start,0))
    while(d):
        edge,depth = d.popleft()
        for i in links[edge]:
            if(i == start):
                selfdepth = depth + 1
                parent[i] = edge
                return( selfdepth, parent )
            if(not i in done):
                parent[i] = edge
                d.append((i,depth+1))
                done.add(i)

    return ( selfdepth, parent )

k = 10**6
start = -1
for i in range(1,n+1):
    selfdepth, parent_tmp = bfs(links, i)
    if(k > selfdepth):
        k = selfdepth
        start = i
        parent_k = parent_tmp

if(start == -1):
    print(-1)
    exit()

print(k)
print(start)
now = parent_k[start]
cnt = 0
while(now != start):
    print(now)
    now = parent_k[now]

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる


    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる






n,k = m()

g = cl.defaultdict(set)

gb = cl.defaultdict(set)
for i in range(k):
    a,b = m()
    a -= 1
    b -= 1
    g[a].add(b)
    gb[b].add(a)

ans = [None for i in range(n)]

for opt in range(n):
    for start in g[opt]:
        cost = [-1]*n
        cost[start] = 0
        de = [start]
        po = []
        fl = True

        while len(de) > 0 and fl:
            po = []
            for i in de:
                for j in g[i]:
                    if cost[j] < 0:
                        cost[j] = cost[i] + 1
                        po.append(j)
                        if j == opt:
                            fl = False
            de = po

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