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 collections
import bisect
def main():

    N, M = map(int, input().split())
    graph = collections.defaultdict(list)
    for i in range(M):
        a, b = map(int, input().split())
        graph[a].append(b)

    ans = []
    visited = set()
    for i in range(1, N+1):
        if i not in visited:
            visited.add(i)
            cur = [[i, [i], set([i])]]
            # print(cur)
            while cur:
                temp = []
                # print(cur)
                for j, l, s in cur:
                    flag = False
                    p = -1
                    for k in graph[j]:
                        if k in s:
                            flag = True
                            p = max(p, bisect.bisect_left(l, k))
                        else:
                            temp.append([k, l + [k], s | {k}])
                        if k not in visited:
                            visited.add(k)
                    if flag:
                        return l[p:]
                cur = temp

    return ans

if __name__ == '__main__':
    output = main()
    if len(output) == 0: print("-1")
    else:
        print(len(output))
        for v in output:
            print(v)

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()
		max_deep_next = -1
		last_list = []
		for node_next in graph[node]:
			if deep[node_next] >= 1:
				last_list.append(node_next)
			max_deep_next = max(max_deep_next, deep[node_next])
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if max_deep_next == 1:
			last = node
			judge = 1
			break
	if judge == 1:
		break


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

ans = [last]
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, 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()
		max_deep_next = -1
		last_list = []
		for node_next in graph[node]:
			if deep[node_next] >= 1:
				last_list.append(node_next)
			max_deep_next = max(max_deep_next, deep[node_next])
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if max_deep_next == 1:
			last = node
			judge = 1
			break
	if judge == 1:
		break


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

ans = [last]
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:
# -*- 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)
    visited = set()
    parent = [-1 for _ in range(N)]
    depth = [-1 for _ in range(N)]
    l = float('inf')
    target = -1
    hq = []
    heappush(hq, (0,0,-1))
    while hq:
        d,v,w = heappop(hq)
        if v not in visited:
            visited.add(v)
            depth[v] = d
            parent[v] = w
            for u in E[v]:
                if u in visited:
                    if d+1-depth[u] < l:
                        l = d+1-depth[u]
                        target = (v,u)
                else:
                    heappush(hq, (d+1,u,v))
    
    if target == -1: 
        res = '-1'
    else:      
        tail, head = target
        cycle = [str(tail+1)]
        while tail != head :
            tail = parent[tail]
            cycle.append(str(tail+1))

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

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

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()
		max_deep_next = -1
		for node_next in graph[node]:
			max_deep_next = max(max_deep_next, deep[node_next])
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if max_deep_next == 1:
			last_list = []
			last = node
			for node_next in graph[node]:
				if deep[node_next] >= 1:
					last_list.append(node_next)
			judge = 1
			break
	if judge == 1:
		break


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

ans = [last]
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, 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()
		max_deep_next = -1
		for node_next in graph[node]:
			max_deep_next = max(max_deep_next, deep[node_next])
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if max_deep_next == 1:
			last_list = []
			last = node
			for node_next in graph[node]:
				if deep[node_next] >= 1:
					last_list.append(last_list)
			judge = 1
			break
	if judge == 1:
		break


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

ans = [last]
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:
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 = [[i] for i in range(n)]
res = []
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]:
                    res = el
                    res2 = go
                    break
                tank.append(el+[go])
    new = tank

if res == []:
    print(-1)
else:
    print(len(res)+1)
    for e in res:
        print(e+1)
    print(go+1)

Submission status: Wrong Answer

Solution code:
import copy
import sys
sys.setrecursionlimit(1000000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int, input().split())
    e[a-1].append(b-1)

st=[0]*n

def func(po, li):
    global st
    st[po]=1
    for j in e[po]:
        if st[j] == 1:
            print(len(li))
            for val in li:
                print(val)
            exit()
        elif st[j] == 0:
            newli=copy.copy(li)
            newli.append(j+1)
            func(j, newli)
    st[po]=2
        


for p in range(n):
    if st[p] == 0:
        func(p, [p+1])

print(-1)

Submission status: Wrong Answer

Solution code:
import copy
import sys
sys.setrecursionlimit(1000000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int, input().split())
    e[a-1].append(b-1)

st=[0]*n

def func(po, li):
    global st
    st[po]=1
    for j in e[po]:
        if st[j] == 1:
            print(len(li))
            for val in li:
                print(val)
            exit
        elif st[j] == 0:
            newli=copy.copy(li)
            newli.append(j+1)
            func(j, newli)
    st[po]=2
        


for p in range(n):
    if st[p] == 0:
        func(p, [p+1])

print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, M = list(map(int, input().split()))
E = [None]*M
for m in range(M):
    E[m] = list(map(int, input().split()))

    
def main(): 
    I = [E[m][0] for m in range(M)]
    O = [E[m][1] for m in range(M)]

    cntI = collections.Counter(I)
    cntO = collections.Counter(O)
    
    L = []
    for key, val in cntO.items():
        if 1 < val:
            L.append(key)
    #print(L)
    for m in reversed(range(0, M)):
        if E[m][1] in L:
            E.pop(m)
    I2 = [E[m][0] for m in range(len(E))]
    O2 = [E[m][1] for m in range(len(E))]

    
    if len(I2) == 1:
        return print(-1)
    print(len(I2))
    
    for i in I2:
        print(i)
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def topological_sort(graph):
    """
    :param list of (list of int) graph:
    :return:
    """
    # 入次数
    ins = [0] * len(graph)
    for vs in graph:
        for v in vs:
            ins[v] += 1

    # 入次数がゼロのやつ
    zeros = []
    for v, cnt in enumerate(ins):
        if cnt == 0:
            zeros.append(v)

    # 入次数がゼロのやつから順に追加してく
    ret = []
    while zeros:
        v = zeros.pop()
        ret.append(v)
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                zeros.append(u)

    if len(ret) == len(graph):
        # トポロジカルソートできた
        return []

    cycle = []
    for i, c in enumerate(ins):
        if c > 0:
            cycle.append(i)

    ok = []
    for c in cycle:
        for v in graph[c]:
            if ins[v] > 0:
                ok.append(c)
                break

    return ok


N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)

cycle = topological_sort(graph)
if not cycle:
    print(-1)
    exit()

candidate = [False] * (N + 1)
for v in cycle:
    candidate[v] = True


def dfs(v, seen, hist):
    cc = []
    for u in graph[v]:
        if not candidate[u]:
            continue
        if seen[u]:
            cc.append(u)
    if cc:
        return hist, cc

    for u in graph[v]:
        if not candidate[u]:
            continue
        seen[u] = True
        hist.append(u)
        ret, lasts = dfs(u, seen, hist)
        seen[u] = False
        if ret:
            return ret, lasts
        hist.pop()
    return False, []


stack = cycle[:]
ng = [False] * (N + 1)
while stack:
    v = stack.pop()
    if ng[v]:
        continue
    seen = [False] * (N + 1)
    seen[v] = True
    ret, lasts = dfs(v, seen, [v])
    if lasts == [v] and len(ret) > 2:
        print(len(ret))
        print(*ret, sep='\n')
        exit()
    ng[v] = True
    for v in lasts:
        if not ng[v]:
            stack.append(v)

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
#vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
#    vu[B].add(A)

inV = [False]*N
for s in range(N):
#    print("s=",s)
#    print(uv)
    bfs_q = deque()
    bfs_q.append((s,set({})))
    while bfs_q:
        u, chain = bfs_q.pop()
        goal = False
        NG = False
        for c in uv[u]:
            if c == s and len(chain):
                goal = True
            elif c in chain:
                NG = True
                break
        if NG:
            continue
        elif goal:
            print(len(chain)+1)
            for c in chain:
                print(c+1)
            print(u+1)
            exit()
        elif u in chain:
            continue
        else:
            for c in uv[u]:
                new_chain = chain.copy()
                new_chain.add(u)
                bfs_q.append((c, new_chain))
    for i in range(s+1,N):
        if s in uv[i]:
            uv[i].remove(s)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

def dfs(v):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            k = dfs(u)
            if k != -1:
                return k
            vis[u] = 1
        else:
            return u
    return -1

def dfs2(v, path):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            p = dfs2(u, path+[v+1])
            if len(p) > 0:
                return p
            vis[u] = 1
        else:
            return path+[v]
    return []

N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
for i in range(N):
    vis = [1] * N
    u = dfs(i)
    if u != -1:
        vis = [1] * N
        path = set(dfs2(u, []))
        print(len(path))
        print(*path, sep = '\n')
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def topological_sort(graph):
    """
    :param list of (list of int) graph:
    :return:
    """
    # 入次数
    ins = [0] * len(graph)
    for vs in graph:
        for v in vs:
            ins[v] += 1

    # 入次数がゼロのやつ
    zeros = []
    for v, cnt in enumerate(ins):
        if cnt == 0:
            zeros.append(v)

    # 入次数がゼロのやつから順に追加してく
    ret = []
    while zeros:
        v = zeros.pop()
        ret.append(v)
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                zeros.append(u)

    if len(ret) == len(graph):
        # トポロジカルソートできた
        return []

    cycle = []
    for i, c in enumerate(ins):
        if c > 0:
            cycle.append(i)

    ok = []
    for c in cycle:
        for v in graph[c]:
            if ins[v] > 0:
                ok.append(c)
                break

    return ok


N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)

cycle = topological_sort(graph)
if not cycle:
    print(-1)
    exit()

candidate = [False] * (N + 1)
for v in cycle:
    candidate[v] = True


def dfs(v, seen, hist):
    cc = []
    for u in graph[v]:
        if not candidate[u]:
            continue
        if seen[u]:
            cc.append(u)
    if cc:
        return hist, cc

    for u in graph[v]:
        if not candidate[u]:
            continue
        seen[u] = True
        hist.append(u)
        ret, lasts = dfs(u, seen, hist)
        seen[u] = False
        if ret:
            return ret, lasts
        hist.pop()
    return False, []


stack = cycle[:]
ng = [False] * (N + 1)
while stack:
    v = stack.pop()
    if ng[v]:
        continue
    seen = [False] * (N + 1)
    seen[v] = True
    ret, lasts = dfs(v, seen, [v])
    if lasts == [v] and not len(ret) <= 2:
        print(len(ret))
        print(*ret, sep='\n')
        exit()
    ng[v] = True
    for v in lasts:
        if not ng[v]:
            stack.append(v)

print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)

v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(n)]

outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in es:
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)

def dfs(n, l):
    global outs
    for out in outs[n]:
        if out in l:
            if len(l) < v:
                print(len(l))
                for i in sorted(l):
                    print(i)
                exit()
        else:
            dfs(out, l[:] + [out])


if len(res) == v+1:
    pass
else:
    for i in range(1, v+1):
        dfs(i, [])
print("-1")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
graph = [[] for _ in range(n)]
for i in range(m):
    a, b = LI()
    graph[a - 1] += [b - 1]


visited = [0] * n
flag = False
ret = INF
for i in range(n):
    if visited[i]:
        continue
    que = deque()
    que.append((i, set([i])))
    visited[i] = 1
    while que:
        cur, visited_set = que.popleft()
        for nxt in graph[cur]:
            if nxt in visited_set:
                if len(visited_set) < ret:
                    ans = list(visited_set)
                    flag = True
            else:
                visited[nxt] = 1
                a = visited_set.copy()
                a.add(nxt)
                que += [(nxt, a)]

    if flag:
        for j in ans:
            print(j + 1)
        break
else:
    print(-1)

Submission status: Wrong Answer

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


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


parent_list = [ [] for i in range(n) ]
node_list = [ "White" for i in range(n) ]
node_list[0] = "Black"

search_list = [0]
loop_list = []
rank_list = [0 for i in range(n)]
r = 0
while search_list != []:
    r += 1
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:

            if node_list[j] == "White":
                new_search_list.append(j)
                node_list[j] = "Black"
                rank_list[j] = r
                
                parent_list[j] = parent_list[i] + [i]
            elif j in parent_list[i]:
                if rank_list[i] > rank_list[j] +1:
                    loop_list.append([rank_list[i]-rank_list[j],i,j])
    search_list = new_search_list
loop_list.sort()

if loop_list == []:
    print(-1)
else:
    r, p, q = loop_list[0]
    ans_list = [p]
    for j in parent_list[p]:
        if j not in parent_list[q]:
            ans_list.append(j)
    print(len(ans_list))
    for k in [ i+1 for i in ans_list ]:
        print(k)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

def dfs(v):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            k = dfs(u)
            if k != -1:
                return k
            vis[u] = 1
        else:
            return u
    return -1

def dfs2(v, path):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            p = dfs2(u, path+[v+1])
            if len(p) > 0:
                return p
            vis[u] = 1
        else:
            return path+[v]
    return []

N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
for i in range(N):
    vis = [1] * N
    u = dfs(i)
    if u != -1:
        vis = [1] * N
        path = dfs2(u, [])
        print(len(path))
        print(*path, sep = '\n')
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def topological_sort(graph):
    """
    :param list of (list of int) graph:
    :return:
    """
    # 入次数
    ins = [0] * len(graph)
    for vs in graph:
        for v in vs:
            ins[v] += 1

    # 入次数がゼロのやつ
    zeros = []
    for v, cnt in enumerate(ins):
        if cnt == 0:
            zeros.append(v)

    # 入次数がゼロのやつから順に追加してく
    ret = []
    while zeros:
        v = zeros.pop()
        ret.append(v)
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                zeros.append(u)

    if len(ret) == len(graph):
        # トポロジカルソートできた
        return []



    cycle = []
    for i, c in enumerate(ins):
        if c > 0:
            cycle.append(i)

    ok = []
    for c in cycle:
        for v in graph[c]:
            if ins[v] > 0:
                ok.append(c)
                break

    return ok


N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]

for a, b in AB:
    graph[a].append(b)

cycle = topological_sort(graph)
if not cycle:
    print(-1)
    exit()

candidate = [False] * (N + 1)
for v in cycle:
    candidate[v] = True



def dfs(v, seen, hist):
    cc = []
    for u in graph[v]:
        if not candidate[u]:
            continue
        if seen[u]:
            cc.append(u)
    if cc:
        return hist, cc

    for u in graph[v]:
        if not candidate[u]:
            continue
        seen[u] = True
        hist.append(u)
        ret, lasts = dfs(u, seen, hist)
        seen[u] = False
        if ret:
            return ret, lasts
        hist.pop()
    return False, []


stack = cycle[:]
ng = [False] * (N + 1)
while stack:
    v = stack.pop()
    if ng[v]:
        continue
    seen = [False] * (N + 1)
    seen[v] = True
    ret, lasts = dfs(v, seen, [v])
    if lasts == [v]:
        print(len(ret))
        print(*ret, sep='\n')
        exit()
    ng[v] = True
    for v in lasts:
        if not ng[v]:
            stack.append(v)

assert False

Submission status: Wrong Answer

Solution code:
from collections import deque
def main():
  a,b=map(int,input().split())
  c=[[] for i in range(a)]
  for i in range(b):
    x,y=map(int,input().split())
    c[x-1].append(y-1)
  
  d=deque()
  ans=-1
  e=[-1 for i in range(a)]
  for i in range(a):
    f=[0 for i in range(a)]
    if e[i]==-1:
      d.append(i)
      while len(d)!=0:
        x=d.pop()
        for y in c[x]:
          e[y]=x
          if f[y]==1:
            ans= y
            break
          else:
            f[y]=1
            d.append(y)
        if ans>-1:
          break
      if ans>-1:
        break
        
    if i==a-1:
      print(-1)
      break
  y=ans    
  ans2=[]
  while 1:
    ans2.append(e[y]+1)
    y=e[y]
    if y==ans:
      break
    
  print(len(ans2))
  for i in (ans2):
    print(i)
  
if __name__ == '__main__':  
  main()