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 ** 7)

def solve(G, p, ans, st, fst, arr, x):
    cnt_1 = 0
    z = -1
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
            z = nxt
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            k = arr[z]
            for v in st:
                if arr[v] >= k:
                    ans.append(v)
            return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst, arr, x+1):
            return True
        st.remove(nxt)
    return False

def main():
    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)
    ans = []
    f = False
    st = set()
    arr = [0]*(n+1)
    for i in range(1, n+1):
        arr[i] = 1
        st.add(i)
        if solve(G, i, ans, st, i, arr, 1):
            f = True
            break
        arr[i] = 0
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def solve(G, p, ans, st):
    cnt_1 = 0
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        for v in st:
            ans.append(v)
        return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st):
            return True
        st.remove(nxt)
    return False

def main():
    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)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def solve(G, p, ans, st):
    cnt = 0
    for nxt in G[p]:
        if nxt in st:
            cnt += 1
    if cnt > 1:
        return False
    elif cnt == 1:
        for v in st:
            ans.append(v)
        return True
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st):
            return True
        st.remove(nxt)
    return False

def main():
    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)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0 and prev[nv] == -1:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = []
            for _ in range(max(dist)+1):
                ans.append(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = ans
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = []
            for _ in range(max(dist)+1):
                ans.append(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = ans
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Pure
# へいろ検出　ベルマン 一発
import sys
sys.setrecursionlimit(10**7)
N, M = map(int, input().split())

graph = []
G = [[] for i in range(N+1)]
visited = [False for i in range(N+1)]
par = [-1 for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    graph.append((a, b, -1))
    G[a].append(b)


def bellman_ford(s, graph, n):
    dist = [10**20 for i in range(n+1)]
    par = [-1 for i in range(n+1)]
    dist[s] = 0
    start = 0
    for i in range(1, 2*n+1):
        flag = False
        for some in graph:
            a, b, d = some[0], some[1], some[2]
            newlen = dist[a]+d
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen
                par[b] = a
                if i == 2*n:
                    start = a
        if not flag:
            break
        if i == 2*n:
            return (start, par)
    return -1


X = bellman_ford(1, graph, N)
if X== -1:
    print(-1)


else:
    # 不閉路が存在する時
    now = X[0]
    par = X[1]
    ans = set([now])
    while par[now] not in ans:
        now = par[now]
        ans.add(now)
    K = len(ans)
    print(K)
    for x in ans:
        print(x)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
# https://atcoder.jp/contests/abc142/submissions/7764934
# ほぼまんま。


def main():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)

    # スタート地点は全て試す
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            # これまで通ってきた頂点と行き先の積集合
            s = route & E[v]
            # sが空集合(ループでない)か、行き先に始点のみが含まれる場合は継続
            # 行き先に始点以外の場所が含まれるなら、もっと良い始点の選び方がある。
            if not s and s != {start}:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
# https://atcoder.jp/contests/abc142/submissions/7764934
# ほぼまんま。


def main():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)

    # スタート地点は全て試す
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            # これまで通ってきた頂点と行き先の積集合
            s = route & E[v]
            # 行き先が複数の箇所に到達するなら
            # もっと良い始点の選び方があるのでスキップして良い
            if len(s) > 1:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1010)
from collections import *

def dfs(v):
    pos[v] = len(s)
    s.append(v)
    low = -1
    
    for nv in G[v]:
        if pos[nv]!=-1 and pos[v]-pos[nv]>1:
            low = max(low, pos[nv])
    
    if low!=-1:
        for i in range(low, pos[v]+1):
            cyc.append(s[i])
            
        return True
    
    for nv in G[v]:
        if pos[nv]==-1:
            if dfs(nv):
                return True
    
    s.pop()
    return False

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)
    
pos = [-1]*N
s = deque([])
cyc = []
dfs(0)

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

print(len(cyc))

for v in cyc:
    print(v+1)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    A=[0]*M
    B=[0]*M
    
    for i in range(M):
        A[i],B[i]=MI()
        A[i]-=1
        B[i]-=1
        adj[A[i]].append(B[i])
    
    import queue

    
    def bfs(a,b):
        #a=>bの辺をもとに，bからaの最短距離を求める
        q=queue.Queue()
        q.put((b,a,0))
        use=[0]*N
        use[b]=1
        while not(q.empty()):
            v,p,d=q.get()
            if v==a:
                return d+1
            else:
                for nv in adj[v]:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        return -1
    
    def bfs2(a,b):
        #a=>bの辺をもとに，bからaの最短距離を求める
        #経路復元も
        P=[-1]*N
        q=queue.Queue()
        q.put((b,a,0))
        use=[0]*N
        use[b]=1
        flag=0
        while not(q.empty()):
            if flag:
                break
            v,p,d=q.get()
            P[v]=p
            if v==a:
                flag=1
            else:
                for nv in adj[v]:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        L=[b]
        v=a
        while v!=b:
            L.append(v)
            v=P[v]
        return L
        
                        
                        
        

    
    ans=N+1
    aa=0
    bb=0
    for i in range(M):#全ての辺をなめる
        temp=bfs(A[i],B[i])#ここはab間の最短距離をbfsで求める
        if temp!=-1:
            if temp<ans:
                ans=temp
                aa=A[i]
                bb=B[i]

    
    if ans==N+1:
        print(-1)
    else:
        print(ans)
        """
        ans=bfs2(aa,bb)
        for i in ans:
            print(i+1)
        """
        
        

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    A=[0]*M
    B=[0]*M
    
    for i in range(M):
        A[i],B[i]=MI()
        A[i]-=1
        B[i]-=1
        adj[A[i]].append(B[i])
    
    import queue

    
    def bfs(a,b):
        #a=>bの辺をもとに，bからaの最短距離を求める
        q=queue.Queue()
        q.put((b,a,0))
        use=[0]*N
        use[b]=1
        while not(q.empty()):
            v,p,d=q.get()
            if v==a:
                return d+1
            else:
                for nv in adj[v]:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        return -1
    
    def bfs2(a,b):
        #a=>bの辺をもとに，bからaの最短距離を求める
        #経路復元も
        P=[-1]*N
        q=queue.Queue()
        q.put((b,a,0))
        use=[0]*N
        use[b]=1
        flag=0
        while not(q.empty()):
            if flag:
                break
            v,p,d=q.get()
            P[v]=p
            if v==a:
                flag=1
            else:
                for nv in adj[v]:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        L=[b]
        v=a
        while v!=b:
            L.append(v)
            v=P[v]
        return L
        
                        
                        
        

    
    ans=N+1
    aa=0
    bb=0
    for i in range(M):#全ての辺をなめる
        temp=bfs(A[i],B[i])#ここはab間の最短距離をbfsで求める
        if temp!=-1:
            if temp<ans:
                ans=temp
                aa=A[i]
                bb=B[i]

    
    if ans==N+1:
        print(-1)
    else:
        print(ans)
        ans=bfs2(aa,bb)
        for i in ans:
            print(i+1)
        
        

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    A=[0]*M
    B=[0]*M
    canuse=[1]*N#閉路が小さくなるならば，s使える頂点の数は減っていく
    
    for i in range(M):
        A[i],B[i]=MI()
        A[i]-=1
        B[i]-=1
        adj[A[i]].append(B[i])
    
    def loop(n, X, i0,p0):
        # i0が根
        ans=[]
        
        st = [(~i0,p0), (i0,~p0)]

        while st:
            #頂点 i を見る
            
            (i,p) = st.pop()
            #print(i,ans,usedf,st)
            
            #帰り際の処理，ここを入れる場合，
            if i < 0:
                ans.pop()
                continue
            
            #行きがけの処理
            if i >= 0:
                if i==p0:
                    ans.append(p0)
                    break
                
                ans.append(i)
                
            for a in X[i][::-1]:
                if a!=p and a!=~p:
                    if canuse[a]==1:
                        st.append((~a,(abs(i))))
                        st.append((a,abs(i)))
                    
        return ans

    ans=[1]*(N+1)
    la=N+1
    
    #全ての辺に対して，その辺を起点としたループ顕彰
    for i in range(M):
        if canuse[A[i]]==1 and canuse[B[i]]==1:
        
            temp=loop(N,adj,B[i],A[i])
            if temp!=[]:
                lt=len(temp)
                
                temp.sort()
                now=0
                for i in range(N):
                    if i!=temp[now]:
                        canuse[i]=0
                    else:
                        now+=1
                        if now==lt:
                            break
                        
                
                if lt<la:
                    ans=[]
                    la=lt
                    for i in range(lt):
                        ans.append(temp[i])

    
    if la==(N+1):
        print(-1)
    else:
        print(la)
        for i in ans:
            print(i+1)
        
        

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(M):
        A,B=MI()
        A-=1
        B-=1
        adj[A].append(B)
        
    usedf=[0]*N
    
    def EulerTour(n, X, i0,p0):
        # 隣接グラフXを消費しながら，親リストPを作りながら進む．
        # i0が根
        ans=[]
        
        st = [(~i0,p0), (i0,~p0)]

        while st:
            #頂点 i を見る
            
            (i,p) = st.pop()
            #print(i,ans,usedf,st)
            
            #帰り際の処理，ここを入れる場合，オイラーツアーの最後に「-1」がつくので注意
            if i < 0:
                usedf[~i]-=1
                ans.pop()
                continue
            
            #行きがけの処理
            if i >= 0:
                if usedf[i]==1:#既出のところを行きがけで発見したら
                    break
                
                usedf[i]+=1
                ans.append(i)
                
            for a in X[i][::-1]:
                if a!=p and a!=~p:
                    st.append((~a,(abs(i))))
                    st.append((a,abs(i)))
                    
        return ans

    # Euler Tour の構築
    ans=EulerTour(N,adj,0,-1)

    
    if ans==[]:
        print(-1)
    else:
        print(len(ans))
        for i in ans:
            print(i+1)
        
        

main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N + 1]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) >= n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            ans = t
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) >= n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) >= n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) == n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def main():
    ans = None
    for i in range(N):
        ans = joint(i, [])
        if ans is not None:
            break
    if ans is None:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
infi = 10 ** 10


def bfs(start):
    # res = 頂点数, サイクル最後の頂点、で持つ
    res = (infi, -1)
    dist = [-1] * (n + 1)
    par = [-1] * (n + 1)
    que = deque([])
    que.append(start)
    dist[start] = 0
    while que:
        v = que.popleft()
        for u in graph[v]:
            if dist[u] >= 0:
                continue
            dist[u] = dist[v] + 1
            par[u] = v
            que.append(u)
    for i in range(1, n + 1):
        if i == start:
            continue
        if dist[i] == -1:
            continue
        if start in graph[i]:
            if res[0] > dist[i] + 1:
                res = (dist[i] + 1, i)
    if res[0] == infi:
        return -1, []
    cycle_num = res[0]
    v = res[1]
    CYCLE = deque([])
    while v > 0:
        CYCLE.appendleft(v)
        v = par[v]

    return cycle_num, CYCLE


jisho = {}
ans = (-1, [])
cycle_num = infi
kouho_v = -1
for i in range(1, n + 1):
    temp_num, temp_cycle = bfs(i)
    print(i, temp_num, temp_cycle)
    if temp_num == -1:
        continue
    if cycle_num > temp_num:
        cycle_num = min(cycle_num, temp_num)
        kouho_v = i
        jisho[i] = temp_cycle

if kouho_v == -1:
    print(-1)
    exit()
else:
    ans_num = cycle_num
    ans_list = jisho[kouho_v]
    print(cycle_num)
    print(*ans_list, sep="\n")

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 find_loop(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = find_loop(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
    processed = set()
    i = cycle[0]
    while i not in processed:
        processed.add(i)
        for j in edges[i]:
            if j in nxt:
                k = nxt[i]
                while k != j:
                    l = nxt[k]
                    del nxt[k]
                    k = l
                nxt[i] = j
        i = nxt[i]
    start = next(iter(nxt))
    ret = [i]
    i = nxt[i]
    while i != start:
        ret.append(i)
        i = nxt[i]
    return ret

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = find_loop(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

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

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                pu = hist[(i-1)]
                if (ns[u]&us)-set([nu, pu]):
                    for v in (ns[u]&us)-set([nu, pu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

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

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                pu = hist[(i-1)]
                if ns[u]&us-set([nu, pu]):
                    for v in ns[u]&us-set([nu, pu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update or len(us)==len(hist):
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)