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 defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
    

g = Graph()
N, M = [int(i) for i in input().split()]

for i in range(M):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(u-1, v-1+N, 1)

ans_n = 10 ** 6
ans_index = -1
for i in range(N):
    d = Dijkstra(g, i)
    ans_n_ = d.dist[i+N]

    if ans_n_ < ans_n:
        ans_index = i
        ans_n = ans_n_

if ans_n == 10 ** 6:
    print(-1)
else:
    d = Dijkstra(g, ans_index)
    ans = d.shortest_path(ans_index + N)
    ans.sort()
    print(ans_n)
    for j in range(ans_n):
        print(ans[j]+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版 
    vs.add(v)
    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:
            pvs.add(v)
            path.append(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
                vs.add(u)
                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

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edgesR[to].append(fr)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()
    V = set(L)
    dist = [float('inf')] * N
    que = deque([(loopStart, 0)])

    while que:
        now, d = que.popleft()

        if dist[now] <= d:
            if now == loopStart:
                dist[loopStart] = d
                break
            continue
        dist[now] = d

        for to in edges[now]:
            if to in V:
                que.append((to, d + 1))

    ans = [loopStart]
    now = loopStart
    while dist[now] > 1:
        for back in edgesR[now]:
            if dist[now] - 1 == dist[back]:
                ans.append(back)
                now = back
                break

    ans = set([a + 1 for a in ans])
    print(len(ans))
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = []
    K = len(L)
    for i, now in enumerate(L):
        for to in edges[now]:
            if i + 1 >= K or to == L[i + 1]:
                ans.append(now + 1)
                break
        else:
            break
    else:
        print(0)
        print()
        # print(len(ans))
        # print(*ans, sep='\n')
        exit()

print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    print(0)
    print()
    exit()

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)

Submission status: Accepted

Solution code:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

for i in range(N):
    r = DFS(i,0)
    if r > 0:
        for j in range(N):
            if visit[j] < r:
                S.discard(j)
        for j in range(N):
            if j in S:
                for k in to[j]:
                    if k in S:
                        if visit[k] < visit[j]:
                            for l in range(N):
                                if visit[l] < visit[k] or visit[l] > visit[j]:
                                    S.discard(l)
                        else:
                            for l in range(N):
                                if visit[l] > visit[j] and visit[l] < visit[k]:
                                    S.discard(l)
        print(len(S))
        for j in list(S):
            print(j+1)
        break
    if i == N-1:
        print(-1)

Submission status: Accepted

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

class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for vs in self.adj:
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v.extend(to_be_added)
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

    def extract_cycle(self):
        self.seen = [0] * self.n
        self.checked = [0] * self.n
        self.hist = deque()
        self.node_in_cycle = -1

        def dfs(v):
            self.seen[v] = 1
            self.hist.append(v)
            for nv in self.adj[v]:
                if self.checked[nv]:
                    continue
                if self.seen[nv] and not self.checked[nv]:
                    self.node_in_cycle = nv
                    return
                dfs(nv)
                if self.node_in_cycle != -1:
                    return
            self.hist.pop()
            self.checked[v] = 1

        for i in range(self.n):
            if not self.checked[i]:
                dfs(i)
            if self.node_in_cycle != -1:
                break
        if self.node_in_cycle == -1:
            return []
        else:
            cycle = []
            while self.hist:
                t = self.hist.pop()
                cycle.append(t)
                if t == self.node_in_cycle:
                    break
            cycle.reverse()
            return cycle

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)

DG = DirectedGraph(edge)
cycle = DG.extract_cycle()

if len(cycle) == 0:
    print(-1)
    exit()

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        exit()

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

Submission status: Accepted

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

class DirectedGraph:
    def __init__(self, adj):
        self.n = len(adj)
        self.adj = adj
        self.is_asyclic = False
        self.max_path_len = None

    def topological_sort(self):
        indegree = [0] * self.n
        for i, vs in enumerate(self.adj):
            for dest in vs:
                indegree[dest] += 1
        zero_v = []
        for v, indeg in enumerate(indegree):
            if indeg == 0:
                zero_v.append(v)
        max_path_len = 1
        tp_sorted = []
        to_be_added = []
        while True:
            while zero_v:
                v = zero_v.pop()
                tp_sorted.append(v)
                for dest in self.adj[v]:
                    indegree[dest] -= 1
                    if indegree[dest] == 0:
                        to_be_added.append(dest)
            if len(to_be_added) > 0:
                zero_v += to_be_added
                to_be_added = []
                max_path_len += 1
            else:
                break
        if len(tp_sorted) == self.n:
            self.is_asyclic = True
            self.max_path_len = max_path_len
            return tp_sorted
        else:
            self.is_asyclic = False
            return None

    def extract_cycle(self):
        self.seen = [0] * self.n
        self.checked = [0] * self.n
        self.hist = deque()
        self.node_in_cycle = -1

        def dfs(v):
            self.seen[v] = 1
            self.hist.append(v)
            for nv in self.adj[v]:
                if self.checked[nv]:
                    continue
                if self.seen[nv] and not self.checked[nv]:
                    self.node_in_cycle = nv
                    return
                dfs(nv)
                if self.node_in_cycle != -1:
                    return
            self.hist.pop()
            self.checked[v] = 1

        for i in range(self.n):
            if not self.checked[i]:
                dfs(i)
            if self.node_in_cycle != -1:
                break
        if self.node_in_cycle == -1:
            return []
        else:
            cycle = []
            while self.hist:
                t = self.hist.pop()
                cycle.append(t)
                if t == self.node_in_cycle:
                    break
            cycle.reverse()
            return cycle

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(m):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)

DG = DirectedGraph(edge)
cycle = DG.extract_cycle()

if len(cycle) == 0:
    print(-1)
    exit()

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        exit()

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

Submission status: Accepted

Solution code:
from collections import deque

n, m = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
inverse = [[] for _ in range(n)]
ab = []
for i in range(m):
    a, b = [int(item) - 1 for item in input().split()]
    ab.append((a, b))
    edge[a].append(b)

seen = [0] * n
checked = [0] * n
hist = deque()
ret = -1
def dfs(v):
    global ret
    seen[v] = 1
    hist.append(v)
    for nv in edge[v]:
        if checked[nv]: 
            continue
        if seen[nv] and not checked[nv]:
            ret = nv
            return
        dfs(nv)
        if ret != -1: 
            return
    hist.pop()
    checked[v] = 1

for i in range(n):
    dfs(i)
    if ret != -1:
        break

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

cycle = []
while hist:
    t = hist.pop()
    cycle.append(t)
    if t == ret:
        break
cycle.reverse()

while True:
    in_cycle = set(cycle)
    deg = [0] * n 
    for item in cycle:
        for v in edge[item]:
            if v in in_cycle:
                deg[v] += 1
    
    ok = True
    for i, item in enumerate(cycle):
        if deg[item] > 1:
            ok = False
            cur_id = start = i
    if ok:
        print(len(cycle))
        print("\n".join([str(item + 1) for item in cycle]))
        exit()

    ncycle = []
    cur = cycle[cur_id]
    while True:
        ncycle.append(cur)
        if cycle[start] in edge[cur]:
            break
        cur_id = (cur_id + 1) % len(cycle)
        cur = cycle[cur_id]
    cycle = ncycle[:]

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i,o=[0]*n,[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v in range(n)if i[v]<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a].append(b)
ansr, ansd = -1, INF
for r in range(1, N+1):
    d = [INF] * (N+1)
    d[0] = 0
    dq = deque()
    for w in es[r]:
        dq.append(w)
        d[w] = 1
    while len(dq) > 0:
        v = dq.popleft()
        if v == r:
            break
        nd = d[v]+1
        for u in es[v]:
            if nd < d[u]:
                d[u] = nd
                dq.append(u)
    if d[r] < ansd:
        ansd = d[r]
        ansr = r
if ansr == -1:
    print(-1)
else:
    vis = [0] * (N+1)
    vis[0] = 1
    p = [-1] * (N+1)
    dq = deque()
    for v in es[ansr]:
        vis[v] = 1
        p[v] = 0
        dq.append(v)
    while len(dq) > 0:
        v = dq.popleft()
        if v == ansr:
            break
        for u in es[v]:
            if vis[u] == 0:
                vis[u] = 1
                p[u] = v
                dq.append(u)
    lst = []
    v = ansr
    while p[v] != -1:
        lst.append(v)
        v = p[v]
    print(len(lst))
    print(*lst, sep = '\n')

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

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

for i in range(M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)


for start in range(N):
	parent = [-1] * N
	depth = [0] * N
	que = deque([])
	que.append(start)
	depth[start] = 1
	while len(que) > 0:
		node = que.popleft()
		judge = 0
		if len(graph[node]) > 0:
			for node_next in graph[node]:
				if depth[node_next] == 1:
					judge = 1
				if depth[node_next] == 0:
					depth[node_next] = depth[node] + 1
					que.append(node_next)
					parent[node_next] = node
		if judge == 1:
			last = node
			break
	if judge == 1:
		break


if judge != 1:
	print(-1)
	exit()

node_list = deque([last])
while True:
	loc = parent[node_list[0]]
	if loc == -1:
		break
	else:
		node_list.appendleft(loc)

node_set = set([node_list[0]])


for i in range(1, len(node_list)):
	max_depth = -1
	for edge in graph[node_list[i]]:
		if edge in node_set:
			for j in range(i):
				if edge == node_list[j]:
					max_depth = max(max_depth, j)
	if max_depth >= 0:
		start = max_depth
		end = i
		break
	node_set.add(node_list[i])

#print(node_set, node_list, depth)
print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 1)

Submission status: Accepted

Solution code:
from collections import deque
from copy import deepcopy


# detection of a cycle
def detect_cycle(N, repn):
    color = ['WHITE'] * (N + 1)
    unfinished_vertex = set([i for i in range(1, N + 1)])
    cycle = []
    Repn = deepcopy(repn)

    def dfs(u0):
        deq = deque([u0])
        color[u0] = 'GRAY'

        while deq != deque([]) and cycle == []:
            u = deq[-1]
            if len(Repn[u]) != 0:
                v = Repn[u].popleft()
                if color[v] == 'WHITE':
                    color[v] = 'GRAY'
                    deq.append(v)
                elif color[v] == 'GRAY':
                    cycle.append(v)
            else:
                deq.pop()
                color[u] = 'BLACK'
                unfinished_vertex.remove(u)

        return deq

    while cycle == [] and unfinished_vertex != set([]):
        u = unfinished_vertex.pop()
        unfinished_vertex.add(u)
        deq = dfs(u)
        #print('deq = {}, cycle = {}'.format(deq, cycle))
    #print('deq = {}'.format(deq))
    if cycle != []:
        v = cycle.pop()
        while True:
            u = deq.pop()
            cycle.append(u)
            if u == v:
                break
        cycle.reverse()
        return cycle # cycle = [v -> ... -> u (-> v)]
    else:
        return []

# one-step minimization of a cycle
def minimize_cycle(cycle, repn):
    length = len(cycle)
    cycle_idx = {u : i for i, u in enumerate(cycle)}
    minimized = False

    for i, u in enumerate(cycle):
        if minimized == True:
            break
        else:
            for v in repn[u]:
                if v in cycle_idx.keys():
                    j = cycle_idx[v]
                    if i + 1 == j:
                        continue
                    elif i == length - 1 and j == 0:
                        continue
                    elif i < j:
                        reduced_cycle = cycle[:(i + 1)] + cycle[j:]
                        minimized = True
                        break
                    else:
                        reduced_cycle = cycle[j:(i + 1)]
                        minimized = True
                        break

    if minimized == True:
        return reduced_cycle, minimized
    else:
        return cycle, minimized


def main():
    N, M = map(int, input().split())
    repn = [deque([]) for i in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        repn[a].append(b)

    cycle = detect_cycle(N, repn)
    #print('cycle detected: {}'.format(cycle))
    if cycle == []:
        print(-1)
        exit()

    minimized = True
    while minimized == True:
        cycle, minimized = minimize_cycle(cycle, repn)
        #print('cycle minimized: {}, {}'.format(minimized, cycle))

    print(len(cycle))
    for u in cycle:
        print(u)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import heapq
class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """4 5
1 2
2 3
2 4
4 1
4 3"""
        output = """3
1
2
4"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """4 5
1 2
2 3
2 4
1 4
4 3"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2"""
        output = """4
2
3
4
5"""
        self.assertIO(input, output)



def resolve():
    (N,M)=(int(i) for i in input().split())
    graph=[[[],[]] for i in range(N)]
    for i in range(M):
        (a,b)=(int(i)-1 for i in input().split())
        graph[a][0].append(b)
        graph[b][1].append(a)
    flg=True
    element=[True for i in range(N)]
    while flg:
        flg=False
        for i in range(N):
            if element[i]==False:
                continue
            if graph[i][0]==[]:
                for j in graph[i][1]:
                    graph[j][0].remove(i)
                flg=True
                graph[i][1]=[]
                element[i]=False
            if graph[i][1]==[]:
                for j in graph[i][0]:
                    graph[j][1].remove(i)
                flg=True
                graph[i][0]=[]
                element[i]=False




    def dicstra(i):

        cost=[100000 for _ in graph]
        cost[i]=0

        oya=[[] for _ in graph]
        muki = [j[0] for j in graph]

        visited=[False for j in muki]
        q=[]
        heapq.heappush(q,[0,i])
        while q:
            c,ind=heapq.heappop(q)
            visited[ind]=True
            oya[ind].append(ind)
            for j in muki[ind]:
                if (not visited[j]) and  cost[j]>cost[ind]+1:
                    cost[j]=cost[ind]+1
                    oya[j]=oya[ind][:]
                    heapq.heappush(q,[cost[j],j])
        xx=[oya[j] for j in graph[i][1]]
        xx.sort(key=lambda it: len(it))


        for j in xx[0]:
            for k in range(len(graph[j][0])):
                if k>=len(graph[j][0]):
                    break                
                x=graph[j][0][k]
                if not (x in xx[0]):
                    graph[j][0].remove(x)
                    if k>=len(graph[j][0]):
                        break
            for k in range(len(graph[j][1])):
                if k>=len(graph[j][1]):
                        break
                x=graph[j][1][k]
                if not (x in xx[0]):

                    graph[j][1].remove(x)

            if len(graph[j][1])>1:

                return j
                
        else:
            print(len(xx[0]))
            for i in xx[0]:
                print(i+1)
            return -1
    for i in range(N):
        if element[i]:
            while i>=0:
                
                i = dicstra(i)
            
            
            break
    else:
        print(-1)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import copy

n, m = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n+1)]
radj = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)
    radj[b]


def searchRoute(i):
    global adj
    nexts = deque()
    route = [i]
    visited = set()
    result = []
    for x in adj[i]:
        if x < i:
            continue
        nroute = copy.copy(route)
        nexts.append((x, nroute))
    while len(nexts) > 0:
        error = False
        found = False
        x, xroute = nexts.popleft()
        xroute.append(x)
        visited.add(x)
        for y in adj[x]:
            if y < i:
                continue
            if y == i:
                found = True
                break
            if y in visited:
                break
            yroute = copy.copy(xroute)
            nexts.append((y, yroute))
        if found:
            result = xroute
            break
    return result

heiro = []
for i in range(1, n+1):
    res = searchRoute(i)
    if len(res) > 0:
        heiro = res
        break

if len(heiro) == 0:
    print(-1)
    exit()
while True:
    visited = set()
    bp = [-1, -1]
    rt = defaultdict(int)
    for i in range(len(heiro)):
        visited.add(heiro[i])
        rt[heiro[i]] = i
        for j in adj[heiro[i]]:
            if j in visited and not (i == len(heiro) - 1 and j == heiro[0]):
                bp = [i, rt[j]]
                break
        if bp[0] != -1:
            break
    if bp[0] == -1:
        print(len(heiro))
        for i in heiro:
            print(i)
        exit()
    heiro = heiro[bp[1]:bp[0]+1]