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 solve_f(n, g):

    for i in range(n):
        parent = [-1] * n
        queue = deque([i])
        done = False
        answer = []
        # bfs
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p]:
                if q == i:
                    r_list = []
                    r = p
                    while r != -1:
                        r_list.append(r)
                        r = parent[r]
                    # check
                    check = 1
                    for r in r_list:
                        check = max(len(set(g[r]).intersection(r_list)), check)
                    if check == 1:
                        return [len(r_list)] + [r + 1 for r in r_list]
                elif parent[q] == -1:
                    parent[q] = p
                    queue.append(q)

    return [-1]


def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        g[a - 1].append(b - 1)
    res = solve_f(n, g)
    for r in res:
        print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
Eb = [{} for _ in [0]*N]
for a,b in AB:
    E[a-1][b-1] = 1
    Eb[b-1][a-1] = 1

import heapq
def Dijkstra(N,E,start):
    d = [-1]*N
    q = [(0,start)]
    while q:
        ci,i = heapq.heappop(q)
        if d[i]!= -1:continue
        d[i] = ci
        for j,cj in E[i].items():
            if d[j]!=-1:continue
            heapq.heappush(q,(ci+cj,j))
    return d
INF = N*10
ans = [INF]
for i in range(N):
    d = Dijkstra(N,E,i)
    j = -1
    dj = INF
    for k in Eb[i]:
        if d[k]>0 and d[k]<dj:
            j = k
            dj = d[k]
    if (j!=-1) and ((dj+1) < ans[0]):
        ans = [dj+1,i+1]
        while j!=i:
            ans.append(j+1)
            dj = d[j]
            for k in Eb[j]:
                if d[k] == dj-1:
                    j = k
                    dj = d[k]
                    break

if ans[0] == INF : ans = [-1]
for out in ans:
    print(out)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
neighbours = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x:int(x)-1,input().split())
    neighbours[A].append(B)

visited = [False for i in range(N)]
def bfs(node):
    parents = [None for i in range(N)]
    stack = [node]
    while stack:
        item = stack.pop(0)
        orig = item
        for neighbour in neighbours[item]:
            if visited[neighbour]:
                if parents[neighbour] == None:
                    parents[neighbour] = item
                try:
                    graph = {neighbour}
                    while item != neighbour:
                        graph.add(item)
                        item = parents[item]
                        if item == orig and item != neighbour:
                            1/0
                    print(len(graph))
                    for item in graph:
                        print(item+1)
                    return True
                except:
                    pass
            if not visited[neighbour]:
                parents[neighbour] = item
                visited[neighbour] = True
                stack.append(neighbour)
            
for i in range(N):
    if not visited[i]:
        if bfs(i):
            break
else:
   print(-1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print((n-(n>>1))/n)
    return

#B
def B():
    n,k = LI()
    h = LI()
    ans = 0
    for i in h:
        if i >= k:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    b = [(a[i],i+1) for i in range(n)]
    b.sort()
    ans = [b[i][1] for i in range(n)]
    print(*ans)
    return

#D
def D():
    def divisor(n):
        if n < 4:
            return set([n])
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.add(i)
            i += 1
        res.add(m)
        return res
    a,b = LI()
    if min(a,b) == 1:
        print(1)
        return
    s = divisor(a)
    t = divisor(b)
    s &= t
    print(len(s))
    return

#E
def E():
    n,m = LI()
    v = []
    for i in range(m):
        a,b = LI()
        c = LI()
        s = 0
        for j in c:
            s |= 1<<(j-1)
        v.append((a,s))
    l = 1<<n
    dp = [[float("inf")]*l for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        a,c = v[i]
        for b in range(l):
            if dp[i][b] == float("inf"):
                continue
            nb = b|c
            nd = dp[i][b]+a
            if nd < dp[ni][nb]:
                dp[ni][nb] = nd
            nd = dp[i][b]
            if nd < dp[ni][b]:
                dp[ni][b] = nd
    if dp[m][-1] == float("inf"):
        print(-1)
    else:
        print(dp[m][-1])
    return

#F
def F():
    def dfs(x,d):
        for y in v[x]:
            if now[y] == True:
                z = x
                d[z] = 2
                while z != y:
                    z = pre[z]
                    d[z] = 2
                k.append(1)

            elif not d[y]:
                d[y] = 1
                pre[y] = x
                now[y] = True
                dfs(y,d)
                now[y] = False

    def dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = [(0,s,0)]
        pre = [None]*n
        while q:
            dx,x,k = heappop(q)
            if dx < dist[(x,k)]:
                continue
            if x == s and k:
                break
            for y in v[x]:
                if d[y] != 2:
                    continue
                if y == s:
                    nk = 1
                else:
                    nk = 0
                nd = dx+1
                if nd < dist[(y,nk)]:
                    dist[(y,nk)] = nd
                    pre[y] = x
                    heappush(q,(nd,y,nk))
        return (dist,pre)

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)

    d = [0]*n
    pre = [None]*n
    now = [False]*n
    k = []
    for x in range(n):
        if not d[x]:
            d[x] = 1
            now[x] = True
            dfs(x,d)
            if k:
                break
            now[x] = False
    else:
        print(-1)
        return
    di,p,s = float("inf"),[],None
    for x in range(n):
        if d[x] != 2:
            continue
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    ans = [s+1]
    x = p[s]
    while x != s:
        ans.append(x+1)
        x = p[x]
    ans.sort()
    print(len(ans))
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

AB = []
lis = [ [] for i in range(N)]

for i in range(M):

    A,B = map(int,input().split())

    A -= 1
    B -= 1

    lis[A].append(B)

q = deque([])

first = [-1] * (N+1)
first[0] = 0
first[-1] = 0

q.append( first )

end = [True] * N
end[0] = False

while len(q) > 0:

    now = q.pop()
    lasp = now[-1]
    nownum = now[lasp] 

    #print (q,now,lasp,nownum)

    for nex in lis[lasp]:

        if now[nex] == -1:
            ncopy = now.copy()
            ncopy[nex] = nownum + 1
            ncopy[-1] = nex
            end[nex] = False
            q.append(ncopy)

        else:

            flag = True

            for i in range(N):

                if now[i] >= 0:

                    for j in lis[i]:

                        if (now[j] >= now[nex] and now[j] != now[i] + 1) and not (i == lasp and j == nex):
                            flag = False
                            break

                if not flag:
                    break

            if flag:
                ans = []

                for i in range(N):
                    if now[i] >= now[nex]:
                        ans.append(i + 1)

                print (len(ans))
                for i in ans:
                    print (i)

                sys.exit()

    if len(q) == 0:
        for i in range(N):
            if end[i]:

                first = [-1] * (N+1)
                first[i] = 0
                first[-1] = i
                q.append(first)
                end[i] = False
                break
            #print (flag,nex,lasp)

print (-1)

Submission status: Accepted

Solution code:
import heapq


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    prev = [0] * len(adj)
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                prev[v_to[0]] = v_from
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist, prev


N, M = map(int, input().split())
adj = [[] for _ in range(2 * N + 1)]
flg = 1
see = [0] * (N + 1)
for _ in range(M):
    A, B = map(int, input().split())
    adj[A].append([B, 1])
    adj[A].append([B + N, 1])

ans_best = []
len_ans = N+1
for start in range(1, N+1):
    if flg == 0:
        if see[start] == 0:
            continue
    ans = []
    dist, prev = dijkstra(adj, start)
    if dist[start + N] < 10 ** 10:
        k = start + N
        while k != start:
            k = prev[k]
            ans.append(k)
        if len(ans) < len_ans:
            ans_best = ans
            len_ans = len(ans)
            if flg:
                for a in ans:
                    see[a] = 1
                flg = 0

if len_ans == N+1:
    print(-1)
else:
    print(len_ans)
    for a in ans_best:
        print(a)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    # N, M = [int(a) for a in input().split()]

    # a = []
    # # b = []
    # c = []
    #
    # for _ in range(M):
    #     aa, bb = [int(a) for a in input().split()]
    #     cc = [int(a) for a in input().split()]
    #     a.append(aa)
    #     # b.append(bb)
    #     c.append(cc)
    N, M = [int(a) for a in input().split()]

    AB = [
        [int(a) for a in input().split()]
        for _ in range(M)
    ]

    pp = [[] for _ in range(N)]
    for a, b in AB:
        pp[a - 1].append(b - 1)

    startpool = set(range(N))

    result = None

    while len(startpool) != 0:
        start = min(startpool)

        q = deque([(start, [start])])
        renketu = {start}
        while len(q) != 0:
            p, history = q.popleft()
            target = pp[p]
            for t in target:
                if t in history:
                    if result is None:
                        result = history
                    elif len(result) > len(history) - history.index(t):
                        result = history[history.index(t):]
                if t not in renketu:
                    q.append([t, history + [t]])

                renketu.add(t)
        startpool -= renketu

    if result is not None:
        print(len(result))
        for a in result:
            print(a + 1)
        return
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
X = [[] for i in range(N*3)]
for i in range(M):
    x, y = map(int, input().split())
    X[x-1].append(y-1)

INF = 1<<100
def BFS(n, E, i0=0):
    Q = deque([a for a in E[i0]])
    D = [INF] * n
    for a in E[i0]:
        D[a] = 1
    while Q:
        x = Q.popleft()
        for c in X[x]:
            if D[c] == INF:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [BFS(N, X, i)[i] for i in range(N)]
# print("Y =", Y)
mi = min(Y)
if mi == INF:
    print(-1)
else:
    for i in range(N):
        if Y[i] == mi:
            s = i
            break
    Z = [-1] * N
    for i in range(N):
        for j in X[i]:
            if Y[j] == mi:
                Z[i] = j
                break
    for i in range(N):
        s = Z[s]
    print(mi)
    for i in range(mi):
        s = Z[s]
        print(s+1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print((n-(n>>1))/n)
    return

#B
def B():
    n,k = LI()
    h = LI()
    ans = 0
    for i in h:
        if i >= k:
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = LI()
    b = [(a[i],i+1) for i in range(n)]
    b.sort()
    ans = [b[i][1] for i in range(n)]
    print(*ans)
    return

#D
def D():
    def divisor(n):
        if n < 4:
            return set([n])
        res = set([1])
        i = 2
        m = n
        while i**2 <= n:
            if m%i == 0:
                while m%i == 0:
                    m //= i
                res.add(i)
            i += 1
        res.add(m)
        return res
    a,b = LI()
    if min(a,b) == 1:
        print(1)
        return
    s = divisor(a)
    t = divisor(b)
    s &= t
    print(len(s))
    return

#E
def E():
    n,m = LI()
    v = []
    for i in range(m):
        a,b = LI()
        c = LI()
        s = 0
        for j in c:
            s |= 1<<(j-1)
        v.append((a,s))
    l = 1<<n
    dp = [[float("inf")]*l for i in range(m+1)]
    dp[0][0] = 0
    for i in range(m):
        ni = i+1
        a,c = v[i]
        for b in range(l):
            if dp[i][b] == float("inf"):
                continue
            nb = b|c
            nd = dp[i][b]+a
            if nd < dp[ni][nb]:
                dp[ni][nb] = nd
            nd = dp[i][b]
            if nd < dp[ni][b]:
                dp[ni][b] = nd
    if dp[m][-1] == float("inf"):
        print(-1)
    else:
        print(dp[m][-1])
    return

#F
def F():
    def dfs(x,d):
        for y in v[x]:
            if now[y] == True:
                z = x
                d[z] = 2
                while z != y:
                    z = pre[z]
                    d[z] = 2
                k.append(1)

            elif not d[y]:
                d[y] = 1
                pre[y] = x
                now[y] = True
                dfs(y,d)
                now[y] = False

    def dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = [(0,s,0)]
        pre = [None]*n
        while q:
            dx,x,k = heappop(q)
            if x == s and k:
                break
            for y in v[x]:
                if d[y] != 2:
                    continue
                if y == s:
                    nk = 1
                else:
                    nk = 0
                nd = dx+1
                if nd < dist[(y,nk)]:
                    dist[(y,nk)] = nd
                    pre[y] = x
                    heappush(q,(nd,y,nk))
        return (dist,pre)

    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)

    d = [0]*n
    pre = [None]*n
    now = [False]*n
    k = []
    for x in range(n):
        if not d[x]:
            d[x] = 1
            now[x] = True
            dfs(x,d)
            if k:
                break
            now[x] = False
    else:
        print(-1)
        return
    di,p,s = float("inf"),[],None
    for x in range(n):
        if d[x] != 2:
            continue
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    ans = [s+1]
    x = p[s]
    while x != s:
        ans.append(x+1)
        x = p[x]
    ans.sort()
    print(len(ans))
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
import numpy as np
from collections import defaultdict

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

if M == 0:
    print(-1)
    exit()

AB = [tuple(int(x) for x in line.split()) for line in readlines()]

A,B = zip(*AB)
graph = csr_matrix(([1]*M,(A,B)),(N+1,N+1))
_,comp = connected_components(graph,connection='strong')

size = np.bincount(comp)

if size.max() == 1:
    print(-1)
    exit()

n = np.where(size > 1)[0][0]

V = set(np.where(comp == n)[0])

graph = [[] for _ in range(N+1)]
for a,b in AB:
    if a in V and b in V:
        graph[a].append(b)

# とりあえず1つサイクルを見つける
order = defaultdict(int)
x = V.pop()
V.add(x)
q = [x]
order[x] = 1
path = [x]
flag = False
while True:
    y = graph[x][0]
    if order[y] != 0:
        path = path[order[y]-1:]
        break
    path.append(y)
    order[y] = order[x] + 1
    x = y

V = set(path)
next_v = {u:v for u,v in zip(path,path[1:])}; next_v[path[-1]] = path[0]

# 辺を1つ追加しながら、小さいサイクルを見つける
for a,b in AB:
    if not (a in V and b in V):
        continue
    # 間の頂点を削除
    x = next_v[a]
    while x != b:
        V.remove(x)
        x = next_v[x]
    next_v[a] = b

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
g = [[False] * n for _ in range(n)]
gs = [[] for _ in range(n)]
for i in range(m):
    s, t = na()
    gs[s-1].append(t-1)
    g[s-1][t-1] = True

ans = 999999
best = None
for i in range(n):
    ds = [9999999] * n
    prevs = [-1] * n
    ds[i] = 0
    q = [i]
    qp = 0
    while qp < len(q):
        cur = q[qp]
        qp += 1
        for e in gs[cur]:
            if ds[e] > ds[cur] + 1:
                ds[e] = ds[cur] + 1
                prevs[e] = cur
                q.append(e)
    for j in range(n):
        if g[j][i]:
            if ds[j] + 1 < ans:
                ans = ds[j] + 1
                best = [0] * (ds[j]+1)
                best[0] = i
                cur = j
                r = -1
                while cur != i:
                    best[r] = cur
                    r -= 1
                    cur = prevs[cur]

if not best:
    print(-1)
else:
    print(ans)
    for x in best:
        print(x+1)

Submission status: Runtime Error

Solution code:
import math

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
d = [[math.inf]*N for _ in range(N)]
for a, b in AB:
    d[a-1][b-1] = 1


def warshall_floyd(d):
    for k in range(len(d)):
        for i in range(len(d)):
            for j in range(len(d)):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])


warshall_floyd(d)
min_d = min([d[i][i] for i in range(N)])
if min_d == math.inf:
    print(-1)
else:
    ans = []
    for i in range(N):
        if d[i][i] == min_d:
            ans.append(i + 1)
    if len(ans) != min_d:
        raise ValueError('同じループが二つ')
    print(min_d)
    for i in ans:
        print(i)

Submission status: Runtime Error

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):
    if len(path)!=2:
        for v in path:
            nvs=[nv for nv in g[v] if nv in path]
            if len(nvs)==1:continue
            end=set(nvs)
            end.add(v)
            for nv in nvs:
                ary={v}
                ary.add(nv)
                nv=g[nv][0]
                while nv not in end:
                    ary.add(nv)
                    nv=[x for x in g[v] if nv in path][0]
                if nv==v:
                    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}
            while seen[v] not in path:
                v=seen[v]
                path.add(v)
            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: Runtime Error

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):
    if len(path)!=2:
        for v in path:
            nvs=[nv for nv in g[v] if nv in path]
            if len(nvs)==1:continue
            end=set(nvs)
            end.add(v)
            for nv in nvs:
                ary={v}
                ary.add(nv)
                nv=g[nv][0]
                while nv not in end:
                    ary.add(nv)
                    nv=g[nv][0]
                if nv==v:
                    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}
            while seen[v] not in path:
                v=seen[v]
                path.add(v)
            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: Runtime Error

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 dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                    seen[nv][0]=v
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                        seen[nv][0]=v
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:print(hoge)
    cnt+=1

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

Submission status: Runtime Error

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 dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:print(hoge)
    cnt+=1

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

Submission status: Runtime Error

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()
    if False in arrived:
        return arrived.index(False)
    else:
        return -1

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 True:
    cycle = find_cycle(adj)
    if cycle == -1:
        cycle = []
        break
    elif isinstance(cycle, list):
        break
    else:
        find_cycle(adj, cycle)

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