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:
def examA():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """
        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]
    X.append([0,V,D])
    X.append([L,0,0])
    X.sort()
    V = [[]for _ in range(N+2)]
    for i in range(N+1):
        x1, v1, d1 = X[i]
        r = x1 + d1
        for j in range(i+1,N+2):
            x2, v2, d2 = X[j]
            if r<x2:
                break
            cost = (x2-x1)/v1
            V[i].append((j,cost))

    dij = Dijkstra(V, 0)
    ans = dij.dist[-1]
    if ans>=inf:
        print("impossible")
        return
    print('{:.18f}'.format(ans))
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    # 参考 https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61
    def cycle(neighbor, start, ring_size):
        stack = []
        stack.append([start])
        while (stack):
            curr_path = stack.pop()
            check = set(curr_path)
            if len(curr_path) > ring_size:
                continue
            # print curr_path
            last = curr_path[-1]
            for nei in neighbor[last]:
                if nei in check:
                    if (0 < len(curr_path) < ring_size) and (curr_path[0] == nei):
                        new_path = copy(curr_path)
                        new_path.append(nei)
                        return new_path

                new_path = copy(curr_path)
                new_path.append(nei)
                stack.append(new_path)
        return -1
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
    loop = -1
    for i in range(N):
        loop = cycle(V,i,N)
        if loop!=-1:
            break
    if loop==-1:
        print(-1)
        return
    while(True):
        next = -1
        for k in loop:
            next = cycle(V,k,len(loop)-1)
            if next != -1:
                break
        if next==-1:
            break
        loop = next

    ans = loop
    print(len(ans)-1)
    for v in ans[:len(ans)-1]:
        print(v+1)
    return

import sys,bisect,itertools,heapq,math,random
from copy import copy,deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cand1=set()
cand2=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  cand1.add(a)
  cand2.add(b)
cand=cand1&cand2
ans=-1
for i in range(1,n+1):
  if ans!=-1:
    break
  if i not in cand:
    continue
  else:
    q=collections.deque()
    q.append((i,[i]))
    checked=[0]*(n+1)
    while len(q)!=0:
      v,chain=q.popleft()
      if v==i and len(chain)!=1:
        ans=chain[:-1]
        break
      for u in g[v]:
        if u not in cand:
          continue
        elif checked[u]==0:
          checked[u]=1
          q.append((u,chain+[u]))
    cand.discard(i)
if ans==-1:
  print(ans)
else:
  print(len(ans))
  for v in ans:
    print(v)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == n - 1: print(-1)
else: print(0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
c = [[[] for i in range(n)] for j in range(n)]
ans = [-1]
for k in range(m):
  a, b = map(int, input().split())
  c[a-1][b-1] = [b]
  for i in range(n):
    if c[i][b-1] == [] and c[i][a-1] != []:
      c[i][b-1] = c[i][a-1] + [b]
      break
  if c[b-1][b-1] != []:
    ans = [len(c[b-1][b-1])] + c[b-1][b-1]
    break
[print(i) for i in ans]

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
tree = dict(zip(range(1, N+1), [[] for i in range(N)]))
for i in range(M):
  a, b = map(int, input().split())
  tree[a].append(b)


ans = []
l = 1001
d = [1]
while d:
  node = d[-1]
  if tree[node]:
    child = tree[node].pop()
    if child in ans and node in ans:
      idn = ans.index(node)
      idc = ans.index(child)
      ans = ans[:idn+1] + ans[idc:]
      l = len(ans)
    if child in d:
      idx = d.index(child)
      if len(d) - idx < l:
        ans = d[idx:]
        l = len(ans)
    else:
      d.append(child)
  else:
    d.pop()

if ans:
  print(len(ans))
  print(*ans, sep='\n')
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)


# cycleを少なくとも一つ検出する
def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    if length <= 3:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)


# cycleを少なくとも一つ検出する
def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        while graph[v_i]:
            j = graph[v_i].pop()
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)


# cycleを少なくとも一つ検出する
def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    for i in range(length):
        v_i = v[i]
        if i == length - 1:
            v_j = v[0]
        else:
            v_j = v[i + 1]

        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[v_i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    if i > idx:
                        v = v[i:idx + 1]
                    else:
                        v = v[idx:] + v[:i + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if len(graph[i]) == 1])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[v_i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    if i > idx:
                        v = v[i:idx + 1]
                    else:
                        v = v[idx:] + v[:i + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if len(graph[i]) == 1])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    if i > idx:
                        v = v[i:idx + 1]
                    else:
                        v = v[idx:] + v[:i + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if len(graph[i]) == 1])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    if i < idx:
                        v = v[i:idx + 1]
                    else:
                        v = v[idx:] + v[:i + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if len(graph[i]) == 1])
if not v:
    print(-1)
    exit()

while True:
    print(v)
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    if i < idx:
                        v = v[i:idx + 1]
                    else:
                        v = v[idx:] + v[:i + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
indegree = [0] * (N + 1)
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)
        indegree[j] += 1


def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        checked_in_this_cycle = [False] * (N + 1)
        start = original_stack.pop()
        checked_in_this_cycle[start] = True
        if checked[start]:
            continue
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if checked_in_this_cycle[i]:
                    return route
                else:
                    stack.append((i, route + [i]))
                    checked_in_this_cycle[i] = True
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if len(graph[i]) == 1])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    for i in range(len(v) - 1):
        v_i = v[i]
        v_j = v[i + 1]
        for j in graph[i]:
            if j != v_j:
                if j in v_s:
                    idx = v.index(j)
                    v = v[min(i, idx):max(i, idx) + 1]
                    break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)

for i in A_s:
    if not graph[i]:
        print(-1)
        exit()

stack = [i for i in range(1, N + 1) if len(graph[i]) == 1]
while stack:
    v = stack.pop()
    queue = deque([(v, [v])])
    while queue:
        v_1, route = queue.popleft()
        for i in graph[v_1]:
            if i in route:
                route = route[route.index(i):]
                print(len(route))
                print('\n'.join(map(str, route)))
                exit()
            else:
                queue.append((i, route + [i]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
N, M = map(int, input().split())
if M == 0:
  print(1)
  print(1)
  exit(0)
e = dd(list)
reve = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  reve[v].append(u)
vis = set()
inc = [0] * (N + 1)
def dfs(x, l):
  global vis
  global inc
  vis.add(x)
  ok = 0
  for y in reve[x]:
    if y in vis: inc[x] += 1
  if inc[x] > 1:
    inc[x] = 0
    vis.discard(x)
    return
  for y in e[x]:
    if y == l:
      ok = 1
      continue
    if y in vis:
      inc[x] = 0
      vis.discard(x)
      return
  if ok:
    print(len(vis))
    for v in vis: print(v)
    #print(vis, inc)
    exit(0)
  for y in e[x]:
    dfs(y, l)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s, s)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
if M == 0:
  print(1)
  print(1)
  exit(0)
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
vis = set()
res = []
chk = None
def check():
  global chk
  if chk != None:
    return chk
  ress = set(res)
  c = 0
  for x in res:
    for y in e[x]:
      if y in ress:
        c += 1
        if c > len(res):
          chk = None
          return
  chk = True
  return True
def dfs(x):
  global vis
  global res
  vis.add(x)
  if len(res):
    if check(): return
  for y in e[x]:
    if y in vis and len(res) == 0:
      res += sorted(vis)
      #print(res, vis)
      if check(): return
      else: res = []
    else:
      dfs(y)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s)
  #print(res, s)
if len(res) == 0:
  print(-1)
  exit(0)
print(len(res))
for r in res: print(r)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
vis = set()
res = []
chk = None
def check():
  global chk
  if chk != None:
    return chk
  ress = set(res)
  c = 0
  for x in res:
    for y in e[x]:
      if y in ress:
        c += 1
        if c > len(res):
          chk = None
          return
  chk = True
  return True
def dfs(x):
  global vis
  global res
  vis.add(x)
  if len(res):
    if check(): return
  for y in e[x]:
    if y in vis and len(res) == 0:
      res += sorted(vis)
      #print(res, vis)
      if check(): return
      else: res = []
    else:
      dfs(y)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s)
  #print(res, s)
if len(res) == 0:
  print(-1)
  exit(0)
print(len(res))
for r in res: print(r)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
vis = set()
res = []
def dfs(x):
  global vis
  global res
  vis.add(x)
  if len(res): return
  for y in e[x]:
    if len(res): return
    if y in vis:
      res += sorted(vis)
      break
    dfs(y)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s)
  #print(res, s)
if len(res) == 0:
  print(-1)
  exit(0)
print(len(res))
for r in res: print(r)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

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

seen = [False for _ in range(n)]
visited = [False for _ in range(n)]
begin = -1
hist = []

def dfs(x):
	global begin, hist
	if begin >= 0:
		return
	seen[x] = True
	hist.append(x)
	for v in adj[x]:
		if visited[v]:
			continue
		if seen[v] == True and visited[v] == False:
			begin = v
			return
		dfs(v)
		if begin >= 0:
			return
	visited[x] = True
	hist.pop()
	return

for i in range(n):
	if begin < 0:
		dfs(i)
	if begin >= 0:
		break

if begin < 0:
	print(-1)
	sys.exit()
else:
	cycle = []
	included = [False for _ in range(n)]
	included[begin] = True
	while hist and hist[-1] != begin:
		cycle.append(hist[-1])
		included[hist[-1]] = True
		hist.pop()
	cycle.append(begin)
	hist.pop()

	while True:
		meets = True
		l = len(cycle)
		ind = [-1 for _ in range(n)]
		for i in range(l):
			ind[cycle[i]] = i
		for i in range(l):
			if meets == False:
				break
			for v in adj[cycle[(i+1)%l]]:
				if included[v] == True and v != cycle[i]:
					meets = False
					new_start_id, new_end_id = ind[v], (i+1)%l
					print(new_start_id, new_end_id)
					break

		if meets:
			print(len(cycle))
			print(*[c+1 for c in cycle], sep="\n")
			break
		else:
			new_cycle = []
			included = [False for _ in range(n)]
			cur = new_end_id
			while cur != new_start_id:
				new_cycle.append(cycle[cur])
				included[cycle[cur]] = True
				cur = (cur+1)%l
			new_cycle.append(cycle[new_start_id])
			cycle = new_cycle