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:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)

import sys
sys.setrecursionlimit(10**7)

def func(loop):
    sl=set(loop)
    k=len(loop)
    for i in range(k):
        v=loop[i]
        for nv in g[v]:
            if nv not in sl:continue
            if nv==loop[(i+1)%k]:continue
            j=[j for j in range(k) if loop[j]==nv][0]
            if i<j:
                ary=loop[:i+1]+loop[j:]
            else:
                ary=loop[j:i+1]
            func(ary)
    print(len(loop))
    for x in loop:
        print(x+1)
    exit()


def dfs(v,par):
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dfs(nv,par)
            par[nv]=-1
        else:
            loop=[v]
            while v!=nv:
                loop.append(par[v])
                v=par[v]
            loop.reverse()
            func(loop)

dfs(0,[-1]*n)
print(-1)

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(10**7)

def func(loop):
    sl=set(loop)
    k=len(loop)
    for i in range(k):
        v=loop[i]
        for nv in g[v]:
            if nv not in sl:continue
            if nv==loop[(i+1)%k]:continue
            j=[j for j in range(k) if loop[j]==nv][0]
            if i<j:
                ary=loop[:i+1]+loop[j:]
            else:
                ary=loop[j:i+1]
            func(ary)
    print(len(loop))
    for x in loop:
        print(x+1)
    exit()


def dfs(v,par):
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dfs(nv,par)
            par[nv]=-1
        else:
            loop=[]
            while v!=nv:
                loop.append(v)
                v=par[v]
            loop.append(nv)
            loop.reverse()
            func(loop)

dfs(0,[-1]*n)
print(-1)

"""
4 5
1 2
2 3
3 4
4 1
3 1

┌───<─────<────┐
1 -> 2 -> 3 -> 4
     └──<───<──┘

"""

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(10**7)

def dfs(v,par,loop):
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dist[nv]=dist[v]+1
            loop=dfs(nv,par,loop)
            if loop:return loop
            par[nv]=-1
        else:
            while v!=nv:
                loop.append(v)
                v=par[v]
            loop.append(nv)
    return loop
dist=[0]*n
loop=dfs(0,[-1]*n,[])
if len(loop)==0:
    print(-1)
    exit()

from collections import deque
todo=deque([loop[0]])
inf=float('inf')
seen=[inf]*n
seen[loop[0]]=0
par=[-1]*n
ans=[]
sl=set(loop)
while todo:
    v=todo.popleft()
    for nv in g[v]:
        if nv in sl:
            if seen[nv]>seen[v]+1:
                seen[nv]=seen[v]+1
                par[nv]=v
                todo.append(nv)
            else:
                while v!=nv:
                    ans.append(v)
                    v=par[v]
                ans.append(nv)
                todo=[]
                break

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

Submission status: Wrong Answer

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

import sys
sys.setrecursionlimit(10**7)

def dfs(v,par,loop,dist):
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dist[nv]=dist[v]+1
            loop=dfs(nv,par,loop,dist)
            par[nv]=-1
        else:
            l=dist[v]-dist[nv]+1
            if len(loop)==0 or len(loop)>l:
                ary=[]
                while v!=nv:
                    ary.append(v)
                    v=par[v]
                ary.append(nv)
                loop=ary
    return loop
dist=[0]*n
loop=dfs(0,[-1]*n,[],dist)
if len(loop)==0:
    print(-1)
    exit()
loop.reverse()
print(len(loop))
for x in loop:
    print(x+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
indeg = [0] * (n+1)
outdeg = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indeg[b] += 1
    outdeg[a] += 1

is_valid = [indeg[i] * outdeg[i] for i in range(n+1)]
u = n+10
ans = []
from collections import deque
for start in range(1, n+1):
    if not is_valid[start]:
        continue

    print("start: ", start, "---------")
    q = deque([start])
    visited = [False] * (n+1)
    prev = [-1] * (n+1)
    visited[start] = True

    has_ans = False
    while q:
        now = q.popleft()
        # print("now", now)
        for node in graph[now]:
            if node == start:
                # print("roop")
                prev[node] = now
                has_ans = True
                break
            if visited[node] or not is_valid[node]:
                continue
            # print("  to: ", node)
            prev[node] = now
            visited[node] = True
            q.append(node)
        if has_ans:
            break

    if not has_ans:
        continue
    cnt = 0
    tmp = []
    now = start
    for _ in range(n):
        tmp.append(now)
        cnt += 1
        now = prev[now]
        if now == start or now == -1:
            break
    if cnt < u:
        u = cnt
        ans = tmp

if ans:
    print(u)
    for t in ans:
        print(t)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if v == b and u == a:
                continue
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

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

Submission status: Wrong Answer

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if v == b and u == a:
                continue
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 < temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

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

Submission status: Wrong Answer

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if v == b and u == a:
                continue
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

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

Submission status: Wrong Answer

Solution code:
import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
m = INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if v == b and u == a:
                continue
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= m:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        m =  visit[a]+1

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

Submission status: Wrong Answer

Solution code:

from collections import deque
def resolve():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)

    shortest = N + 1
    res = []
    for s in range(N):
        dist = [-1] * N
        pre = [-1] * N
        q = deque()
        q.append(s)
        dist[s] = 0
        while q:
            v = q.popleft()
            for to in G[v]:
                if dist[to] == -1:
                    dist[to] = dist[v] + 1
                    pre[to] = v
                    q.append(to)

        for t in range(N):
            if t == s or dist[t] == -1:
                continue
            for to in G[t]:
                if to == s:  # サイクルになっている頂点
                    tmp = [s]
                    cur = t
                    while cur != s:
                        tmp.append(cur)
                        cur = pre[cur]
                        if shortest > len(tmp):
                            shortest = len(tmp)
                            res = tmp

    if shortest == N + 1:
        print(-1)
    else:
        print(len(res))
        for v in res:
            print(v + 1)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
cnt=0
while seen[f] not in path:
    f=seen[f]
    path.add(f)
    if cnt>n:print(abc)
    cnt+=1

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:exit()
    cnt+=1

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

""""
4 5
1 2
2 3
3 4
4 1
1 3

4 4
1 2
2 3
3 4
4 3
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
cnt=0
while seen[f] not in path:
    f=seen[f]
    path.add(f)
    if cnt>n:print(abc)
    cnt+=1

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:exit()
    cnt+=1

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:#閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
cnt=0
while seen[f] not in path:
    f=seen[f]
    path.add(f)
    if cnt>n:exit()
    cnt+=1

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:exit()
    cnt+=1

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

from collections import deque

def main():
	n,m=MI()
	G=[[] for _ in range(n+1)]

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

	A=[10**5]*(n+1)

	for i in range(1,n+1):
		Q=deque([[i,0]])
		D=[-1]*(n+1)
		while Q:
			#print(Q)
			now,d=Q.popleft()
			if now==i and d>0:
				A[i]=d
				break
			for nx in G[now]:
				if D[nx]==-1:
					D[nx]=d+1
					Q.append([nx,d+1])
	#print(A)

	k=min(A)
	#print(k)

	if k==10**5:
		print(-1)
		exit()

	s=A.index(k)
	#print(s)

	A=[]
	Q=deque([[s,0]])
	D=[10**5]*(n+1)

	while Q:
		now,d=Q.pop()
		if now==s and d>0:
			break
		if d==k:
			continue
		A.append(now)
		for nx in G[now]:
			if D[nx]>d+1:
				D[nx]=d+1
				Q.append([nx,d+1])
	D[s]=0

	#print(A)
	#print(D)

	print(k)
	print(*A,sep="\n")










if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        
        while not_yet:
            key = not_yet.popleft()
            
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        ans = [key+1]
                        now = key
                        while now != i:
                            ans.append(par[now]+1)
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if ans:
                break
        
    if ans:
        print(len(ans))
        for a in ans:
            print(a)
    else:
        print(-1)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    
    tree = [[] for _ in range(n)]
    edge = dict()
    for i in range(m):
        a, b = map(int, input().split())
        tree[a-1].append(b-1)
        edge[(a-1, b-1)] = i+1
    
    ans = 0
    for i in range(n):
        not_yet = deque([i])
        already = [False]*n
        dist = [0]*n
        par = [0]*n
        already[i] = True
        
        while not_yet:
            key = not_yet.popleft()
            
            for v in tree[key]:
                if already[v]:
                    
                    if v == i:
                        ans = []
                        ans.append(edge[(key, v)])
                        now = key
                        while now != i:
                            ans.append(edge[(par[now], now)])
                            now = par[now]
                        break
                    continue
                
                not_yet.append(v)
                already[v] = True
                dist[v] = dist[key] + 1
                par[v] = key
            if ans:
                break
        
    if ans:
        print(len(ans))
        for a in ans:
            print(a)
    else:
        print(-1)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  state = [-1 for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = [s]
  while q:
    flag = 0
    x = q.pop()
    if x < 0:
      state[~x] = 0
      continue
    q.append(~x)
    for y in graph[x]:
      state[x] = 1
      if state[y] == -1:
        p[y] = x
        q.append(y)
      elif state[y] == 0:
        continue
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        exit()
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  check = [0 for i in range(N)]
  for i in l:
    check[i] = 1
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if check[y]:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

def find_cycle(adj, start = 0):
    """
    有効グラフ上で、0-indexedが前提の実装。
    あれば、適当なサイクルをリストで返す。
    参考1: https://qiita.com/drken/items/a803d4fc4a727e02f7ba
    参考2: https://qiita.com/Kiri8128/items/2b0023bed9af642c751c
    """
    n = len(adj)
    stack = [~start, start]
    history = []
    arrived = [False] * n
    finished = [False] * n
    while stack:
        v = stack.pop()
        if v >= 0:
            arrived[v] = True
            history.append(v)
            for nv in adj[v]:
                if not arrived[nv]:
                    stack.append(~nv)
                    stack.append(nv)
                elif not finished[nv]: #arrived but not finished -> a cycle exists.
                    index = history.index(nv)
                    return history[index:]
        else:
            finished[~v] = True
            history.pop()
    return []

N, M = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    adj[A-1].append(B-1)

cycle = find_cycle(adj)


if not cycle:
    print(-1)
    exit()
else:
    cycle_updated = True
    while cycle_updated:
        cycle_updated = False
        cycle_index = {v:i for i, v in enumerate(cycle)}
        l = len(cycle)
        for i, v in enumerate(cycle):
            cv = cycle[i+1-l]
            for nv in adj[v]:
                if nv != cv and nv in cycle_index:
                    cycle_updated = True
                    j = cycle_index[nv]
                    if i < j:
                        cycle = cycle[:i+1] + cycle[j:]
                    else:
                        cycle = cycle[j:i+1]
                    break
            if cycle_updated:
                break
    print(len(cycle))
    print(*[elem+1 for elem in cycle], sep = '\n')

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for a,b in AB:
    c[a-1].append(b-1)
from collections import deque
import sys
sys.setrecursionlimit(10**9)
def f2(q):
    s=set(q)
    for a,b in AB:
        if a in s and b in s:
            i=q.index(b)
            if q[i-1]!=a:
                break
    if a in s and q[i-1]!=a:
        q2=deque([a,b])
        while q[(i+1)%len(q)]!=a:
            q2.append(q[(i+1)%len(q)])
            i+=1
        f2(q2)
    print(len(q),*q,sep='\n')
    exit()
v=[0]*N 
w=[0]*N
def f(p,v,q):
    v[p]=1
    w[p]=1
    q.append(p+1)
    for n in c[p]:
        if v[n]:
            f2(q)
        else:
            f(n,v,q)
    q.pop()
    v[p]=0
for p in range(N):
    if w[p]==0:
        f(p,v,deque())
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
from collections import deque
N,M = list(map(int,input().split()))

E = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a,b = a-1, b-1
  #E[a].append(b)
  E[b].append(a)
  
seen = [ False for _ in range(N)]
finished = [ False for _ in range(N)]
hist = deque()
"""
1 -> 2 -> 3 -> 4 -> 5 -> 3 のように
探索さいしょの方は捨てるべきかも。
今まで通ったことある頂点にぶち当たったらposに保存する
"""
def dfs(E, now, prev):
  seen[now] = True
  hist.append(now)
  for nxt in E[now]:
    if nxt == prev:
      continue
    if finished[nxt]:
      continue
    # detect loop
    if seen[nxt] and not finished[nxt]:
      # loopでぶつかったポイントを覚えておく
      return nxt
    
    # recursive
    ret = dfs(E, nxt, now)
    
    if ret > -1:
      return ret
  _ = hist.popleft()
  finished[now] = True
  return -1

pos = dfs(E, 0, -1);

cycle = []
while hist:
  # 逆順に取得する
  t = hist.pop()
  cycle.append(t+1)
  if t == pos:
    break
    
if cycle:
  print(len(cycle))
  for a in cycle[::]:
    print(a)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(i, c):
    global q
    q.append(i)
    x[i] = c
    while q:
        p = q.popleft()
        for j in G[p]:
            if x[j] == 0:
                x[j] = c
                q.append(j)
            elif x[j] == c:
                dfs(j, j, deque())
    return

def dfs(i, s, q):
    q.append(i)
    y[i] = 1
    for j in G[i]:
        if j == s:
            print_ans(q)
        if y[j] == 0:
            dfs(j, s, q)
            q.pop()
            y[j] = 0
    return

def print_ans(q):
    print(len(q))
    for i in q:
        print(i)
    exit()

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)
x = [0] * (n + 1)
y = [0] * (n + 1)
c = 1
q = deque()
for i in range(1, n + 1):
    if x[i] == 0:
        bfs(i, c)
    c += 1
print(-1)