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: Wrong Answer

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 = []
X = A.copy()
for _ in range(N-2):
  for m,v in itertools.product(range(len(X)),A):
    if X[m][-1] == v[0]:
      if v[1] in X[m]:
        ans.append(X[m]+[v[1]])
        break
      else:
        XX.append(X[m] + [v[1]])
  if len(XX) == 0:break
  X = XX

if ans == []:
  print(-1)
else:
  ans[0] = [len(ans[0])-1] + ans[0]
  print(*ans[0][:-1])

Submission status: Wrong Answer

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-2):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        break
      else:
        XX.append(x + [v[1]])
    X = XX

if ans == []:
  print(-1)
else:
  ans[0][0] = len(ans[0])-2
  print(*ans[0][:-1])

Submission status: Wrong Answer

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-2):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        break
      else:
        XX.append(x + [v[1]])
    X = XX

if ans == []:
  print(-1)
else:
  ans[0][0] = len(ans[0])-2
  print(*ans[0])

Submission status: Wrong Answer

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]

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

if ans == []:
  print(-1)
else:
  ans[0][0] = len(ans[0])-2
  print(*ans[0][:-1])

Submission status: Wrong Answer

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]

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

if ans == []:
  print(-1)
else:
  ans[0][0] = len(ans[0])-1
  print(*ans[0])

Submission status: Wrong Answer

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]

flg = 0
ans = []
XX = []
for _ in range(N-2):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        flg = 1
      else:
        XX.append(x + [v[1]])
    if flg == 1:break
    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: Wrong Answer

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-2):
  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: Wrong Answer

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]

for _ in range(M):
  for m,v in itertools.product(range(M),A):
    if X[m][-1] == v[0]:
      X[m] = X[m] + [v[1]]
      if v[1] in X[m][:-1]:
        n = X[m].index(v[1])
        ans = list(set(X[m][n-1:]))
        ans[0] = len(ans)-1
        print(*ans)
        import sys
        sys.exit()
print(-1)

Submission status: Wrong Answer

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]

for m,v in itertools.product(range(M),A):
  if X[m][-1] == v[0]:
    X[m] = X[m] + [v[1]]
    if v[1] in X[m][:-1]:
      n = X[m].index(v[1])
      ans = list(set(X[m][n:]))
      ans[0] = len(ans)-1
      print(*ans)
      import sys
      sys.exit()
print(-1)

Submission status: Wrong Answer

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]
  for i, v in itertools.product(range(len(X)),A):
      if X[i][-1] == v[0]:
        X[i] = X[i] + [v[1]]
        if len(X[i]) > len(set(X[i])):
          ans = list(set(X[i]))
          ans[0] = len(ans)-1
          print(*ans)
          import sys
          sys.exit()

print(-1)

Submission status: Wrong Answer

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]

Submission status: Wrong Answer

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]
  for i, v in itertools.product(range(len(X)),A):
      if X[i][-1] == v[0]:
        X[i] = X[i] + [v[1]]
        if len(X[i]) > len(set(X[i])):
          ans = list(set(X[i]))
          ans[0] = len(ans)-1
          print(ans)
          import sys
          sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        query.append((chil,newkeiro))

  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        if not str(chil) in keiro:
         newkeiro = keiro +str(chil)
         query.append((chil,newkeiro))
        if visit[parent]:
         break
  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
  else:
    print(0)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
    exit()
  else:
    query2.sort()
    for j in range(len(query2)):
      n,ans = query2[j]
      if n <= 1:
        continue
      else:
       print(len(ans))
       for i in ans:
         print(int(i)+1)
       exit()
  print(-1)
  exit()
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
    exit()
  else:
    query2.sort()
    for j in range(len(query2)):
      n,ans = query2[j]
      if n <= 2:
        continue
      else:
       print(len(ans))
       for i in ans:
         print(int(i)+1)
       exit()
  print(-1)
  exit()
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          if len(ans) >= 2:
            visit[parent] = True
            query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
    exit()
  else:
    query2.sort()
    for j in range(len(query2)):
      n,ans = query2[j]
      if n <= 2:
        continue
      else:
       print(len(ans))
       for i in ans:
         print(int(i)+1)
       exit()
  print(-1)
  exit()
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          if len(ans) >= 3:
            visit[parent] = True
            query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

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

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-1)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
#graph = coo_matrix((weights, (cols, rows)), shape=(N, N)).tocsr() #N→1
try:
    d1 = bellman_ford(graph, indices = [0], directed=True, unweighted=False)
    print(-1)
except:
    print(0)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

#sys.setrecursionlimit(10000)

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

rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-1)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()

try:
    d1 = bellman_ford(graph, indices = [N-1], directed=True, unweighted=False)
    print(-1)
except:
    print(0)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = []
X = [[0]]*M
flg = 0
for m in range(M):
  a,b = list(map(int,input().split()))
  A.append([a,b])
  X[m] = X[m] + [a] + [b]
  for v in A:
    for i in range(len(X)):
      if X[i][-1] == v[0]:
        X[i] = X[i] + [v[1]]
        if len(X[i]) > len(set(X[i])):
          ans = list(set(X[i]))
          flg = 1
          break

if flg ==0:
  ans = -1
else:
  ans[0] = len(ans)-1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

INF = float('inf')

n, m = map(int, raw_input().strip().split())

g = [[] for i in xrange(n + 1)]

for _ in xrange(m):
    u, v = map(int, raw_input().strip().split())
    g[u].append(v)

ans = INF

# run bfs from eaxch vertex to
# determine the smallest cycle containing that vertex
# TC = O(|V| * |E|)

vis = [0] * (n + 1)
dist = [0] * (n + 1)
par = [0] * (n + 1)

cycle = []

def bfs(v):
    global ans, vis, dist, cycle
    
    flag = 0 # cycle not found
    
    q = deque([v])
    vis[v] = 1

    while q:
        u = q.popleft()
        for child in g[u]:
            if (vis[child]):
                if (child == v):

                    cur = dist[u] + 1
                    if cur < ans:
                        ans = cur

                        # fill the cycle list
                        cycle = []
                        
                        cycle.append(str(u))
                        vertex = u
                        while vertex != v:                            
                            vertex = par[vertex]
                            cycle.append(str(vertex))

                    else: pass

                    # cycle found, break                    
                    flag = 1
                    break
            
            vis[child] = 1
            dist[child] = dist[u] + 1
            par[child] = u
            
            q.append(child)

        if flag: break

for v in xrange(1, n + 1):
    #bfs(v)

    if (v == n): break
    
    for i in xrange(n + 1): vis[i] = dist[i] = par[i] = 0

if (ans == INF):
    print -1
else:
    print ans
    print '\n'.join(cycle)

Submission status: Wrong Answer

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):
  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: Wrong Answer

Solution code:
from collections import deque

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

edges = [[] for _ in range(N)]
edgesR = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edgesR[to].append(fr)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    dist = [float('inf')] * N
    que = deque([(loopStart, 0)])

    while que:
        now, d = que.popleft()

        if dist[now] <= d:
            if now == loopStart:
                dist[loopStart] = d
                break
            continue
        dist[now] = d

        for to in edges[now]:
            que.append((to, d + 1))

    ans = [loopStart]
    now = loopStart
    while dist[now] > 1:
        for back in edgesR[now]:
            if dist[now] - 1 == dist[back]:
                ans.append(back)
                now = back
                break

    ans = set([a + 1 for a in ans])
    print(len(ans))
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = []
    K = len(L)
    for i, now in enumerate(L):
        for to in edges[now]:
            if i + 1 >= K or to == L[i + 1]:
                ans.append(now + 1)
                break
        else:
            break
    else:
        print(len(ans))
        print(*ans, sep='\n')
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = set([v + 1 for v in L])

    if len(ans) <= 2:
        continue

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

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    ans = set([v + 1 for v in L])
    print(len(ans))
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    ans = set([v + 1 for v in L])
    print(len(ans))
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
_=open(0);print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    if L[-1] != L[0]:
        continue

    L.pop()
    print(len(L))
    ans = [v + 1 for v in L]
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L.pop()
    while L[0] != loopStart:
        L.popleft()

    print(len(L))
    ans = [v + 1 for v in L]
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    if len(L) - 1 <= 1:
        continue

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            V.remove(L.pop())
    else:
        continue

    loopStart = L[-1]
    while L[0] != loopStart:
        L.popleft()

    print(len(L) - 1)
    ans = [v + 1 for v in L]
    print(*ans[: -1], sep='\n')
    exit()

print(-1)