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:
N, M=map(int, input().split())
#N : 頂点　M : 辺
G  = [[] for _ in range(N)]



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





def dfs(v,goal,first = True):

    route.append(v)
    if not first:
        visit[v-1]=1        
        if v==goal:

            route.pop()
            return True

    for next in G[v-1]:
        
        if visit[next-1]:
            continue
        
        if dfs(next,goal,False) == True:
            return True
    route.pop()
    return False


flag = False

for nn in range(N):
    route = []
    visit = [0]*N
    flag = dfs(nn+1, nn+1)

    if flag:
        break



if flag:
    print(len(route))
    for i in route:
        print(i)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
#N : 頂点　M : 辺
G  = [[] for _ in range(N)]



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





def dfs(v,goal,first = True):
    print(v)
    route.append(v)
    if not first:
        visit[v-1]=1        
        if v==goal:
            print('goal')
            route.pop()
            return True

    for next in G[v-1]:
        
        if visit[next-1]:
            continue
        
        if dfs(next,goal,False) == True:
            return True
    route.pop()
    return False


flag = False

for N in range(N):
    route = []
    visit = [0]*N
    flag = dfs(N, N)
    if flag:
        break



if flag:
    print(len(route))
    for i in route:
        print(i)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
#N : 頂点　M : 辺
G  = [[] for _ in range(N)]



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





def dfs(v,goal,first = True):
    route.append(v)
    if not first:
        visit[v-1]=1        
        if v==goal:
            route.pop()
            return True

    for next in G[v-1]:
        
        if visit[next-1]:
            continue
        
        if dfs(next,goal,False) == True:
            return True
    route.pop()
    return False

route = []
visit = [0]*N


if dfs(1, 1):
    print(len(route))
    for i in route:
        print(i)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
vis = {}
def dfs(i):
    if i in vis: return vis[i]
    vis[i] = True
    vis[i] = any(map(dfs, g[i]))
    return vis[i]
print(any(map(dfs, range(n)))-1)

Submission status: Runtime Error

Solution code:
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

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

dag = False
for v in range(N):
    s, prev = BFS(v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

Submission status: Runtime Error

Solution code:
from collections import deque, defaultdict

def topological_sort(V, E):
    indeg = {v: 0 for v in V}
    for ends in E.values():
        for v in ends:
            indeg[v] += 1
    q = deque([v for v in V if indeg[v] == 0])
    top_sorted = []
    while q:
        v = q.popleft()
        top_sorted.append(v)
        for u in E[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    if len(top_sorted) == len(V): # The input digraph is acyclic.
        return top_sorted
    else: # There is a directed cycle in the digraph.
        return top_sorted

N, M = map(int, input().split())
V = list(range(1, N+1))
E1 = defaultdict(list)
E2 = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E1[a].append(b)
    E2[b].append(a)
deleted = topological_sort(V, E1)
if len(deleted) == N: print(-1)
else:
    V = list(set(V) - set(deleted))
    deleted = topological_sort(V, E2)
    V = list(set(V) - set(deleted))
    print(len(V))
    print(*V, sep='\n')

Submission status: Runtime Error

Solution code:
n,m = list(map(lambda x: int(x),input().split()))
v = [[0 for i in range(n)] for j in range(n)]

class Node:
    def __init__(self):
        self.nextNodes = []
        self.check = -1
        
Nodes = [Node() for i in range(n)]
for i in range(m):
    a,b = list(map(lambda x: int(x),input().split()))
    v[a-1][b-1] = 1
    Nodes[a-1].nextNodes.append(b-1)

def check(root,now,hist):
    if len(hist) > 0 and root == now:
        return True,hist
    if Nodes[now].check != -1:
        return False,[]
    Nodes[now].check = 1
    for i in Nodes[now].nextNodes:
        a,b = check(root,i,hist+[now])
        if a:
            return a,b
    return False,[]

for i in range(n):
    flag,ans = check(i,i,[])
    if flag:
        print(len(ans))
        for j in range(len(ans)):
            print(ans[j]+1)
        exit(0)
print(-1)

Submission status: Runtime Error

Solution code:
def bfs(graph, start):
    dist = [10000] * len(graph)
    dist[start - 1] = 0
    route = [0] * len(graph)
    queue = [start]
    visited = []
    firstFlag = False
    lastLabelBeforeGoal = 0
    while queue:
        label = queue.pop(0)
        
        if label == start and firstFlag == True:
            __logging(visited, queue)
            visited.append(label)
        firstFlag = True
        if label not in visited:
            visited.append(label)
            queue += graph.get(label, [])
            for i in queue:
                if start == i and dist[start - 1] == 0:
                    dist[i - 1] = dist[label - 1] + 1
                    route[i - 1] = label
                    minRoute = [start]
                    pointBeforeNowPoint = start
                    while dist[start - 1] != len(minRoute):
                        pointBeforeNowPoint = route[pointBeforeNowPoint - 1]
                        minRoute.append(pointBeforeNowPoint)
                    minRoute.reverse()
                    return minRoute

                else:
                    if dist[i - 1] > dist[label - 1] + 1:
                        dist[i - 1] = dist[label - 1] + 1
                        route[i - 1] = label
               
               
               
       


if __name__ == '__main__':
    
    n, m = map(int, input().split(" "))
    graph = {}

    for i in range(n):
        graph.update({i + 1 : []})

    for i in range(n):
        fromPoint, toPoint = map(int, input().split(" "))
        graph[fromPoint].append(toPoint)
   
    min = [0] * (n + 1)
    
    for i in range(n):
        ans = bfs(graph, i)
        if ans !=None and len(ans)<len(min):
            min = ans

    if len(min) < n + 1:
        print(len(min))
        for i in range(len(min)):
            print(min[i])
    else: 
        print(-1)

Submission status: Runtime Error

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

if N >= 700:
      print(aaa)
    
else:
  print("a")

Submission status: Runtime Error

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

if M >= 1500:
      print(aaa)
    
else:
  print("a")

Submission status: Runtime Error

Solution code:
import sys
[N,M] = list(map(int,input().split()))

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

for _ in range(M):
    [A,B] = list(map(int,input().split()))
    edges[A].append(B)

seen = set()


def findcycle(node):
    parent = {}
    in_stack = set()

    def dfs(u):
        seen.add(u)
        in_stack.add(u)

        for v in edges[u]:
            if v in in_stack:
                return (u,v,parent)
            else:
                parent[v] = u
                d = dfs(v)
                if None != d:
                    return d

        in_stack.remove(u)
        return None

    return dfs(node)

for n in range(1,N+1):
    if n in seen:
        continue

    cycle_ = findcycle(n)
    if cycle_ == None:
        continue
    (v,u,parent) = cycle_
    cycle = []

    cur = v
    while cur != u:
        cycle.append(cur)
        cur = parent[cur]
    cycle.append(u)
    cycle = cycle[::-1]
    cycle_s = set(cycle)
    node_to_index = {}
    for i,n in enumerate(cycle):
        node_to_index[n] = i

    def get_induced(u):
        induced = [u]
        while True:
            u = induced[-1]
            furthest_node = None
            furthest_index = -1

            furthest_back_node = None
            furthest_back_index = -1
            for v in edges[u]:
                if not v in cycle_s:
                    continue

                if node_to_index[v] < node_to_index[u] and node_to_index[v] > furthest_back_index:
                    furthest_back_index = node_to_index[v]
                    furthest_back_node = v
                if node_to_index[v] > furthest_index:
                    furthest_index = node_to_index[v]
                    furthest_node = v

            if furthest_back_node:
                return induced[induced.index(furthest_back_node):]
            induced.append(furthest_node)
        return induced

    ind = get_induced(u)
    print(len(ind))
    for nn in ind:
        print(nn)
    sys.exit(0)
print(-1)

Submission status: Runtime Error

Solution code:
# -*- Coding: utf-8 -*-
INF = 1001001001
n, m = map(int, input().split())

def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[j]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    

to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
c = [bfs(i, to) for i in range(n)]
ans = [1 for i in range(n+1)]
for i in range(n):
  if len(ans) > len(c[i]):
    ans = c[i]
if len(ans) == n + 1:
  print(-1)
else:
  print(len(ans))
  for v in ans[::-1]:
    print(v+1)

Submission status: Runtime Error

Solution code:
import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  X[m] = X[m] + [a] + [b]


ans = []
XX = []
for _ in range(N-1):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
      else:
        XX.append(x + [v[1]])
    X = XX

if ans == []:
  print(-1)
else:
  n = m+2
  for a in ans:
    if n > len(a):
      n = len(a)
      ans_min = a[:-1]
  ans_min[0] = len(ans_min)-1
  print(*ans_min)

Submission status: Runtime Error

Solution code:
import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  X[m] = X[m] + [a] + [b]


ans = []
XX = []
for _ in range(N-1):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
      else:
        XX.append(x + [v[1]])
    X = XX

if ans == []:
  print(-1)
else:
  n = m+2
  for a in ans:
    if n > len(a):
      n = len(a)
      ans_min = a[:-1]
  ans_min[0] = len(ans_min)-1
  print(ans_min)

Submission status: Runtime Error

Solution code:
import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  X[m] = X[m] + [a] + [b]

ans = []
for m,v in itertools.product(range(M),A):
    if X[m][-1] == v[0]:
      if v[1] in X[m]:
        ans.append(X[m])
      else:
        X[m] = X[m] + [v[1]]

if ans == []:
  print(-1)
else:
  n = m+2
  for a in ans:
    if n > len(a):
      ans_min = a
  ans_min[0] = len(ans_min)-1
  print(ans_min)

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)

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

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

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

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

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

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

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.buffer.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
res = []
l = []
vis = [0] * (N + 1)
globalvis = [0] * (N + 1)
def dfs(p):
  global vis
  global globalvis
  global l
  for q in e[p]:
    if vis[q] == 0:
      vis[q] = 1
      globalvis[q] = 1
      dfs(q)
      vis[q] = 0
    else:
      l = [p, q]
def finaldfs(p, g):
  global res
  for q in e[p]:
    if q == g:
      res.append(g)
      print(len(res))
      for r in res:
        print(r)
      exit(0)
    if vis[q] == 0:
      res.append(q)
      vis[q] = 1
      finaldfs(q, g)
      res.pop()
      vis[q] = 0
for i in range(1, N + 1):
  if globalvis[i] == 1: continue
  vis[i] = 1
  globalvis[i] = 1
  dfs(i)
  if len(l): break
if len(l):
  vis = [0] * (N + 1)
  #print("a", vis)
  res.append(l[1])
  finaldfs(l[1], l[0])
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:

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

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

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

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

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


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


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

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

node_set = set([node_list[0]])

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

print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 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].append(b-1)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])

t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

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())
	G[a-1].append(b-1)
deg=[0 for i in range(N)]
for i in range(N):
	for p in G[i]:
		deg[p]+=1
q=deque(i for i in range(N) if deg[i]==0)
res=[]
while q:
	u=q.popleft()
	res.append(u)
	for v in G[u]:
		deg[v]-=1
		if K[v]==0:
			q.append(v)
if len(res)==N:
	print(-1)
	exit()
X={i for i in range(N)}
for st in range(N):
	pre=[-1 for i in range(N)]
	q=deque([st])
	flag=0
	while(q):
		r=q.popleft()
		for p in G[r]:
			if pre[p]==-1:
				pre[p]=r
				q.append(p)
			if before[st]!=-1:
				Y={st}
				tmp=pre[st]
				while(tmp!=st):
					Y.add(tmp)
					tmp=before[tmp]
				if len(Y)<len(X):
					X={i for i in Y}
				flag=1
				break
		if flag:
			break
print(len(X))
for i in X:
	print(i+1)

Submission status: Runtime Error

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []

t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(0, [0])
        if len(ans) != 0:
            break

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

check = 1
while check == 1:
    check = 0
    for i in range(len(ans)-1):
        for x in e[ans[i]]:
            #print(x, ans[:i])
            if x in ans[:i]:
                ans = [] + ans[:i+1]
                check = 1
    for x in e[ans[-1]]:
        if x in ans[1:len(ans)]:
            ans = [] + ans[ans.index(x):]
            check = 1

print(len(ans))
for x in ans:
    print(x+1)

Submission status: Runtime Error

Solution code:
N,M=map(int, input().split())
vs=set()
def dfs(v,path,pvs):
    lp=l=N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        vs.add(u)
        nl, nlp = dfs(u,path+[u],pvs|{u})
        if nl < l:
            lp, l = nlp, nl
    return l,lp
d = [set() for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    d[a].add(b)

l,lp=dfs(1,[v],{v})
if l<=N:
	print("\n".join(str(x) for x in[l]+lp))
    break
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a-1, b-1))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    sys.exit()
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle and prev[b] != a:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
        pv[b] = a
print(len(circle))
for i in circle:
    print(i+1)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a-1, b-1))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    exit()
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle and prev[b] != a:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
print(len(circle))
for i in circle:
    print(i+1)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    AB.append((a, b))
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                prev[nv] = v
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    exit()
circle = set()
circle.add(v0)
pv = prev[v0]
while pv != v0:
    circle.add(pv)
    pv = prev[pv]
for a, b in AB:
    if a in circle and b in circle:
        pv = prev[b]
        while pv != a:
            circle.remove(pv)
            pv = prev[pv]
print(len(circle))
for i in circle:
    print(i+1)

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)

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

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

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
#    print(i, loop)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

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

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

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