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:

from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)

    shortest = N + 1
    res = []
    for s in range(N):
        dist = [-1] * N
        pre = [-1] * N
        q = deque()
        q.append(s)
        dist[s] = 0
        while q:
            v = q.popleft()
            for to in G[v]:
                if dist[to] == -1:
                    dist[to] = dist[v] + 1
                    pre[to] = v
                    q.append(to)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue
            for to in G[t]:
                if to == s:  # サイクルになっている頂点
                    tmp = [s]
                    cur = t
                    while cur != s:
                        tmp.append(cur)
                        cur = pre[cur]
                    if shortest > len(tmp):
                        shortest = len(tmp)
                        res = tmp

    if shortest == N + 1:
        print(-1)
    else:
        print(len(res))
        res.sort()
        for v in res:
            print(v + 1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()
	G=[[] for _ in range(n+1)]

	for _ in range(m):
		a,b=MI()
		G[a].append(b)

	A=[10**5]*(n+1)

	for i in range(1,n+1):
		Q=deque([[i,0]])
		D=[-1]*(n+1)
		while Q:
			#print(Q)
			now,d=Q.popleft()
			if now==i and d>0:
				A[i]=d
				break
			for nx in G[now]:
				if D[nx]==-1:
					D[nx]=d+1
					Q.append([nx,d+1])
	#print(A)

	k=min(A)
	#print(k)

	if k==10**5:
		print(-1)
		exit()

	s=A.index(k)
	#print(s)

	A=[]
	Q=deque([[s,0]])
	D=[10**5]*(n+1)

	while Q:
		now,d=Q.pop()
		if now==s and d>0:
			break
		if d==k:
			continue
		A.append(now)
		for nx in G[now]:
			if D[nx]>d+1:
				D[nx]=d+1
				Q.append([nx,d+1])
	D[s]=0

	#print(A)
	#print(D)

	ans=[]
	d=k-1
	for i in reversed(A):
		if D[i]==d:
			ans.append(i)
			d-=1

	print(k)
	print(*ans[::-1],sep="\n")










if __name__ == "__main__":
	main()

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        sub = []
        
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        sub = [key+1]
                        now = key
                        while now != i:
                            sub.append(par[now]+1)
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if sub:
                break
            
        if sub:
            if ans:
                if len(ans) > len(sub):
                    ans = copy(sub)
            else:
                ans = copy(sub)
            
        
    if ans:
        print(len(ans))
        for a in ans:
            print(a)
    else:
        print(-1)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
p = [None for i in range(N)]
def detect_cycle(graph):
  N = len(graph)
  Q = [i for i in range(N)]
  cycle = []
  while Q:
    state = [-1 for i in range(N)]
    s = Q.pop()
    if p[s] != None: continue
    p[s] = -1
    q = [s]
    while q:
      x = q.pop()
      if x < 0:
        state[~x] = 0
        continue
      q.append(~x)
      for y in graph[x]:
        state[x] = 1
        if state[y] == 0: continue
        elif state[y] == -1:
          p[y] = x
          q.append(y)
        else:
          p[y] = x
          now = x
          while now != y:
            cycle.append(now)
            now = p[now]
          cycle.append(y)
          return cycle
  return cycle

def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

c = detect_cycle(graph)
if not c:
  print(-1)
else:
  squeeze(c)

Submission status: Accepted

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
p = [None for i in range(N)]
def detect_cycle(graph):
  N = len(graph)
  Q = [i for i in range(N)]
  
  cycle = []
  while Q:
    state = [-1 for i in range(N)]
    FLAG = 0
    s = Q.pop()
    if p[s] != None: continue
    p[s] = -1
    q = [s]
    while q:
      flag = 0
      x = q.pop()
      if x < 0:
        state[~x] = 0
        continue
      q.append(~x)
      for y in graph[x]:
        state[x] = 1
        if state[y] == 0: continue
        elif state[y] == -1:
          p[y] = x
          q.append(y)
        else:
          p[y] = x
          now = x
          while now != y:
            cycle.append(now)
            now = p[now]
          cycle.append(y)
          flag = 1
          break
      if flag:
        FLAG = 1
        break
    if FLAG:
      break
  return cycle

def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

c = detect_cycle(graph)
if not c:
  print(-1)
else:
  squeeze(c)

Submission status: Accepted

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if y in l:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)

Submission status: Accepted

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

def DD(arg): return defaultdict(arg)
INF = float('inf')

N,M = list(map(int,input().split()))
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  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

#####MakeDivisors######
def make_divisors(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)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)

Submission status: Accepted

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

def find_cycle(adj, start = 0):
    """
    有効グラフ上で、0-indexedが前提の実装。
    あれば、適当なサイクルをリストで返す。
    参考1: https://qiita.com/drken/items/a803d4fc4a727e02f7ba
    参考2: https://qiita.com/Kiri8128/items/2b0023bed9af642c751c
    """
    global arrived, finished
    stack = [~start, start]
    history = []
    while stack:
        v = stack.pop()
        if v >= 0:
            arrived[v] = True
            history.append(v)
            for nv in adj[v]:
                if not arrived[nv]:
                    stack.append(~nv)
                    stack.append(nv)
                elif not finished[nv]: #arrived but not finished -> a cycle exists.
                    index = history.index(nv)
                    return history[index:]
        else:
            finished[~v] = True
            history.pop()
    return []

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)


arrived = [False] * N
finished = [False] * N
while False in arrived:
    start = arrived.index(False)
    cycle = find_cycle(adj, start)
    if cycle:
        break

if not cycle:
    print(-1)
    exit()
else:
    cycle_updated = True
    while cycle_updated:
        cycle_updated = False
        cycle_index = {v:i for i, v in enumerate(cycle)}
        l = len(cycle)
        for i, v in enumerate(cycle):
            cv = cycle[i+1-l]
            for nv in adj[v]:
                if nv != cv and nv in cycle_index:
                    cycle_updated = True
                    j = cycle_index[nv]
                    if i < j:
                        cycle = cycle[:i+1] + cycle[j:]
                    else:
                        cycle = cycle[j:i+1]
                    break
            if cycle_updated:
                break
    print(len(cycle))
    print(*[elem+1 for elem in cycle], sep = '\n')

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")


from collections import defaultdict
n,m = map(int, input().split())
ns = defaultdict(set)
es = set()
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    es.add((u,v))

### サイクル検出 cycle detection

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:]
# 極小サイクルを復元
def sub(hist):
    s = set(hist)
    ss = set((hist[i],hist[i+1]) for i in range(len(hist)-1))
    ss.add((hist[len(hist)-1], hist[0]))
    l = None
    for u,v in es:
        if u in s and v in s and (u,v) not in ss:
            l = []
            for i,k in enumerate(hist):
                if k==v:
                    break
            for j in range(i,len(hist)):
                l.append(hist[j])
                if hist[j]==u:
                    break
            else:
                for j in range(len(hist)):
                    l.append(hist[j])
                    if hist[j]==u:
                        break
#     print(hist, l, i, u,v,ss)
    if l is None or len(l)==len(hist):
        return hist
    else:
        return sub(l)
ans = None
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        hist = cycle(hist, pos)
        ans = sub(hist)
        break
if ans is None:
    print(-1)
else:
    print(len(ans))
    write("\n".join(map(lambda x: str(x+1), ans)))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for a,b in AB:
    c[a-1].append(b-1)
from collections import deque
import sys
sys.setrecursionlimit(10**9)
def f2(q):
    s=set(q)
    for a,b in AB:
        if a in s and b in s:
            i=q.index(b)
            if q[i-1]!=a:
                break
    if a in s and b in s and q[i-1]!=a:
        q2=deque([a,b])
        while q[(i+1)%len(q)]!=a:
            q2.append(q[(i+1)%len(q)])
            i+=1
        f2(q2)
    print(len(q),*q,sep='\n')
    exit()
v=[0]*N 
w=[0]*N
def f(p,v,q):
    v[p]=1
    w[p]=1
    q.append(p+1)
    for n in c[p]:
        if v[n]:
            f2(q)
        else:
            f(n,v,q)
    q.pop()
    v[p]=0
for p in range(N):
    if w[p]==0:
        f(p,v,deque())
print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq


def main():
    N, M = list(map(int, input().split()))
    adj = defaultdict(list)
    for _ in range(M):
        A, B = list(map(lambda x: int(x) - 1, input().split()))
        adj[A].append(B)
    # 最小サイズのサイクルを探す
    min_cycle_size = N + 1
    min_cycle = list()
    for s in range(N):
        parent = [None] * N
        que = [(0, s)]
        while len(que) > 0:
            dist, node = heapq.heappop(que)
            if dist > 0 and node == s:
                break
            for next_node in adj[node]:
                if parent[next_node] is not None:
                    continue
                parent[next_node] = node
                heapq.heappush(que, (dist + 1, next_node))
        # s始まりの最小サイクルが見つかった場合
        if parent[s] is not None:
            cycle = [s]
            node = parent[s]
            while node != s:
                cycle.append(node)
                node = parent[node]
            if len(cycle) < min_cycle_size:
                min_cycle_size = len(cycle)
                min_cycle = cycle
    # 答え
    if min_cycle_size > N:
        print(-1)
    else:
        print(min_cycle_size)
        for node in min_cycle:
            print(node + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve(G, p, ans, st, fst, arr, x):
    arr[p] = x
    cnt_1 = 0
    z = -1
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
            z = nxt
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            k = arr[z]
            for v in st:
                if arr[v] >= k:
                    ans.append(v)
            return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst, arr, x+1):
            return True
        st.remove(nxt)
    arr[p] = 0
    return False

def main():
    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)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M=map(int,input().split())
edge=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int1,input().split())
    edge[a].append(b)

used=[False]*N
for i in range(N):
    if used[i]==True:
        continue
    stack=[i]
    path=[]
    while stack:
        v=stack.pop()
        if v>=0:
            used[v]=True
            path.append(v)
            for nv in edge[v]:
                if not used[nv]:
                    stack.append(~v)
                    stack.append(nv)
                else:
                    if nv in path:
                        path.append(nv)
                        break
            else:
                continue
            break
        else:
            path.pop()
    else:
        continue
    break
else:
    print(-1)
    exit()
cycle=path[path.index(path[-1]):]
while True:
    s=set(cycle)
    next_cycle=[]
    for i,v in enumerate(cycle[:-1]):
        next_cycle.append(v)
        for nv in edge[v]:
            if nv==cycle[i+1]:
                continue
            if nv in s:
                next_cycle.extend(cycle[cycle.index(nv):])
                break
        else:
            continue
        break
    else:
        break
    cycle=[]
    ss=set()
    for v in next_cycle:
        if v in ss:
            vv=v
            break
        ss.add(v)
    f=False
    for v in next_cycle:
        if v==vv:
            cycle.append(v)
            if not f:
                f=True
            else:
                break
        elif f:
            cycle.append(v)
    
print(len(cycle)-1)
for v in cycle[:-1]:
    print(v+1)

Submission status: Accepted

Solution code:
from collections import deque

INF = 10**18
N, M = map(int, input().split())

graph = [[] for _ in range(N)]

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

loopsize = INF

for root in range(N):
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in graph[node]:
            if adj == root:
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    else:
        continue
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)

if loopsize != INF:
    print(loopsize)
    for node in path:
        print(node + 1)
else:
    print(-1)