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:
from collections import deque
N,M = map(int,input().split())
side = [[]for i in range(N)]
bside = [[]for i in range(N)]
for i in range(M):
    a,b = map(ini,input().split())
    side[a-1].append(b-1)
    bside[b-1].append(a-1)
for i in range(N):
    node = [0]*N
    node[i] = 1 
    queue = deque([i])
    while queue != deque([]):
        q = queue.popleft()
        for j in range(side[q]):
            if j = q:
                queue = deque([])
                break
            if node[j] == 0:
                node[j] = node[q]+1
                queue.append(j)

Submission status: Runtime Error

Solution code:
import copy
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)

st=[0]*n

def func(po, li):
    global st
    st[po]=1
    for j in e[po]:
        if st[j] == 1:
            print(len(li))
            for val in li:
                print(val)
            exit
        elif st[j] == 0:
            newli=copy.copy(li)
            newli.append(j+1)
            func(j, newli)
    st[po]=2
        


for p in range(n):
    if st[p] == 0:
        func(p, [p+1])

Submission status: Runtime Error

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


new = [[i] for i in range(n)]

while len(new) > 0:
    tank = []
    for i in range(len(new)):
        el = new[i]
        if el != None:
            for go in edge[el[-1]]:
                if not go in new:
                    if el[0] in edge[go]:
                        res = el
                        res2 = go
                        break
                    tank.append(el.append(go))
    new = tank

print(len(res)+1)
for e in el:
    print(res)
print(go)

Submission status: Runtime Error

Solution code:
def scc(N, G, RG):
    # https://tjkendev.github.io/procon-library/python/graph/scc.html
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

from collections import Counter
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_rev[b].append(a)

label, group = scc(N+1, E, E_rev)
cnt = Counter(group)
Closed = [False] * (N+1)

for v, gr in enumerate(group):
    if Closed[gr]:
        continue
    Closed[gr] = True
    if cnt[gr]==1:
        continue

    path = [v]
    path_set = {v}
    while True:
        u = E[v][0]
        if u!=v:
            while u in path_set:
                path_set.remove(path.pop())
            path.append(u)
            v = u
        else:
            break
    print(path)
    exit()
print(-1)

Submission status: Runtime Error

Solution code:
import heapq
def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

def path_recovery(e,d,path):
    # 経路
    route = [e]
    # 残りの距離
    a = d[e]
    flag = False
    while a!=0:
        for i in range(len(path[e])):
            if zz <= len(route):
                flag = True
                break
            if d[path[e][i][1]]+path[e][i][0]==a:
                route.append(path[e][i][1])
                a -= path[e][i][0]
                e = path[e][i][1]
                break
        if flag:
            return 0

    route.reverse()
    return route

inf = float('inf')

n,m = map(int, input().split())
# s:始点, path[i]:[[cost,to]...] i=fromの隣接リスト
path = [[]for i in range(n)]
path2 = [[]for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    path[a-1].append([1,b-1])
    path2[b-1].append([1,a-1])

x = [[] for i in range(n)]

for i in range(n):
    d = dijkstra(i,path)
    x[i]=d

# e:終点, d[i]:始点から各頂点への最短距離, path[i]:[[cost,to]...] i=fromの隣接リスト

kouho = []
z = inf
for i in range(n):
    for j in range(i+1,n):
        if x[i][j]!=inf and x[j][i]!=inf:
            zz = z
            ans = path_recovery(j,x[i],path2)
            zz = z-len(ans)+1
            ans2 = path_recovery(i,x[j],path2)
            if ans==0 or ans2==0:
                continue
            else:
                kouho.append([len(ans)+len(ans2)-2,ans[:-1]+ans2[:-1]])
                z = min(z,kouho[-1][0])
if len(kouho)>0:
    kouho.sort()
    print(kouho[0][0])
    for i in range(len(kouho[0][1])):
        print(kouho[0][1][i]+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)


def bfs(start):
    que = deque([start])
    visited = [0] * N
    checked = [0] * N
    while que:
        n = que.pop()
        visited[n] += 1

        for to in G[n]:
            if checked[to] >= 1:
                return False

            if visited[to] and to != start:
                continue

            if to == start:
                return 1
            checked[to] += 1
            que.appendleft(to)


def dfs(start):
    stack = [[start, [start]]]
    visited = [0] * N
    while stack:
        n, checked = stack.pop()
        visited[n] = 1
        for to in G[n]:
            if visited[to] and to != start:
                continue
            if to == start:
                return checked
            stack.append([to, checked + [to]])


for start in range(N):
    x = bfs(start)

    if x is not False:
        ans = dfs(x)
        
        print(len(ans))
        for a in ans:
            print(a + 1)
        exit()

print(-1)

Submission status: Runtime Error

Solution code:
INF = float('inf')
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, From, To, cost=1):
        self.graph[From].append((To,cost))

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

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:INF)
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        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, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]




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

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g.add_edge(a,b)
    g.add_edge(a,b+N)
    g.add_edge(a+N,b)

ans = -1
for i in range(N):
    d = Dijkstra(g,i)
    if d.dist[i+N] != INF:
        path = d.shortest_path(i+N)
        path = path[:-1]
        path = [node%N for node in path]
        if len(path) == len(set(path)):
            ans = path
            break

if ans != -1:
    print(len(ans))
    for i in range(len(ans)):
        print(ans[i]+1)
else:
    print(ans)

d[i].shortest_path(i+N)

Submission status: Runtime Error

Solution code:
import heapq
def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

def path_recovery(e,d,path):
    # 経路
    route = [e]
    # 残りの距離
    a = d[e]
    flag = False
    while a!=0:
        for i in range(len(path[e])):
            if zz < len(route):
                flag = True
                break
            if d[path[e][i][1]]+path[e][i][0]==a:
                route.append(path[e][i][1])
                a -= path[e][i][0]
                e = path[e][i][1]
                break
        if flag:
            return 0

    route.reverse()
    return route

inf = float('inf')

n,m = map(int, input().split())
# s:始点, path[i]:[[cost,to]...] i=fromの隣接リスト
path = [[]for i in range(n)]
path2 = [[]for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    path[a-1].append([1,b-1])
    path2[b-1].append([1,a-1])

x = [[] for i in range(n)]

for i in range(n):
    d = dijkstra(i,path)
    x[i]=d

# e:終点, d[i]:始点から各頂点への最短距離, path[i]:[[cost,to]...] i=fromの隣接リスト

kouho = []
z = inf
for i in range(n):
    for j in range(i+1,n):
        if x[i][j]!=inf and x[j][i]!=inf:
            zz = z
            ans = path_recovery(j,x[i],path2)
            zz = z-len(ans)+1
            ans2 = path_recovery(i,x[j],path2)
            if ans==0 or ans2==0:
                continue
            else:
                kouho.append([len(ans)+len(ans2)-2,ans[:-1]+ans2[:-1]])
                z = min(z,kouho[-1][0])
if len(kouho)>0:
    kouho.sort()
    print(kouho[0][0])
    for i in range(len(kouho[0][1])):
        print(kouho[0][1][i]+1)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.check = False

def main():
    N, M = map(int, input().split())
    
    dic = {}
    for i in range(M):
        a, b = map(int, input().split())
        if a in dic:
            dic[a].append(b)
        else:
            dic[a] = [b]
    
    def dfs(now, start):
        if now in dic:
            for next_ in dic[now]:
                if next_ == start:
                    return True, [now]
                jud, l = dfs(next_, start)
                if jud:
                    return jud, l + [now]
        return False, [now]
    
    for start in dic.keys():
        jud, l = dfs(start, start)
        if jud:
            print(len(l))
            for num in l[::-1]:
                print(num)
            return
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def topological_sort(v, e_in, e_from):
    '''
    # note
    -----------------
    order: o(|v|+|e|)

    # parameters
    ------------------
    v:n(node)
    e_from: [ [ pointing nodes]]]
    e_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*v  # cnt[i] is num of pointed nodes
    q = []
    for v in range(v):
        cnt[v] = len(e_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            q.append(v)

    while q:
        del_node = q.pop()
        ret.append(del_node)
        for j in e_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                q.append(j)

    return ret


n, m = map(int, input().split())
edges = [list(map(lambda x:int(x)-1, input().split()))]
d = [[float('inf')]*n for _ in range(n)]
for a, b in edges:
    d[a][b] = 1

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

if min([min(v) for v in d]) == 0:
    assert 1 == 2

else:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
G = [set() for _ in range(V + 1)]
for _ in range(E):
    s, t = [int(_) for _ in input().split()]
    G[s].add(t)
parent = [-1] * (V + 1)
for start in range(1, V + 1):
    if parent[start]!=-1:
        continue
    stack = [start]
    while stack:
        now = stack.pop()
        if parent[now]!=-1:
            end = now
            now = parent[now]
            ans = [end]
            while now != end:
                ans += [now]
                now = parent[now]
            print(len(ans))
            print(*ans[::-1], sep='\n')
            exit()
        for ne in G[now]:
            if parent[ne]==-1:
                parent[ne] = now
                stack += [ne]
print(-1)

Submission status: Runtime Error

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

class Node:
    def __init__(self, id):
        self.id = id
        self.link = []
        self.check = False

def main():
    N, M = map(int, input().split())
    
    dic = {}
    for i in range(M):
        a, b = map(int, input().split())
        if a in dic:
            dic[a].append(b)
        else:
            dic[a] = [b]
    
    goal = {}
    
    def dfs(now, start):
        if now in goal:
            return goal[now]
        if now in dic:
            for next_ in dic[now]:
                if next_ == start:
                    return True, [now]
                jud, l = dfs(next_, start)
                if jud:
                    return jud, l + [now]
        return False, [now]
    
    for start in dic.keys():
        jud, l = dfs(start, start)
        if jud:
            print(len(l))
            for num in l[::-1]:
                print(num)
            return
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    conns = [[] for _ in range(N)]
    connn = [[] for _ in range(N)]
    for i in range(M):
        conns[A[i] - 1].append(B[i] - 1)
        connn[B[i] - 1].append(A[i] - 1)

    for i in range(N):
        conns[i].sort()

    def dfs(idx, used, current = []):
        used[idx] = True
        current.append(idx)
        ret = None
        j = -1
        #print(' =========== ')
        #print(idx, used)
        #print(conns[idx])
        k = 0
        while k < len(conns[idx]):
            nex = conns[idx][k]
            while used[conns[idx][k]]:
                j = conns[idx][k]
                k += 1
            if j >= 0:
                i = current.index(j)
                return current[i:]

            tmp = dfs(nex, used)
            if tmp:
                    ret = tmp
            k += 1
        used[idx] = False
        current.pop()
        return ret

    used = [False] * N
    ret = dfs(0, used)
    if ret:
        print(len(ret))
        for r in ret:
            print(r + 1)
    else:
        print(-1)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]" 
    B = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


parent_list = [ [] for i in range(n) ]
node_list = [ "White" for i in range(n) ]
node_list[0] = "Black"

search_list = [0]
loop_list = []

r = 0
while search_list != []:
    r += 1
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:

            if node_list[j] == "White":
                new_search_list.append(j)
                node_list[j] = "Black"
                parent_list[j] = parent_list[i] + [i]
            elif j in parent_list[i]:
                loop_list.append([i,j])
    search_list = new_search_list


if parent_list == []:
    print(-1)
else:
    p, q = loop_list[0]

    ans_list = parent_list[p] + [p]
    print(len(ans_list))
    for k in [ i+1 for i in ans_list ]:
        print(k)

Submission status: Runtime Error

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def topological_sort(graph):
    """
    :param list of (list of int) graph:
    :return:
    """
    # 入次数
    ins = [0] * len(graph)
    for vs in graph:
        for v in vs:
            ins[v] += 1

    # 入次数がゼロのやつ
    zeros = []
    for v, cnt in enumerate(ins):
        if cnt == 0:
            zeros.append(v)

    # 入次数がゼロのやつから順に追加してく
    ret = []
    while zeros:
        v = zeros.pop()
        ret.append(v)
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                zeros.append(u)

    if len(ret) == len(graph):
        # トポロジカルソートできた
        return []

    ret = []
    for i, c in enumerate(ins):
        if c > 0:
            ret.append(i)
    return ret


N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)

cycle = topological_sort(graph)
if not cycle:
    print(-1)
    exit()

candidate = [False] * (N + 1)
for v in cycle:
    candidate[v] = True


def dfs(v, seen, hist):
    cc = []
    for u in graph[v]:
        if not candidate[u]:
            continue
        if seen[u]:
            cc.append(u)
    if cc:
        return hist, cc

    for u in graph[v]:
        if not candidate[u]:
            continue
        seen[u] = True
        hist.append(u)
        ret, lasts = dfs(u, seen, hist)
        seen[u] = False
        if ret:
            return ret, lasts
        hist.pop()
    return False, []


stack = [cycle[0]]
ng = [False] * (N + 1)
while stack:
    v = stack.pop()
    if ng[v]:
        continue
    seen = [False] * (N + 1)
    seen[v] = True
    ret, lasts = dfs(v, seen, [v])
    if lasts == [v]:
        print(len(ret))
        print(*ret, sep='\n')
        exit()
    ng[v] = True
    for v in lasts:
        if not ng[v]:
            stack.append(v)

assert False

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
V = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a in V:
        V[a].append(b)
    else:
        V[a] = [b]


def fun(l):
    if l[-1] not in V:
        return
    for bb in V[l[-1]]:
        if bb in l:
            return l
        n = list(l)
        n.append(bb)
        re = fun(n)
        if re:
            return re


for a in V.keys():
    result = fun([a, ])
    if result:
        break

if not result:
    print(-1)
else:
    for r in result:
        print(r)

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def topological_sort(V, E_in, E_from):
    '''
    #Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)

    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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

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

ret = topological_sort(N, edge_in, edge_from)
if len(ret) == N:
    print(-1)
else:
    # ヘイロを見つける
    assert 1 == 2

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def topological_sort(V, E_in, E_from):
    '''
    #Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)

    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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

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

ret = topological_sort(N, edge_in, edge_from)
if len(ret) != N:
    print(-1)
else:
    # ヘイロを見つける
    assert 1 == 2

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def topological_sort(V, E_in, E_from):
    '''
    #Note
    -----------------
    Order: O(|V|+|E|)

    # parameters
    ------------------
    V:N(node)
    E_from: [ [ pointing nodes]]]
    E_in:[[pointed nodes]]

    # return
    ret: list of node(topologycal sorted)
    '''

    # count num of pointed nodes for each nodes
    ret = []

    cnt = [0]*V  # cnt[i] is num of pointed nodes
    Q = []
    for v in range(V):
        cnt[v] = len(E_in[v])
        if cnt[v] == 0:
            "cnt[v]=0 -> node v　is root(start of algorithm)"
            Q.append(v)

    while Q:
        del_node = Q.pop()
        ret.append(del_node)
        for j in E_from[del_node]:
            "delete edge from del_node to other node"
            cnt[j] -= 1
            if cnt[j] == 0:
                Q.append(j)

    return ret


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

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

ret = topological_sort(N, edge_in, edge_from)
if ret:
    print(-1)
else:
    assert 1 == 2

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
if not m:
    print(-1)
    exit()
e=[[]for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
f=[None]*n
f[0]=-1
s=[0]
while s:
    v=s.pop()
    for w in e[v]:
        if f[w]!=None:
            ans=[]
            while v!=w:
                ans+=v+1,
                if len(ans)>n:
                    print(-1)
                    exit()
                v=f[v]
            ans+=w+1,
            print(len(ans))
            print(*ans[::-1],sep='\n')
            exit()
        else:
            f[w]=v
            s+=w,
print(-1)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
e=[[]for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
f=[None]*n
f[0]=-1
s=[0]
while s:
    v=s.pop()
    for w in e[v]:
        if f[w]!=None:
            ans=[]
            while v!=w:
                ans+=v+1,
                if len(ans)>n:
                    print(-1)
                    exit()
                v=f[v]
            ans+=w+1,
            print(len(ans))
            print(*ans[::-1],sep='\n')
            exit()
        else:
            f[w]=v
            s+=w,
print(-1)

Submission status: Runtime Error

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

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

V

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]

path

# 辺を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: Runtime Error

Solution code:
vN,eN = map(int,input().split())

edges = {}
for i in range(eN):
    a,b = map(int,input().split())
    if a in edges:
        edges[a].add(b)
    else:
        edges[a] = set([b])

bad = [0]*(vN+1)

def f(x, seen):
    if bad[x]:
        return None
    if seen[x]:
        return []
    newseen = list(seen)
    newseen[x] = 1
    if x in edges:
        for i in edges[x]:
            rec = f(i, newseen)
            if rec is not None:
                rec.append(x)
                return rec
    bad[x] = 1
    return None
    

for i in range(1,vN+1):
    result = f(i, [0]*(vN+1))
    if result is not None:
        result.reverse()
        print(len(result))
        for j in result:
            print(j)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
vN,eN = map(int,input().split())

edges = {}
for i in range(eN):
    a,b = map(int,input().split())
    if a in edges:
        edges[a].add(b)
    else:
        edges[a] = set([b])

globalSeen = set()

def f(x):
    if x in globalSeen:
        return False
    if x in edges:
        for i in edges[x]:
            if i in seen:
                return True
            seen.add(i)
            if f(i):
                globalSeen.add(i)
                result.append(x)
                return True
            globalSeen.add(i)
            seen.remove(i)
    return False

for i in range(1,vN+1):
    seen = set()
    result = []
    if f(i):
        result.reverse()
        print(len(result))
        for j in result:
            print(j)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
emp = 0

def dfs(node, graph, visited, stack):
    global emp
    visited[node] = True
    stack.append(node)
    if node in graph:
        for n in graph[node]:
            if n not in stack:
                if not visited[n]:
                    dfs(n, graph, visited, stack)
            else:
                index = stack.index(n)
                ans = len(stack) - index
                if ans == emp: continue
                print(ans)
                for i in stack[index:]:
                    print(i)
                #print(n)
                exit(0)

    stack.pop(-1)


def main():
    global emp
    graph = {}
    visited = {}
    stack = []
    emp, num = (int(i) for i in input().split())  
    for i in range(num):
        n1, n2 = (int(i) for i in input().split())  
        if n1 not in graph:
            graph[n1] = [n2]
        elif n2 not in graph[n1]:
            graph[n1].append(n2)
        if n1 not in visited:
            visited[n1] = False
        if n2 not in visited:
            visited[n2] = False

    for node in list(visited.keys()):
        if not visited[node]:
            dfs(node, graph, visited, stack)

if __name__ == "__main__":
    main()
    print(-1)