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 sys
sys.setrecursionlimit(10**6)
from collections import deque

n,m = map(int,input().split())
G = [list() for _ in range(n+1)]
R = [list() for _ in range(n+1)]
for _ in range(m):
  u,v = map(int,input().split())
  G[u].append(v)
  R[v].append(u)

def find_cycle(visited = [1]):
  v = visited[-1]
  for x in G[v]:
    if x in visited:
      return visited[visited.index(x):]
    res = find_cycle(visited + [x])
    if len(res) > 0:
      return res
  return list()

def trash(i):
  dis = [n]*(n+1)
  dis[i] = 0
  q = deque([i])
  while q:
    v = q.popleft()
    for x in G[v]:
      if x == i: continue
      if dis[x] < dis[v] + 1:
        # print(dis,i,v,x)
        return v
      dis[x] = dis[v] + 1
      q.append(x)
  return False

for i in range(1,n+1):
  cyc = find_cycle([i])
  if cyc: break
  else: print(-1); exit(0)

while True:
  # print(cyc)
  for i in range(1,n+1):
    if i not in cyc:
      for x in G[i]:
        R[x].remove(i)
      G[i] = []
      for x in R[i]:
        G[x].remove(i)
      R[i] = []
     
  for i in cyc:
    if len(G[i]) > 1:
      st = i
      v = trash(st)
      for x in G[v]:
        R[x].remove(v)
      G[v] = []
      for x in R[v]:
        G[x].remove(v)
      R[v] = []
      # print(G)
      # print(R)
      cyc = set(find_cycle([st]))
      break
  else: break
      
print(len(cyc))
print(*cyc, sep='\n')

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[set() for _ in [0]*n]
    g2=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g2[b-1].add(a-1) for a,b in ab]

    def bfs(start,graph):
        temp=[[start,{start}]]
        while temp:
            temp2=[]
            for j,k in temp:
                for i in graph[j]:
                    if i in k:
                        return j,k
                    else:
                        temp2.append([i,k|{i}])
            temp=temp2
        return None,None

    return_set_pre=set(range(n))
    for i in range(n):
        now,return_set=bfs(i,g)
        if return_set!=None:
            break
    if return_set==None:
        print(-1)
        return 0

    while True:
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        if len(return_set)==len([1 for i in range(n) if len(g[i])==1]):
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g2)
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        if len(return_set)==len([1 for i in range(n) if len(g[i])==1]):
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g)
    print(len(return_set))
    for i in return_set:
        print(i+1)
main()

Submission status: Wrong Answer

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

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

def dfs(s,l):
    global g
    nl = l[:]
    nl.append(s)
    for sg in g[s]:
        if sg in nl:
            return [sg,nl]
        else:
            ret = dfs(sg,nl)
            if type(ret) is list:
                return ret
    return False

ret1 = dfs(0,[])
if type(ret1) is list:
    ret2 = dfs(ret1[0],[])
    res = [ret2[1][i]+1 for i in range(len(ret2[1]))]
    print(len(res))
    print("\n".join(map(str,res)))
else: print("-1")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = [0] * (n + 1)
import collections
g = collections.defaultdict(set)

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

def minCircle(s):
    f = [None] * n
    visited = set()
    q = []
    q.append(s)
    while q:
        node = q.pop()
        for nei in g[node]:
            if nei not in visited:
                f[nei] = node
                visited.add(nei)
                q.append(nei)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == n + 1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = [0] * (n + 1)
import collections
g = collections.defaultdict(set)

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

def minCircle(s):
    f = [None] * n
    visited = set()
    q = []
    q.append(s)
    while q:
        p = q.pop()
        for c in g[p]:
            if c not in visited:
                f[c] = p
                visited.add(c)
                q.append(c)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == n + 1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

#n, m = 6, 9
#g = [[1],[2],[3], [4], [0,5,1],[0,1]]
def minCircle(s):
    f = [None] * n
    d = [0]* n
    q = []
    q.append(s)
    d[s] = 0
    while q:
        p = q.pop()
        for c in g[p]:
            if not d[c]:
                f[c] = p
                d[c] = 1
                q.append(c)
        if d[s]:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

ans = [0] * (n +1)
for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == n+1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i + 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

#n, m = 6, 9
#g = [[1],[2],[3], [4], [0,5,1],[0,1]]
def minCircle(s):
    f = [None] * n
    d = [0]* n
    q = []
    q.append(s)
    d[s] = 0
    while q:
        p = q.pop()
        for c in g[p]:
            if not d[c]:
                f[c] = p
                d[c] = 1
                q.append(c)
        if d[s]:
            break
    p = f[s]
    ret = []
    while p and p!= s:
        ret.append(p)
        p = f[p]
    ret.append(s)
    return ret[::-1]

ans = []
for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and (len(t) < len(ans) or not ans):
        ans = t
if not ans:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i + 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

#n, m = 6, 9
#g = [[1],[2],[3], [4], [0,5,1],[0,1]]
def minCircle(s):
    f = [None] * n
    d = [0]* n
    q = []
    q.append(s)
    d[s] = 0
    while q:
        p = q.pop()
        for c in g[p]:
            if not d[c]:
                f[c] = p
                d[c] = 1
                q.append(c)
        if d[s]:
            break
    p = f[s]
    ret = []
    while p and p!= s:
        ret.append(p)
        p = f[p]
    ret.append(s)
    return ret[::-1]

ans = []
for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans) or not ans:
        ans = t
if not ans:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i + 1)

Submission status: Wrong Answer

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

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


def get_first_cycle(n, edges):
    seen = [-1] * n  # seen: -1: 未確認, 0: 非cycleのnode, 1: cycle候補
    for start in range(n):
        if seen[start] == 0:
            continue
        seen[start] = 1
        path = [start]
        while path:
            now = path[-1]
            if not edges[now]:
                path.pop()
                seen[now] = 0
                continue

            next_node = edges[now].pop()
            if seen[next_node] == -1:
                path.append(next_node)
                seen[next_node] = 1

            elif seen[next_node] == 1:
                idx = path.index(next_node)
                cycle = path[idx:]
                return cycle
    return False


cycle = get_first_cycle(n, edges)
if not cycle:
    print(-1)
    exit()
print(len(cycle))
for node in cycle:
    print(node+1)

Submission status: Wrong Answer

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].append(b)
vis = {}
def dfs(i):
    if i in vis:
        return vis[i]
    vis[i] = True
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    return False
for i in range(n):
    if dfs(i):
        print(3)
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    _, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return

#F
def F():
    n,m = LI()
    edg = [[] for i in range(n)]

    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)

    def dfs(i, tmp):
        for s in edg[i]:
            if check[s]:
                check[s] = 0
                tmp1 = tmp[::1] + [s]
                r = dfs(s, tmp1)
                if r:
                    return r
                check[s] = 1
            else:
                return tmp
        return False

    for i in range(n):
        check = [1] * n
        r = dfs(i, [])
        if r:
            print(len(r))
            for ri in r:
                print(ri+1)
            return
    
    print(-1)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    tmd = collections.defaultdict(list)
    for i in range(m):
        tma, tmb = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]

    ans = collections.defaultdict(list)
    for i in range(n):
        ql = [[0, i]]
        ql = collections.deque(ql)
        fq = [10 ** 10] * n
        fq[i] = 0
        ls = collections.defaultdict(list)
        while True:
            if len(ql) != 0:
                cost, tmp = ql.popleft()
                for tmv in tmd[tmp]:
                    if fq[tmv] > cost + 1:
                        ql.append([cost + 1, tmv])
                        fq[tmv] = min(fq[tmv], cost + 1)
                    if tmv == i:
                        ls[tmv] += [tmp]
            else:
                break
        for k, v in ls.items():
            for vv in v:
                ans[fq[vv]] += [[k, vv]]

    mt = collections.defaultdict(list)
    for k, v in ans.items():
        tmd = collections.defaultdict(list)
        start = -1
        for tma, tmb in v:
            tmd[tma-1] += [tmb-1]
            if start == -1:
                start = tma-1

        ql = [[0, start]]
        ql = collections.deque(ql)
        fq = collections.defaultdict(list)
        fq[start]
        while True:
            if len(ql) != 0:
                cost, tmp = ql.popleft()
                for tmv in tmd[tmp]:
                    if tmv not in fq:
                        ql.append([cost + 1, tmv])
                        fq[tmv]
                    if tmv == start:
                        mt[cost+1] += v
            else:
                break
    if len(mt) == 0:
        print(-1)
    else:
        mt = sorted(mt.items(), key=lambda x: x[0], reverse=True)
        for k, v in mt:
            al = set()
            print(k)
            for kv in v:
                al.add(kv[0] + 1)
                al.add(kv[1] + 1)
            for i in al:
                print(i)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    tmd = collections.defaultdict(list)
    for i in range(m):
        tma, tmb = list(map(int, input().rstrip('\n').split()))
        tmd[tma-1] += [tmb-1]

    ans = []
    for i in range(n):
        ql = [[0, i]]
        ql = collections.deque(ql)
        fq = [True] * n
        fq[i] = False
        ls = []
        while True:
            if len(ql) != 0:
                cost, tmp = ql.popleft()
                for tmv in tmd[tmp]:
                    if fq[tmv]:
                        ql.append([cost + 1, tmv])
                        fq[tmv] = False
                    if tmv == i and tmp not in ls:
                        ls.append(tmp)
            else:
                break
        if len(ls) == 1:
            ans.append(ls[0] + 1)
    if len(ans) == 0:
        print(-1)
    else:
        print(len(ans))
        for v in ans:
            print(v)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def dfs(N, AB):
  status = [-1] * N
  for i in range(N):
      if status[i] == 1:
          continue
      stack = [i]
      status[i] = 0
      while stack:
          print("stack:", stack)
          v = stack[-1]
          if AB[v]:
              n = AB[v].pop()
              if status[n] == -1:
                  stack.append(n)
                  status[n] = 0
              elif status[n] == 0:
                  idx = stack.index(n)
                  print("stack:", stack, "n:", n, "idx:", idx)
                  cycle = stack[idx:]
                  
                  return cycle
          else:                  
              status[v] = 1
              stack.pop()
 
  return False

def dfs_2(N, AB):
  for c in range(N):
    visited = set()
    stack = [c]
    while stack:
      curr = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return list(visited)
      else:
        # print("adding in visited:", curr)
        visited.add(curr)
        for i in AB[curr]:
          stack.append(i)
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)

# print("AB:")
# for i in AB:
#   print(i)
cycle = dfs_2(N, AB)
# print("cycle:", cycle)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Submission status: Wrong Answer

Solution code:
def dfs(N, AB):
  status = [-1] * N
  for i in range(N):
      if status[i] == 1:
          continue
      stack = [i]
      status[i] = 0
      while stack:
          print("stack:", stack)
          v = stack[-1]
          if AB[v]:
              n = AB[v].pop()
              if status[n] == -1:
                  stack.append(n)
                  status[n] = 0
              elif status[n] == 0:
                  idx = stack.index(n)
                  print("stack:", stack, "n:", n, "idx:", idx)
                  cycle = stack[idx:]
                  
                  return cycle
          else:                  
              status[v] = 1
              stack.pop()
 
  return False

def dfs_2(N, AB):
  for c in range(N):
    visited = set()
    stack = [c]
    while stack:
      curr = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return list(visited)
      else:
        # print("adding in visited:", curr)
        visited.add(curr)
        for i in AB[curr]:
          if i in visited:
            return list(visited)
          stack.append(i)
  return False

 
 
def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle
 
 
N, M = [int(i) for i in input().split()]
 
AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)

# print("AB:")
# for i in AB:
#   print(i)
cycle = dfs_2(N, AB)
# print("cycle:", cycle)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, raw_input().split())
al=[ [] for i in range(N+1) ]

for i in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)


#BFS 始点を入力で渡すと、始点に戻る閉路の距離の最小値と、その経路を返す
def bfs(start):
	d=[ float("inf") for _ in range(N+1) ]	#Start地点からの距離
	route=[ None for _ in range(N+1)]	#経路復元のため、次の頂点をセット
	q=deque()
	d[start]=0			#初期化
	q.append(start)

	ret=float("inf")
	while q:
		fro=q.popleft()
		for to in al[fro]:
			if to==start:
				alt2=d[fro]+1
				if alt2<ret:
					ret=alt2			
					route[fro]=to
			if d[to]==float("inf"):	#float("inf")なら未訪問
				alt=d[fro]+1
				if alt<d[to]:
					d[to]=alt
					route[fro]=to	#経路復元のため、次の頂点をセット
				q.append(to)
	R=[]
	R.append(start)
	next=route[start]
	while next!=start:
		R.append(next)
		try:
			next=route[next]
		except:
			return -1,[]

	return ret,R


K=float("inf")
v=[]
for i in range(1,N+1):
	kyori,keiro=bfs(i)
	if kyori==-1:
		continue	#閉路がない場合はcontinue
	elif kyori<K:
		K=kyori
		v=keiro

if K==float("inf"):
	print -1
elif K==M:
	print -1
else:
	print K
	for x in v:
		print x

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, raw_input().split())
al=[ [] for i in range(N+1) ]

for i in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)


#BFS 始点を入力で渡すと、始点に戻る閉路の距離の最小値と、その経路を返す
def bfs(start):
	d=[ float("inf") for _ in range(N+1) ]	#Start地点からの距離
	route=[ None for _ in range(N+1)]	#経路復元のため、次の頂点をセット
	q=deque()
	d[start]=0			#初期化
	q.append(start)

	ret=float("inf")
	while q:
		fro=q.popleft()
		for to in al[fro]:
			if to==start:
				alt2=d[fro]+1
				if alt2<ret:
					ret=alt2			
					route[fro]=to
			if d[to]==float("inf"):	#float("inf")なら未訪問
				alt=d[fro]+1
				if alt<d[to]:
					d[to]=alt
					route[fro]=to	#経路復元のため、次の頂点をセット
				q.append(to)
	R=[]
	R.append(start)
	next=route[start]
	while next!=start:
		R.append(next)
		try:
			next=route[next]
		except:
			return -1,[]

	return ret,R


K=float("inf")
v=[]
for i in range(1,N+1):
	kyori,keiro=bfs(i)
	if kyori==-1:
		continue	#閉路がない場合はcontinue
	elif kyori<K:
		K=kyori
		v=keiro

if K==float("inf"):
	print -1
else:
	print K
	for x in v:
		print x

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [set() for _ in range(n)]

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


def get_first_cycle(n, edges):
    seen = [-1] * n  # seen: -1: 未確認, 0: 非cycleのnode, 1: cycle候補
    for start in range(n):
        if seen[start] == 0:
            continue
        seen[start] = 1
        path = [start]
        while path:
            now = path[-1]
            if not edges[now]:
                path.pop()
                seen[now] = 0
                continue

            next_node = edges[now].pop()
            if seen[next_node] == -1:
                path.append(next_node)
                seen[next_node] = 1

            elif seen[next_node] == 1:
                idx = path.index(next_node)
                cycle = path[idx:]
                return cycle
    return False


cycle = get_first_cycle(n, edges)
if not cycle:
    print(-1)
    exit()

nodes = set(cycle)
length = len(cycle)
i = 0
while i < length:
    now = cycle[i]
    routes = edges[now]
    while routes:
        to = routes.pop()
        if to in nodes:
            update = True
            idx = cycle.index(to)
            cycle = cycle[:i+1] + cycle[idx:]
            nodes = set(cycle)
            length = len(cycle)
            break
    i += 1

print(len(cycle))
for node in cycle:
    print(node+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
data=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
lst=[]
for i in range(1,n+1):
    h=[str(i)]
    while h:
        H=[]
        for u in h:
            a=int(u[-1])
            for v in data[a]:
                if v==i:
                    lst.append(int(u))
                    break
                else:
                    H.append(u+str(v))
            else:
                continue
            break
        else:
            h=H
            continue
        break
lst.sort()
li=[]
flag=[0]*(n+1)
for u in lst:
    u=list(str(u))
    for v in u:
        if flag[int(v)]==1:
            break
    else:
        for v in u:
            flag[int(v)]=1
        li.append(u)
for u in li:
    a=int(u[0])
    que=[a]
    while h:
        H=[]
        for i in que:
            if i==a:
                break
            H+=data[i]
        else:
            h=H
            continue
        break
    for i in u:
        if i in h:
            break
    else:
        print(len(u))
        for i in u:
            print(i)
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

class Node:
  def __init__(self,i):
    self.i=i
    self.edge_to=[]
    self.edge_from=[]
    self.step_visit=-1
    self.exist=True
  def delete(self):
    if self.exist:
      self.exist=False
      for i in self.edge_from:
        tree[i].del_edge_to(self.i)
        if(len(tree[i].edge_to)==0):
          tree[i].delete()
      for i in self.edge_to:
        tree[i].del_edge_from(self.i)
        if(len(tree[i].edge_to)==0):
          tree[i].delete()
  def add_edge_from(self,i):
    self.edge_from.append(i)
  def add_edge_to(self,i):
    self.edge_to.append(i)
  def del_edge_from(self,i):
    self.edge_from.remove(i)
  def del_edge_to(self,i):
    self.edge_to.remove(i)
  def visit(self,step):
    if(self.step_visit>=0):
      return self.step_visit
    self.step_visit=step
    return -1
  def next(self):
    for i in range(len(self.edge_to)):
      if(tree[self.edge_to[i]].exist):
        return self.edge_to[i]
    return -1

n_v,n_e=map(int,input().split())
tree=[Node(i) for i in range(n_v)]
trace=[]
for i in range(n_e):
  a,b=map(int,input().split())
  a-=1
  b-=1
  tree[a].add_edge_to(b)
  tree[b].add_edge_from(a)
#input
for i in range(n_v):
  if(len(tree[i].edge_to)==0 or len(tree[i].edge_from)==0):
    tree[i].delete()
#delete unnecessary nodes
for i in range(n_v):
  if(tree[i].exist):
    trace.append(i)
    tree[i].visit(0)
    next=tree[i].next()
    break
if(len(trace)==0):
  print('-1')
  sys.exit()
while True:
  start=tree[next].visit(len(trace))
  if(start>=0 or len(trace)>n_v+1):
    if(start==-1):
      print('-1')
      sys.exit()
    break
  else:
    trace.append(next)
    next=tree[next].next()
#search loop
for i in trace:
  for j in tree[i].edge_to:
    if(j in trace):
      index=trace.index(j)
      if(index>i):
        del trace[i+1:index]
      else:
        trace=trace[index:i+1]
#making it shorter
print(len(trace)-start)
for i in range(start,len(trace)):
  print(trace[i]+1)

Submission status: Wrong Answer

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, N)
    if flag:
        break



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

Submission status: Wrong Answer

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())
V = list(range(N))
E = [[] for _ 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 = cycle_detection(V, E, 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
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')
    """
	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')
    """