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: 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
    """
    n = len(adj)
    stack = [~start, start]
    history = []
    arrived = [False] * n
    finished = [False] * n
    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)

cycle = find_cycle(adj)


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]
    print(len(cycle))
    print(*[elem+1 for elem in cycle], sep = '\n')

Submission status: Runtime Error

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
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 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: Runtime Error

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
v=[0]*N
w=[0]*N
def f(p,q):
    q.append(p+1)
    v[p]=1
    w[p]=1
    d=set()
    for n in c[p]:
        if v[n]:
            d.add(n)
    while len(d)>1:
        x=q.popleft()
        d.remove(x)
        v[x]=0
    if len(d)==1:
        print(len(q),*q,sep='\n')
        exit()
    for n in c[p]:
        if v[n]==0:
            f(n,q)
    q.pop()
    v[p]=0
for p in range(N):
    if w[p]==0:
        f(p,deque())
print(-1)

Submission status: Runtime Error

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)
v=[0]*N
w=[0]*N
def f(p,v,l):
    v[p]=1
    w[p]=1
    l.append(p+1)
    for n in c[p]:
        if v[n]:
            print(len(l),*l,sep='\n')
            exit()
        else:
            f(n,v,l)
    l.pop()
    v[p]=0
for p in range(N):
    if w[p]==0:
        f(p,v,[])
print(-1)

Submission status: Runtime Error

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[0]):]
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: Runtime Error

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=[]
    s=set()
    while stack:
        v=stack.pop()
        if v>=0:
            used[v]=True
            path.append(v)
            s.add(v)
            for nv in edge[v]:
                if not used[nv]:
                    stack.append(~v)
                    stack.append(nv)
                else:
                    if nv in s:
                        path.append(nv)
                        break
            else:
                continue
            break
        else:
            s.discard(path.pop())
    else:
        continue
    break
else:
    print(-1)
    exit()
cycle=path[path.index(path[0]):]
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: Runtime Error

Solution code:
from collections import defaultdict,deque

N,M=map(int,input().split())
A=[[0 for i in range(N+1)] for j in range(N+1)]
edges = []
for i in range(M):
  a,b=map(int,input().split())
  A[a][b]=1
  A[b][a]=-1
  edges.append((a,b))
  
newV=[]
for i in range(1,N+1):
  if max(A[i])==1 and min(A[i])==-1:newV.append(i)

G=defaultdict(list)
for i in range(M):
  a,b=edges[i][0],edges[i][1]
  if a in newV and b in newV:
    G[a].append(b)

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  now = s
  seen[now]=1
  todo.append(now)
  flag=0
  res = False
  while True:
    if len(todo)==0:break
    a = todo.popleft()
    for b in G[a]:
      if seen[b] == 1:
        res=(a,b)
        break
      elif seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
  return res,prev

res,prev=bfs(a)
if res==False:print(-1)
else:
  a,b=res
  old = a
  ans = [a,b]
  while True:
    new = prev[old]
    if new == b:break
    ans.append(new)
    old = new
  
  print(len(ans))
  for i in range(len(ans)):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)

INF = 10**18

N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    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 g.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
    #最小の閉路なら条件を満たす
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)
        res = path

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

Submission status: Runtime Error

Solution code:
# あっとこ
# ぴゅあ
from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**7)


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

K=0
def negative_circle(s, G, n):
    dist = [10**20 for i in range(n+1)]
    dist[s] = 0
    for i in range(1, n+1):
        flag = False
        for some in G:
            a, b = some[0], some[1]
            newlen = dist[a] - 1
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen

        if not flag:
            break
        if i == n:
            return True
    return False


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

have_circle = negative_circle(1, G, N)


if not have_circle:
    print(-1)
    sys.exit()

visited = [False for i in range(N + 1)]
parent = [-1 for i in range(N+1)]
circle_part = []


def dfs(node):
    visited[node] = True
    for child in graph[node]:
        if visited[child] == True:
            parent[child] = node
            circle_part.append(child)
            return
        else:
            if not circle_part:
                parent[child] = node
                dfs(child)


dfs(G[0][0])
now_node = circle_part[0]
A = deque([now_node])
while parent[now_node] != A[0]:
    now_node = parent[now_node]
    A.append(now_node)
A.reverse()
A.appendleft(A.pop())


def make_graph(G, A):
    A_set = set(A)
    graph_A = {A_node: [] for A_node in A}
    edge_A = []
    for x, y in G:
        if x in A_set and y in A_set:
            graph_A[x].append(y)
            edge_A.append((x, y))
    return graph_A, edge_A


graph_A, edge_A = make_graph(G, A)

while len(edge_A) != len(graph_A):
    # 条件を満たさない間
    P = set([(A[i-1], A[i]) for i in range(len(A))])
    S, E = 0, 0
    for pair in edge_A:
        if pair not in P:
            S, E = pair
            break
    visited = [False for i in range(N + 1)]
    circle_part = []
    dfs(E)
    A.clear()
    A = deque([S, E])
    now_node = S
    while parent[now_node] != E:
        now_node = parent[now_node]
        A.append(now_node)
    A.reverse()
    A.appendleft(A.pop())
    graph_A, edge_A = make_graph(G, A)

print(len(A))
for x in A:
    print(x)

Submission status: Runtime Error

Solution code:
# あっとこ
# ぴゅあ
from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**7)


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


def negative_circle(s, G, n):
    dist = [10**20 for i in range(n+1)]
    dist[s] = 0
    for i in range(1, n+1):
        flag = False
        for some in G:
            a, b = some[0], some[1]
            newlen = dist[a] - 1
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen
        if not flag:
            break
        if i == n:
            return True
    return False


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

have_circle = negative_circle(1, G, N)


if not have_circle:
    print(-1)
    sys.exit()

visited = [False for i in range(N + 1)]
parent = [-1 for i in range(N+1)]
circle_part = []


def dfs(node):
    visited[node] = True
    for child in graph[node]:
        if visited[child] == True:
            parent[child] = node
            circle_part.append(child)
            return
        else:
            parent[child] = node
            dfs(child)


dfs(1)
now_node = circle_part[0]
A = deque([now_node])
while parent[now_node] != A[0]:
    now_node = parent[now_node]
    A.append(now_node)
A.reverse()
A.appendleft(A.pop())


def make_graph(G, A):
    A_set = set(A)
    graph_A = {A_node: [] for A_node in A}
    edge_A = []
    for x, y in G:
        if x in A_set and y in A_set:
            graph_A[x].append(y)
            edge_A.append((x, y))
    return graph_A, edge_A


graph_A, edge_A = make_graph(G, A)

while len(edge_A) != len(graph_A):
    # 条件を満たさない間
    P = set([(A[i-1], A[i]) for i in range(len(A))])
    S, E = 0, 0
    for pair in edge_A:
        if pair not in P:
            S, E = pair
            break
    visited = [False for i in range(N + 1)]
    parent = [-1 for i in range(N+1)]
    circle_part = []
    dfs(E)
    A.clear()
    A = deque([S, E])
    now_node = S
    while parent[now_node] != E:
        now_node = parent[now_node]
        A.append(now_node)
    A.reverse()
    A.appendleft(A.pop())
    graph_A.clear()
    edge_A.clear()
    graph_A, edge_A = make_graph(G, A)

print(len(A))
for x in A:
    print(x)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        # ２重ループでO(E)
        for to_ in E[i]:
            in_deg[to_] += 1

    curr = 0
    ans = [v for v in range(N) if in_deg[v] == 0]

    while curr < len(ans):                  # O(V+E)
        v = ans[curr]
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
        curr += 1
    if len(ans) != N:
        return False, ans
    return True, ans


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

    # 入次数、出次数をカウントして、
    # 誘導部分グラフにならない場所を削っていく
    not_looped, ans = Topological_sorting(E)
    if not_looped:
        print(-1)               # DAGなら誘導部分グラフは存在していない
        return
    # 存在するなら、単に閉路を見つければ良い
    in_deg = [0]*N
    for i in range(N):
        for to in E[i]:
            in_deg[to] += 1

    # 深さ優先探索をする
    curr = 0
    cand = []
    while not cand:
        cand = [v for v in range(N) if in_deg[v] == curr]
        curr += 1
    for v in cand:
        prev = [-1]*N
        seen = [-1]*N
        seen[v] = 0
        q = [v]
        head = 0
        while q:
            node = q[head]
            head += 1
            seen[node] = 1
            for u in E[node]:
                if seen[u] == 1:
                    # ループだ
                    prev[u] = node
                    w = node
                    ans.append(node+1)
                    while node != prev[w]:
                        ans.append(prev[w]+1)
                        w = prev[w]
                    print(len(ans))
                    print("\n".join(map(str, ans)))
                    return
                if seen[u] == 0:
                    continue
                q.append(u)
                prev[u] = node
                seen[u] = 0
    print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def main():
    ans = None
    for i in range(N):
        ans = joint(i, [])
        if ans is not None:
            break
    if ans is None:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def dfs(index, visited):
    visited[index] = True
    for i in edges[index]:
        if visited.get(i):
            return [i]
        ret = dfs(i, visited)
        if ret:
            return [i] + ret
    visited[index] = False
    return None

def find_local_minimum(cycle):
    n = len(cycle)
    ind = {v: i for (i, v) in zip(range(n), cycle)}
    ret = []
    i = 0
    while True:
        ret.append(i)
        nxt = 0
        for j in [ind[v] for v in edges[cycle[i]] if v in ind]:
            if j < i:
                j += n
            nxt = max(nxt, j)
        if nxt >= n:
            ret = ret[ret.index(nxt % n):]
            break
        i += 1
        while i < nxt:
            del ind[cycle[i]]
            i += 1
    return [cycle[i % n] for i in ret]

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = dfs(start, visited)
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

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

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                if ns[u]&us-set([nu]):
                    for v in ns[u]&us-set([nu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

Submission status: Runtime Error

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

ret = [0] * (n + 1)
parent = [-1] * n
for start in range(n):
    q = [start]
    parent[start] = start
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            if parent[j] = j:
                loop = [i]
                while parent[i] != i:
                    i = parent[i]
                    loop.append(i)
                if i == start and len(ret) > len(loop):
                    ret = loop
                break
            if parent[j] == -1:
                parent[j] = i
                q.append(j)

if len(ret) > n:
    print(-1)
else:
    print(len(ret))
    for i in reversed(ret):
        print(i + 1)

Submission status: Runtime Error

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

INF = 2**62-1


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap



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

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

        if s not in prev:
            return None

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

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


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
import copy
import numpy as np
def cyclic(n, l, v):
    ans = []
    v.add(n)
    for i in  l[n]:
        if i in v:
            return True, v
    for i in l[n]:
        v2 = copy.deepcopy(v)
        t, vv = cyclic(i, l, v2)
        #v.remove(i)
        if t:
            ans.append(vv)
        if ans:
            return True, ans
    return False, v
def main():
    N, M  = map(int, input().split())
    l = [[] for _ in range(N)]
    r = []
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1].append(b-1)
    for i in range(N):
        v = set()
        t, vv = cyclic(i, l, v)
        if t:
            r.extend(np.ndarray.flatten(np.array(vv)).tolist())
    if r:
        m = 100000
        rr = None
        for i in r:
            if m > len(i):
                m = len(i)
                rr = i
        print(m)
        for i in rr:
            print(i+1)
    else:
        print(-1)
    return -1
main()

Submission status: Runtime Error

Solution code:
import copy
import numpy as np
def cyclic(n, l, v):
    ans = []
    v.add(n)
    for i in  l[n]:
        if i in v:
            return True, v
    for i in l[n]:
        v2 = copy.deepcopy(v)
        t, vv = cyclic(i, l, v2)
        #v.remove(i)
        if t:
            ans.append(vv)
        if ans:
            return True, ans
    return False, v
def main():
    N, M  = map(int, input().split())
    l = [[] for _ in range(N)]
    r = []
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1].append(b-1)
    for i in range(N):
        v = set()
        t, vv = cyclic(i, l, v)
        if t:
            r.extend(np.ndarray.flatten(np.array(vv)).tolist())
    if r:
        m = 100000
        rr = None
        for i in r:
            if m > len(i):
                m = len(i)
                rr = i
        print(m)
        for i in rr:
            print(i+1)
    print(-1)
    return -1
main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

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

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

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

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