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
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

def dfs(v):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            k = dfs(u)
            if k != -1:
                return k
            vis[u] = 1
        else:
            return u
    return -1

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
flg = 0
lst = list(range(N))
ans = -1
for i in range(N):
    for w in lst:
        vis = [1] * N
        s = dfs(w)
        if s != -1:
            flg = 1
            dq = deque()
            p = [-1] * N
            for v in es[s]:
                dq.append(v)
                p[v] = s
            while len(dq) > 0:
                v = dq.popleft()
                if v == s:
                    break
                for u in es[v]:
                    if p[u] == -1:
                        dq.append(u)
                        p[u] = v
            tmp = [s+1]
            v = p[v]
            while v != s:
                tmp.append(v+1)
                v = p[v]
            if ans == -1 or len(tmp) < len(ans):
                ans = tuple(tmp)
                lst = tmp[1:]
if flg:
    print(len(ans))
    print(*ans, sep = '\n')
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import copy
import math
import sys
sys.setrecursionlimit(1000000)
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

sans=[]
def func(po, li):
    global st
    st[po]=1
    for j in e[po]:
        if st[j] == 1:
            sans.append(li)
        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])

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

ind=0
mi=math.inf
for i, val in enumerate(sans):
    if mi > len(val):
        ind=i
        mi=len(val)

print(len(sans[ind]))
for val in sans[ind]:
    print(val)

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([v])
    nvs = [v]
    path = [v]
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            path.pop()
            pvs.remove(abs(v))
        else:
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
                path.append(u)
                vs.add(u)
                pvs.add(u)
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N+1):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = -1
    for u in d[v]:
        if u in pvs:
            f = True
            nloop.append(u)
            break
        if v2i[v] > v2i[u]:
            continue
        max_i = max(v2i[u], max_i)
    if f:
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Runtime Error

Solution code:
def bfs(i):
    queue = [(i,0)]
    
    while queue:
        u,d = queue.pop(0)
            
        for v in grafo[u]:
            next[u] = v
            if v == i:
                return u,d
            
            queue.append((v,d+1))
        
def bfs2(i):
    queue = [(i,0)]
    
    while queue:
        u,d = queue.pop(0)
            
        for v in grafo[u]:
            if v not in candidatos:
                continue
            next[u] = v
            if v == i:
                return u,d
            
            queue.append((v,d+1))
            
            
n,m = [int(i) for i in input().split()]

grafo = {i:[] for i in range(1, m+1)}
next = [0] * (n+1)


for _ in range(m):
    a,b = [int(i) for i in input().split()]
    grafo[a].append(b)

i=0
res = False

# achar qualquer ciclo
while not res and i < n:
    i+=1
    res = bfs(i)

if not res:
    print(-1)
    
else:
    
    final = i

    v = res[0]
    d = res[1]

    candidatos = []
    while next[i] != final:
        candidatos.append(i)
        i = next[i]

    candidatos.append(v)


    res = float('inf')
    caminho = None

    for i in candidatos:
        temp = bfs2(i)
        
        if temp[1] < res:
            res = temp[1]
            caminho = [i, next]

    i = caminho[0]
    while next[i] != caminho[0]:
        print(i)
        i = next[i]

        
    print(i)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit = 10 ** 9
N, M = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    V[a].append(b)
INF = float('inf')

def get_cycle(s):
    P = {i: 0 for i in range(1,N+1)}
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            P[v] = u
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
        if last[0]:
            return
        finished[u] = True
    
    dfs(s)
    cycle = []
    l = last[0]
    if l:
        cycle.append(l)
        l = P[l]
        while l not in cycle:
            cycle.append(l)
            l = P[l]
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

if len(ans):
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Runtime Error

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


# def dfs(u, path):
#     for v in V[u]:
#         if v in path:
#             return path
#         return dfs(v, path + [v])

# cycle = dfs(1, [])

# pass

INF = float('inf')

def get_cycle(s):
    P = {i: 0 for i in range(1,N+1)}
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            P[v] = u
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
        if last[0]:
            return
        finished[u] = True
    
    dfs(s)
    cycle = []
    l = last[0]
    if l:
        cycle.append(l)
        l = P[l]
        while l not in cycle:
            cycle.append(l)
            l = P[l]
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

if len(ans):
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Runtime Error

Solution code:

from collections import deque

n, m = (int(i) for i in input().split())
e = {}
for i in range(m):
    a, b = (int(i) for i in input().split())
    x = e.get(a-1, [])
    e[a-1] = x + [b-1]

def cycle(i, s, e):
    jj = e.get(i, [])
    for j in jj:
        if j == s:
            return [j]
        r = cycle(j, s, e)
        if r != []:
            return r + [j]
    return []


for i in range(n):
    r = cycle(i, i, e)
    if r != []:
        print(len(r))
        for p in r:
            print(p+1)
        break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  E[A - 1].append(B - 1)
V = [N] * N
R = [0] * N

def findLoop(s, v):
  V[s] = v
  G = [0] * (N + 1)
  for adj in E[s]:
    if R[adj] > 0:
      _G = [str(i + 1) for i, a in enumerate(R) if R[adj] <= a]
      if len(_G) < len(G):
        G = _G
      continue
    if V[adj] < v:
      continue
    R[adj] = R[s] + 1
    _G = findLoop(adj, v)
    if len(_G) < len(G):
      G = _G
    R[adj] = 0
  return G if len(G) <= N else [0] * (N + 1)

for v in range(N):
  if V[v] < N:
    continue
  R[v] = 1
  G = findLoop(v, v)
  if len(G) <= N:
    print(len(G))
    print('\n'.join(G))
    break
  R[v] = 0
else:
  print(-1)

Submission status: Runtime Error

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 dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = deque([(s,0)])
        pre = [None]*n
        while q:
            x,k = q.popleft()
            dx = d[(x,k)]
            if x == s and k:
                break
            nd = dx+1
            for y in v[x]:
                if y == s:
                    nk = 1
                else:
                    nk = 0
                if dist[(y,nk)] == float("inf"):
                    dist[(y,nk)] = nd
                    pre[y] = x
                    q.append((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)

    di,p,s = float("inf"),[],None
    for x in range(n):
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    if di == float("inf"):
        print(-1)
        return
    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: Runtime Error

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 dijkstra(s):
        dist = defaultdict(lambda : float("inf"))
        dist[(s,0)] = 0
        q = deque([(s,0)])
        pre = [None]*n
        while q:
            x,k = q.popleft()
            dx = d[(x,k)]
            if x == s and k:
                break
            nd = dx+1
            for y in v[x]:
                if y == s:
                    nk = 1
                else:
                    nk = 0
                if dist[(y,nk)] = float("inf"):
                    dist[(y,nk)] = nd
                    pre[y] = x
                    q.append((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)

    di,p,s = float("inf"),[],None
    for x in range(n):
        dist,pre = dijkstra(x)
        if dist[(x,1)] < di:
            di = dist[(x,1)]
            p = pre
            s = x
    if di == float("inf"):
        print(-1)
        return
    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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

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

    target = range(N)
    queue = [[-1,0]]
    visited = set()
    while queue:
        p = queue.pop()
        v = p[-1]
        if v not in visited:
            visited.add(v)
            for u in E[v]:
                if u in p:
                    target = min(target, p[p.index(u):], key=len)
                else:
                    queue.append(p+[u])
    if target == range(2*N): 
        return '-1'
    else:
        while 1:
            V = set(target)
            L = len(target)
            update = False
            l = L
            e = (target[-1], target[0])
            index = {v:i for i,v in enumerate(target)}
            for i, v in enumerate(target):
                for u in (E[v]&V)-{target[(i+1)%L]}:
                    if (i-index[u]+1)%L < l:
                        l = (i-index[u]+1)%L
                        e = (v,u)
                        target = (target*2)[index[e[1]]:index[e[1]]+l]
                        update = True
                        break
                if update:
                    break
            else:
                *cycle, = map(str, map(int(1).__add__, (target*2)[index[e[1]]:index[e[1]]+l]))
                res = '\n'.join([str(len(cycle))]+cycle)
                return str(res)

    
    

if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  E[A - 1].append(B - 1)
V = [0] * N
R = [0] * N

def findLoop(s):
  V[s] = 1
  G = [0] * (N + 1)
  for adj in E[s]:
    if R[adj] > 0:
      _G = [str(i + 1) for i, a in enumerate(R) if R[adj] <= a]
      if len(_G) < len(G):
        G = _G
      continue
    if V[adj]:
      continue
    R[adj] = R[s] + 1
    _G = findLoop(adj)
    if len(_G) < len(G):
      G = _G
    R[adj] = 0
  return G if len(G) < N else []

for v in range(N):
  if V[v] > 0:
    continue
  R[v] = 1
  G = findLoop(v)
  if G:
    print(len(G))
    print('\n'.join(G))
    break
  R[v] = 0
else:
  print(-1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    target = range(N+1)
    queue = [[-1,0]]
    visited = set()
    while queue:
        p = queue.pop()
        v = p[-1]
        if v not in visited:
            visited.add(v)
            for u in E[v]:
                if u in p:
                    target = min(target, p[p.index(u):], key=len)
                else:
                    queue.append(p+[u])
    if target == range(N+1): 
        return '-1'
    else:
        V = set(target)
        L = len(target)
        l = L
        e = target[:2]
        index = {v:i for i,v in enumerate(target)}
        for i, v in enumerate(target):
            for u in (E[v]&V)-{target[(i+1)%L]}:
                if (i-index[u]+1)%L < l:
                    l = (i-index[u]+1)%L
                    e = [v,u]
        *cycle, = map(str, map(int(1).__add__, (target*2)[index[u]:index[u]+l]))
    res = '\n'.join([str(len(cycle))]+cycle)
    return str(res)

    
    

if __name__ == '__main__':
    print(solve())

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_set = [set() for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
E_rev_set = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_set[a].add(b)
    E_rev[b].append(a)
    E_rev_set[b].add(a)

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

grooo = [set() for _ in range(N+1)]
for v, gr in enumerate(group):
    grooo[gr].add(v)

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

    #print(gr, cnt[gr])
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        #print("v=",v)
        aaa = E_set[v]&path_set
        if aaa:
            break
        if len((groo&E_set[v]))==0:
            exit()
        u = (groo&E_set[v]).pop()
        #print("u=",u)
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        #print(path)
    for i, v in enumerate(path):
        if v in aaa:
            aaa.remove(v)
            if len(aaa)==0:
                break
    ans = path[i:]
    print(len(ans))
    print("\n".join(map(str, ans)))
    exit()
print(-1)

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_set = [set() for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
E_rev_set = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_set[a].add(b)
    E_rev[b].append(a)
    E_rev_set[b].add(a)

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

grooo = [set() for _ in range(N+1)]
for v, gr in enumerate(group):
    grooo[gr].add(v)

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

    #print(gr, cnt[gr])
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        #print("v=",v)
        aaa = groo&E_set[v]&path_set
        if aaa:
            break
        u = (groo&E_set[v]).pop()
        #print("u=",u)
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        #print(path)
    for i, v in enumerate(path):
        if v in aaa:
            aaa.remove(v)
            if len(aaa)==0:
                break
    ans = path[i:]
    print(len(ans))
    print("\n".join(map(str, ans)))
    exit()
print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]
N, M = map(int,input().split())
g = [[np.inf]*(2*N) for _ in range(2*N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = 1
    g[a][b+N] = 1
    g[a+N][b] = 1

ans = np.inf
d = dijkstra(g,return_predecessors=True)

for i in range(N):
    if d[0][i][i+N] != np.inf:
        if ans != np.inf and len(ans)+1 <= d[0][i][i+N]:
            continue
        path = get_path(i,i+N,d[1])[::-1][:-1]
        path = [node%N for node in path]
        if len(path)==len(set(path)):
            if ans==np.inf or len(ans) > len(path):
                ans = path

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
def main():
    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 = [0]*n
    for i in range(n):
        new[i] = i
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        
    print(-1)

if __name__ == '__main__':
    main()

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    visited = set()
    parent = [-1 for _ in range(N)]
    depth = [-1 for _ in range(N)]
    l = float('inf')
    target = -1
    hq = []
    heappush(hq, (0,0,-1))
    while hq:
        d,v,w = heappop(hq)
        if v not in visited:
            visited.add(v)
            depth[v] = d
            parent[v] = w
            for u in E[v]:
                if u in visited:
                    if d+1-depth[u] < l:
                        l = d+1-depth[u]
                        target = (v,u)
                else:
                    heappush(hq, (d+1,u,v))
                    
    tail, head = target
    cycle = [str(tail+1)]
    while tail != head :
        tail = parent[tail]
        cycle.append(str(tail+1))

    res = '\n'.join([str(len(cycle))]+cycle[::-1])
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
k=list(map(int,input().split()))
N = k[0]
M = k[1]
c = [[] for i in range(N)]
t = 1
l = 0
for i in range(M):
    k=list(map(int,input().split()))
    c[k[0]-1].append(k[1]-1)
while(1):
    for m in range(N):
        if(len(c[m]) != 0):
            i = m
            break
        if(m == N - 1):
            l = 1
            t = 1
            break
    ans = []
    ans.append(i)
    b = i
    if(l == 1):
        break
    while(1):
        if(len(c[b]) != 0):
            
            a = c[b].pop(0)
            if(a in ans):
                t = 0
                break
            if(len(c[a]) == 0):
                continue
            ans.append(a) 
            b = a
        else:
            break
    if(t == 0):
        print(len(ans))
        for n in range(len(ans)):
            print(ans[n]+1)
        break
if(t == 1):
    print(-1)