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
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()



N, M = list(map(int, input().split()))
graph = [[] for _ in range(N)]


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

for start in range(N):
	judge = 0
	que = deque()
	que.append(start)
	parent = [-1]*N
	deep = [-1]*N
	deep[start] = 1
	while len(que) > 0:
		node = que.popleft()
		deep_next = -1
		last_list = []
		for node_next in graph[node]:
			print((start, node, node_next))
			if deep[node_next] >= 1:
				print(0)
				last_list.append(node_next)
			if deep[node_next] == 1:
				deep_next = 1
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if deep_next == 1:
			last = node
			judge = 1
			break
	if judge == 1:
		break


if judge == 0:
	print(-1)
	exit()

ans = [last]
print(last_list, last, deep)
while True:
	x = parent[ans[-1]]
	if x == -1:
		break
	elif x in last_list:
		ans.append(x)
		break
	else:
		ans.append(x)
print(len(ans))
for i in range(len(ans)):
	print(ans[i] + 1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit = 10 ** 9
N, M = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    V[a].append(b)
INF = float('inf')

def get_cycle(s):
    P = {i: 0 for i in range(1,N+1)}
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            P[v] = u
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
            if last[0]:
                return
        P[u] = 0
        finished[u] = True
    
    dfs(s)
    cycle = []
    l = last[0]
    if l:
        cycle.append(l)
        l = P[l]
        while l not in cycle:
            if not l:
                cycle = []
                break
            cycle.append(l)
            l = P[l]
        
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

if len(ans):
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit = 10 ** 9
N, M = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    V[a].append(b)
INF = float('inf')

def get_cycle(s):
    P = {i: 0 for i in range(1,N+1)}
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            P[v] = u
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
            if last[0]:
                return
        finished[u] = True
    
    dfs(s)
    cycle = []
    l = last[0]
    if l:
        cycle.append(l)
        l = P[l]
        while l not in cycle:
            if not l:
                cycle = []
                break
            cycle.append(l)
            l = P[l]
        
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

if len(ans):
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit = 10 ** 9
N, M = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    V[a].append(b)
INF = float('inf')

def get_cycle(s):
    P = {i: 0 for i in range(1,N+1)}
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            P[v] = u
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
        if last[0]:
            return
        finished[u] = True
    
    dfs(s)
    cycle = []
    l = last[0]
    if l:
        cycle.append(l)
        l = P[l]
        while l not in cycle:
            if not l:
                cycle = []
                break
            cycle.append(l)
            l = P[l]
        
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

if len(ans):
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def dfs(u):
        vis[u]=True
        for ku in to[u]:
            if vis[ku]:
                vis[u] = False
                return [u]
            res=dfs(ku)
            if res:
                vis[u] = False
                return res+[u]
        vis[u] = False
        return []


    n,m=map(int, input().split())
    to=defaultdict(list)
    for _ in range(m):
        u,v=map(int, input().split())
        to[u-1].append(v-1)
    vis=[False]*n
    for u in range(n):
        tmp=dfs(u)
        if tmp:
            print(len(tmp))
            for x in tmp:
                print(x+1)
            exit()
    print(-1)

main()

Submission status: Wrong Answer

Solution code:
# find a cycle
def find_cycle(g):
    n = len(g)
    used = [0]*n #0:not yet 1: visiting 2: visited
    for v in range(n): #各点でDFS
        if used[v] == 2: continue
        #初期化
        stack = [v]
        hist =[] #履歴
        while stack:
            v = stack[-1]
            if used[v] == 1:
                used[v] = 2 #帰りがけの状態に
                stack.pop()
                hist.pop()
                continue
            hist.append(v)
            used[v] = 1 #行きがけの状態に
            for c in g[v]:
                if used[c] == 2: continue
                elif used[c] == 1: # cを始点とするサイクル発見！
                    return hist[hist.index(c):]
                else:
                    stack.append(c)
    return None

def find_minimal_cycle(g,cycle):
    n = len(g)
    is_in_cycle = [0]*n #サイクルに使われているか
    nxt = [-1]*n #次の頂点
    
    l = len(cycle)
    for i,c in enumerate(cycle):
        is_in_cycle[c] = 1
        nxt[c] = cycle[i+1-l]

    # 極小サイクルを求める
    for v in cycle:
        if is_in_cycle[v]:
            for c in g[v]:
                if is_in_cycle[c] == 1: #もしショートカット v -> c があれば
                    v0 = nxt[v] #以下サイクルのうち v から c までを削除
                    while v0 != c: 
                        is_in_cycle[v0] = 0 
                        v0 = nxt[v0] 
                    nxt[v] = c # nxt を繋ぎ直す
    
    #極小サイクルの出力
    i = is_in_cycle.index(1)
    v = nxt[i]
    hist = [i] #履歴
    while v != i:
        hist.append(v)
        v = nxt[v]
    return hist
    
    

#########################################################

##########################################################
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

cycle = find_cycle(g)

if cycle == None: print(-1)
else:
    print(cycle)
    res = find_minimal_cycle(g,cycle)
    print(len(res))
    for i in res:
        print(i+1)

Submission status: Wrong Answer

Solution code:
# find a cycle
def find_cycle(g):
    n = len(g)
    used = [0]*n #0:not yet 1: visiting 2: visited
    for v in range(n): #各点でDFS
        if used[v] == 2: continue
        #初期化
        stack = [v]
        hist =[] #履歴
        while stack:
            v = stack[-1]
            if used[v] == 1:
                used[v] = 2 #帰りがけの状態に
                stack.pop()
                hist.pop()
                continue
            hist.append(v)
            used[v] = 1 #行きがけの状態に
            for c in g[v]:
                if used[c] == 2: continue
                elif used[c] == 1: # cを始点とするサイクル発見！
                    return hist[hist.index(c):]
                else:
                    stack.append(c)
    return None

def find_minimal_cycle(g,cycle):
    n = len(g)

    is_in_cycle = [0]*n #サイクルに使われているか
    nxt = [-1]*n #次の数
    
    l = len(cycle)
    for i,c in enumerate(cycle):
        is_in_cycle[c] = 1
        nxt[c] = cycle[i+1-l]

    v = root = cycle[0] # cycle[0]を含む極小サイクルを求める
    hist = [v] #履歴
    for _ in range(n):
        nv = -1 #vの次の点
        for c in g[v]:
            if c == root: #始点に帰ってきた
                nxt[v] = root
                return hist                
            elif is_in_cycle[c] == 1: #もしショートカット v -> c があれば
                nv = c # 次の点候補として一旦 c とする
                v0 = nxt[v] #以下サイクルのうち v から c までを削除
                while v0 != c: 
                    is_in_cycle[v0] = 0 
                    v0 = nxt[v0] 
        v = nv
        hist.append(v)


#########################################################

##########################################################
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

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

cycle = find_cycle(g)

if cycle == None: print(-1)
else:
    res = find_minimal_cycle(g,cycle)
    print(len(res))
    for i in res:
        print(i+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

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

    target = range(2*N)
    queue = [[-1,0]]
    visited = set()
    while queue:
        p = queue.pop()
        v = p[-1]
        if v not in visited:
            visited.add(v)
            for u in E[v]:
                if u in p:
                    target = min(target, p[p.index(u):], key=len)
                else:
                    queue.append(p+[u])
    if target == range(2*N): 
        return '-1'
    else:
        while 1:
            V = set(target)
            L = len(target)
            update = False
            l = L
            e = (target[-1], target[0])
            index = {v:i for i,v in enumerate(target)}
            for i, v in enumerate(target):
                for u in (E[v]&V)-{target[(i+1)%L]}:
                    if (i-index[u]+1)%L < l:
                        l = (i-index[u]+1)%L
                        e = (v,u)
                        target = (target*2)[index[e[1]]:index[e[1]]+l]
                        update = True
                        break
                if update:
                    break
            else:
                *cycle, = map(str, map(int(1).__add__, (target*2)[index[e[1]]:index[e[1]]+l]))
                res = '\n'.join([str(len(cycle))]+cycle)
                return str(res)

    
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    target = range(2*N)
    queue = [[-1,0]]
    visited = set()
    while queue:
        p = queue.pop()
        v = p[-1]
        if v not in visited:
            visited.add(v)
            for u in E[v]:
                if u in p:
                    target = min(target, p[p.index(u):], key=len)
                else:
                    queue.append(p+[u])
    if target == range(2*N): 
        return '-1'
    else:
        V = set(target)
        L = len(target)
        l = L
        e = target[:2]
        index = {v:i for i,v in enumerate(target)}
        for i, v in enumerate(target):
            for u in (E[v]&V)-{target[(i+1)%L]}:
                if (i-index[u]+1)%L < l:
                    l = (i-index[u]+1)%L
                    e = [v,u]
        *cycle, = map(str, map(int(1).__add__, (target*2)[index[e[1]]:index[e[1]]+l]))
    res = '\n'.join([str(len(cycle))]+cycle)
    return str(res)

    
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    target = range(N+1)
    queue = [[-1,0]]
    visited = set()
    while queue:
        p = queue.pop()
        v = p[-1]
        if v not in visited:
            visited.add(v)
            for u in E[v]:
                if u in p:
                    target = min(target, p[p.index(u):], key=len)
                else:
                    queue.append(p+[u])
    if target == range(N+1): 
        return '-1'
    else:
        V = set(target)
        L = len(target)
        l = L
        e = target[:2]
        index = {v:i for i,v in enumerate(target)}
        for i, v in enumerate(target):
            for u in (E[v]&V)-{target[(i+1)%L]}:
                if (i-index[u]+1)%L < l:
                    l = (i-index[u]+1)%L
                    e = [v,u]
        *cycle, = map(str, map(int(1).__add__, (target*2)[index[e[1]]:index[e[1]]+l]))
    res = '\n'.join([str(len(cycle))]+cycle)
    return str(res)

    
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    V_ = set()
    V = set(range(N))
    target = range(N+1)
    queue = [[-1,min(V)]]
    while V_ !=  V:
        visited = set()
        while queue:
            p = queue.pop()
            v = p[-1]
            if v not in visited:
                visited.add(v)
                for u in E[v]&V:
                    if u in p:
                        target = min(target, p[p.index(u):], key=len)
                    else:
                        queue.append(p+[u])
        if target == range(N+1): 
            return '-1'
        else:
            V_ = V
            V = set(target)
            target_ = target+target[0:1]
            for i, v in enumerate(target):
                if (E[v]&V)-set(target_[i:i+2]):
                    queue = [[-1,v]]
                    break
            else:
                cycle = [str(v+1) for v in target]
                res = '\n'.join([str(len(cycle))]+cycle)
                return str(res)

    
    

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
def scc(N, G, RG):
    # https://tjkendev.github.io/procon-library/python/graph/scc.html
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

from collections import Counter
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
E_set = [set() for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
E_rev_set = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_set[a].add(b)
    E_rev[b].append(a)
    E_rev_set[b].add(a)

label, group = scc(N+1, E, E_rev)
cnt = Counter(group)
Closed = [False] * (N+1)

grooo = [set() for _ in range(N+1)]
for v, gr in enumerate(group):
    grooo[gr].add(v)

for v, gr in zip(range(N, 0, -1), group[::-1]):
    if Closed[gr]:
        continue
    Closed[gr] = True
    if cnt[gr]==1:
        continue

    #print(gr, cnt[gr])
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        #print("v=",v)
        aaa = E_set[v]&path_set
        if aaa:
            break
        u = (groo&E_set[v]).pop()
        #print("u=",u)
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        #print(path)
    for i, v in enumerate(path):
        if v in aaa:
            aaa.remove(v)
            if len(aaa)==0:
                break
    ans = path[i:]
    print(len(ans))
    print("\n".join(map(str, ans)))
    exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
def scc(N, G, RG):
    # https://tjkendev.github.io/procon-library/python/graph/scc.html
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

from collections import Counter
N, M = map(int, input().split())
E = [[] for _ in range(N+1)]
E_set = [set() for _ in range(N+1)]
E_rev = [[] for _ in range(N+1)]
E_rev_set = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E_set[a].add(b)
    E_rev[b].append(a)
    E_rev_set[b].add(a)

label, group = scc(N+1, E, E_rev)
cnt = Counter(group)
Closed = [False] * (N+1)

grooo = [set() for _ in range(N+1)]
for v, gr in enumerate(group):
    grooo[gr].add(v)

for v, gr in enumerate(group):
    if Closed[gr]:
        continue
    Closed[gr] = True
    if cnt[gr]==1:
        continue

    #print(gr, cnt[gr])
    groo = grooo[gr]

    path = [v]
    path_set = {v}
    while True:
        #print("v=",v)
        aaa = E_set[v]&path_set
        if aaa:
            break
        u = (groo&E_set[v]).pop()
        #print("u=",u)
        while E_rev_set[u]-{v} & path_set:
            path_set.remove(path.pop())
        path.append(u)
        path_set.add(u)
        v = u
        #print(path)
    for i, v in enumerate(path):
        if v in aaa:
            aaa.remove(v)
            if len(aaa)==0:
                break
    ans = path[i:]
    print(len(ans))
    print("\n".join(map(str, ans)))
    exit()
print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


from collections import deque
def bfs(g,root,memo,backtrack):
    q = deque()
    #memo = [-1]*n: あらかじめ初期化しておく
#    """初期化、キューに入れて訪問済みにする"""
#    memo[root] = 0
    q.append(root)
    """BFS"""
    while q: #キューが空になるまで
        v = q.popleft() #キューから情報を取り出す
        for c in g[v]:
            if memo[c] != -1: continue #訪問済みならスキップ
            # 訪問済みにしてキューに入れる
            memo[c] = memo[v] + 1
            backtrack[c] = v
            q.append(c)

##############################            

n,m = [int(i) for i in readline().split()]
g = [[] for _ in range(n)]

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

res = 1000000
v0 = -1
b0 = None

for v in range(n):
    memo = [-1]*n
    backtrack = [-1]*n
    bfs(g,v,memo,backtrack)
    if 1 < memo[v] < res:
        v0 = v
        b0 = backtrack
        res = memo[v]

#print(res,v0,b0)

if res == 1000000: print(-1)
else:
    i = b0[v0]
    ans = [i+1]
    while i != v0:
        i = b0[i]
        ans.append(i+1)
    ans.reverse()
    
    print(res+1)
    print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from heapq import heappush, heappop, heapreplace

def solve():
    N, M = map(int, input().split())
    E = [set() for _ in range(N)]
    for i in range(M):
        a, b = map(int, input().split())
        E[a-1].add(b-1)
    V_ = set()
    V = set(range(N))
    target = range(N+1)
    while V_ !=  V:
        visited = set()
        hq = []
        heappush(hq, (2,[-1,min(V)]))
        while hq:
            l, p = heappop(hq)
            v = p[-1]
            if v not in visited:
                visited.add(v)
                for u in E[v]&V:
                    if u in p:
                        target = min(target, p[p.index(u):], key=len)
                    else:
                        heappush(hq, (l+1, p+[u]))
        if target == range(N+1): 
            return '-1'
        else:
            V_ = V
            V = set(target)

    
    cycle = [str(v+1) for v in target]

    res = '\n'.join([str(len(cycle))]+cycle)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]
N, M = map(int,input().split())
g = [[np.inf]*(2*N) for _ in range(2*N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = 1
    g[a][b+N] = 1
    g[a+N][b] = 1

ans = np.inf
d = dijkstra(g,return_predecessors=True)

for i in range(N):
    if d[0][i][i+N] != np.inf:
        if ans != np.inf and len(ans)+1 <= d[0][i][i+N]:
            continue
        path = get_path(i,i+N,d[1])[::-1][:-1]
        path = [node%N for node in path]
        if len(path)==len(set(path)):
            if ans==np.inf or len(ans) > len(path):
                ans = path

if ans != np.inf:
    print(len(ans))
    for i in range(len(ans)):
        print(ans[i]+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,time
input = sys.stdin.readline
def main():
    start = time.time()
    n,m = map(int,input().split())
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)


    new = [0]*n
    for i in range(n):
        new[i] = [i]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        if time.time()-start > 1.7:
            print(n)
            for i in range(1,n+1):
                print(i)
            exit()
        
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,time
input = sys.stdin.readline
def main():
    start = time.time()
    n,m = map(int,input().split())
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)


    new = [0]*n
    for i in range(n):
        new[i] = [i]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        if time.time()-start > 1.8:
            print(-1)
            exit()
        
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v, l):
    for u in d[v]:
        if u in pvs:
            return l + [u]
        if u in vs:
            continue
        pvs.add(u)
        vs.add(u)
        ll = dfs(u, l + [u])
        pvs.remove(u)
        if ll:
            return ll
    return False

d = [set() for _ in range(N)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a-1].add(b-1)

vs = set()
for i in range(N):
    if i in vs:
        continue
    vs.add(i)
    pvs = set([i])
    loop = dfs(i, [i])
#    print(i, loop, vs)
    if loop:
        break

import sys
#print(loop)
if not loop:
    print("-1")
    sys.exit()
else:
    ll = []
    lx = loop[-1]
    f = False
    for x in loop:
        if lx == x and not f:
            f = True
            continue
        if not f:
            continue
        ll.append(x)
    loop = ll
#print(loop)

v2i = [-1 for _ in range(N)]
for i, v in enumerate(loop):
    v2i[v] = i

i = 0
vs = set()
ss = set()
lnum = len(loop)
ll = []
while True:
    if i in vs:
        break
    v = loop[i]

    m = 0
#    print(v, d[v], v2i, ss, vs)
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[u] in ss:
            continue
        if v2i[v] > v2i[u]:
            m = max(lnum - v2i[v] + v2i[u], m)
        else:
            m = max(v2i[u] - v2i[v], m)
#        print(u, m, v2i[u])
    for j in range(m-1):
        ss.add((i + j + 1) % lnum)
    vs.add(i)
    ll.append(v)
    i = (i + m) % lnum

print(len(ll))
for i in ll:
    print(i+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    print(1)
    n,m = map(int,input().split())
    edge = [[] for _ in [0]*n]
    for _ in range(m):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)


    new = [0]*n
    for i in range(n):
        new[i] = [i]
    res = []
    tank = []
    res2 = -1

    while len(new) > 0:
        tank = []
        for i in range(len(new)):
            el = new[i]

            for go in edge[el[-1]]:
                if not go in el:
                    if el[0] in edge[go]:
                        print(len(el)+1)
                        for e in el:
                            print(e+1)
                        print(go+1)

                        exit()
                    tank.append(el+[go])
        new = tank
        
    print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
def get_path(start, goal, pred):
    return get_path_row(start, goal, pred[start])

def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]
N, M = map(int,input().split())
g = [[np.inf]*(2*N) for _ in range(2*N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a][b] = 1
    g[a][b+N] = 1
    g[a+N][b] = 1

ans = -1
d = dijkstra(g,return_predecessors=True)

for i in range(N):
    if d[0][i][i+N] != np.inf:
        path = get_path(i,i+N,d[1])[::-1][:-1]
        path = [node%N for node in path]
        if len(path)==len(set(path)):
            ans = path
            break

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