Problem:


Score : 600 points

Problem Statement

Given is a directed graph G with N vertices and M edges.

The vertices are numbered 1 to N, and the i-th edge is directed from Vertex A_i to Vertex B_i.

It is guaranteed that the graph contains no self-loops or multiple edges.

Determine whether there exists an induced subgraph (see Notes) of G such that the in-degree and out-degree of every vertex are both 1. If the answer is yes, show one such subgraph.

Here the null graph is not considered as a subgraph.

Notes

For a directed graph G = (V, E), we call a directed graph G' = (V', E') satisfying the following conditions an induced subgraph of G:

V' is a (non-empty) subset of V.

E' is the set of all the edges in E that have both endpoints in V'.

Constraints

1 \leq N \leq 1000

0 \leq M \leq 2000

1 \leq A_i,B_i \leq N

A_i \neq B_i

All pairs (A_i, B_i) are distinct.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

If there is no induced subgraph of G that satisfies the condition, print -1.
Otherwise, print an induced subgraph of G that satisfies the condition, in the following format:

K
v_1
v_2
:
v_K

This represents the induced subgraph of G with K vertices whose vertex set is \{v_1, v_2, \ldots, v_K\}. (The order of v_1, v_2, \ldots, v_K does not matter.)
If there are multiple subgraphs of G that satisfy the condition, printing any of them is accepted.

Sample Input 1

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

Sample Output 1

3
1
2
4

The induced subgraph of G whose vertex set is \{1, 2, 4\} has the edge set \{(1, 2), (2, 4), (4, 1)\}. The in-degree and out-degree of every vertex in this graph are both 1.

Sample Input 2

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

Sample Output 2

-1

There is no induced subgraph of G that satisfies the condition.

Sample Input 3

6 9
1 2
2 3
3 4
4 5
5 6
5 1
5 2
6 1
6 2

Sample Output 3

4
2
3
4
5



Sample input:
4 5
1 2
2 3
2 4
4 1
4 3


Sample output:
3
1
2
4

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().strip().split())

v_list = [[] for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().strip().split())
	v_list[a - 1].append(b - 1)

def check(start):
	queue = [start]
	prevs = [None] * N
	visited = [False] * N
	visited[start] = 0
	while queue:
		v = queue.pop(0)
		d = visited[start] + 1
		for nv in v_list[v]:
			if nv == start:
				route = [v]
				while True:
					prev = prevs[v]
					if prev == None:
						route.reverse()
						return route
					route.append(prev)
					v = prev
			elif visited[nv] == False or visited[nv] > d:
				prevs[nv] = v
				visited[nv] = d
				queue.append(nv)
	return None

def find():
	for start in range(N):
		route = check(start)
		if route != None:
			return route
		else:
			return None

def find_another_route(prev, cur, v_table):
	for nv in v_list[prev]:
		if nv != cur and (nv in v_table):
			return nv
	return None

def fix(route):
	v_table = set(route)
	prev = route[-1]
	for i in range(len(route)):
		cur = route[i]
		another = find_another_route(prev, cur, v_table)
		if another != None:
			new_route = [prev, another]
			j = 0
			while route[j] != another:
				j += 1
			while True:
				j += 1
				cur = route[j]
				if cur == prev:
					return new_route
				else:
					new_route.append(cur)
		prev = cur
	return None

route = find()
if route == None:
	print("-1")
else:
	while True:
		new_route = fix(route)
		if new_route != None:
			route = new_route
		else:
			break
	print(len(route))
	for v in route:
		print(v + 1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
t=[[]for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    t[a].append(b)
def f(a,b):
    c=0
    for i in t[a]:
        for j in b[::-1]:
            if j in t[i]:
                return(b[b.index(j):])
                c=1
                break
        else:
            f(i,b+[i])
for i in range(1,n+1):
    c=f(i,[i])
    if c!=None:
        print(len(c))
        for i in c:
            print(i)

Submission status: Wrong Answer

Solution code:
	
print(-1)
exit()

Submission status: Wrong Answer

Solution code:
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]:
                loop_list.append([abs(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(10**6)

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


def dfs(i, visited, path):
    if visited[i]:
        index = path.index(i)
        print(len(path) - index)
        for x in path[index:]:
            print(x + 1)
        exit()
    if len(es[i]) > 0:
        visited[i] = True
        path.append(i)
        for j in es[i]:
            dfs(j, visited, path)
        visited[i] = False
        path.pop()


for i in range(n):
    dfs(i, [False] * n, [])
print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().strip().split())

v_list = [[] for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().strip().split())
	v_list[a - 1].append(b - 1)

def check(start):
	queue = [start]
	prevs = [None] * N
	visited = [False] * N
	while queue:
		v = queue.pop(0)
		for nv in v_list[v]:
			if nv == start:
				route = [v]
				while True:
					prev = prevs[v]
					if prev == None:
						route.reverse()
						return route
					route.append(prev)
					v = prev
			elif not visited[nv]:
				prevs[nv] = v
				visited[nv] = True
				queue.append(nv)
	return None

def find():
	for start in range(N):
		route = check(start)
		if route != None:
			return route
		else:
			return None

def find_another_route(prev, cur, v_table):
	for nv in v_list[prev]:
		if nv != cur and (nv in v_table):
			return nv
	return None

def fix(route):
	v_table = set(route)
	prev = route[-1]
	for i in range(len(route)):
		cur = route[i]
		another = find_another_route(prev, cur, v_table)
		if another != None:
			new_route = [prev, another]
			j = 0
			while route[j] != another:
				j += 1
			while True:
				j += 1
				cur = route[j]
				if cur == prev:
					return new_route
				else:
					new_route.append(cur)
		prev = cur
	return None

route = find()
if route == None:
	print("-1")
else:
	while True:
		new_route = fix(route)
		if new_route != None:
			route = new_route
		else:
			break
	print(len(route))
	for v in route:
		print(v + 1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
V = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a in V:
        V[a].append(b)
    else:
        V[a] = [b]


def fun(l):
    if l[-1] not in V:
        return None
    for bb in V[l[-1]]:
        if bb in l:
            return l
        re = fun(list(l) + [bb])
        if re:
            return re
    return None


result = None

for a in V.keys():
    result = fun([a, ])
    if result:
        break

if not result:
    print(-1)
else:
    for r in result:
        print(r)

Submission status: Wrong Answer

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

from copy import copy

n,m = map(int, input().split())

G = [[] for i in range(n)]

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

def dfs(cur, s, start):
    if cur < start:
        return
    if cur == start and len(s) != 0:
        print(len(s))
        for i in s:
            print(i+1)
        exit()
    s.add(cur)
    a = []
    f = False
    for to in G[cur]:
        if to == start:
            f = True
        elif to in s:
            return
        else:
            a.append(to)
    if f:
        dfs(start, s, start)
    else:
        for to in a:
            ss = copy(s)
            dfs(to, ss, start)

for i in range(n):
    dfs(i, set(), i)
print(-1)

Submission status: Wrong Answer

Solution code:
INF = float('inf')
from collections import defaultdict
from heapq import heappop, heappush

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()

class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:INF)
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]




N, M = map(int,input().split())
g = Graph()

for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g.add_edge(a,b)
    g.add_edge(a,b+N)
    g.add_edge(a+N,b)

d = [Dijkstra(g,i) for i in range(2*N)]
dist = [d[i].dist for i in range(2*N)]

ans = -1
for i in range(N):
    if dist[i][i+N] != INF:
        path = d[i].shortest_path(i+N)
        path = path[:-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)

Submission status: Wrong Answer

Solution code:
import collections
V, E = [int(_) for _ in input().split()]
G = [set() for _ in range(V + 1)]
for _ in range(E):
    s, t = [int(_) for _ in input().split()]
    G[s].add(t)
seen = set()
for start in range(1, V + 1):
    if start in seen:
        continue
    parent = [-1] * (V + 1)
    stack = collections.deque([start])
    while stack:
        now = stack.popleft()
        if now in seen:
            end = now
            now = parent[now]
            ans = [end]
            while now != end:
                ans += [now]
                now = parent[now]
            print(len(ans))
            print(*ans[::-1], sep='\n')
            exit()
        seen.add(now)
        for ne in G[now]:
            if not ne in seen:
                parent[ne] = now
                stack += [ne]
print(-1)

Submission status: Wrong Answer

Solution code:
import collections
V, E = [int(_) for _ in input().split()]
G = [set() for _ in range(V + 1)]
for _ in range(E):
    s, t = [int(_) for _ in input().split()]
    G[s].add(t)
seen = set()
for start in range(1, V + 1):
    if start in seen:
        continue
    parent = [-1] * (V + 1)
    stack = [start]
    while stack:
        now = stack.pop()
        if now in seen:
            end = now
            now = parent[now]
            ans = [end]
            while now != end:
                ans += [now]
                now = parent[now]
            print(len(ans))
            print(*ans[::-1], sep='\n')
            exit()
        seen.add(now)
        for ne in G[now]:
            if not ne in seen:
                parent[ne] = now
                stack += [ne]
print(-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:
			judge = 1
			last = node
			break
	if judge == 1:
		break

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

ans = [last]
while True:
	x = parent[ans[-1]]
	if x == -1:
		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 = [ 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 = []

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"
                parent_list[j] = parent_list[i] + [i]
            elif j in parent_list[i]:
                loop_list.append([i,j])
    search_list = new_search_list


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
import sys
from collections import defaultdict
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()

G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]

for _ in range(M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)

def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g


def check(target):
    if len(target) == 1:
        return False

    init = list(target)[0]*1
    Q = [init]
    searched = [0] * len(G)
    searched[init] = 1
    
    while Q:
        p = Q.pop()
        for q in G[p]:
            if searched[q]:
                continue
            if not q in target:
                continue
            searched[q] = True
            Q.append(q)
    if not all([searched[x] for x in target]):
        return False
    
    Q = [init]
    searched = [0] * N
    searched[init] = 1

    while Q:
        p = Q.pop()
        for q in rG[p]:
            if searched[q]:
                continue
            if not q in target:
                continue
            searched[q] = True
            Q.append(q)

    return all([searched[x] for x in target])


group, g = SCC(G, rG)

units = defaultdict(set)

for i in range(N):
    units[group[i]].add(i)

for unit in units.values():
    if len(unit) == 1:
        continue
    target = unit | set()
    
    while True:
        for u in unit:
            if check(target ^ set([u])):
                target = target ^ set([u])

        if unit == target:
            break
        else:
            unit = target | set()
    print(len(target))
    print(*[t+1 for t in target], sep="\n")
    break
else:
    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 []

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


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 solve_f(n, g):

    for i in range(n):
        parent = [-1] * n
        queue = deque([i])
        done = False
        answer = []
        # bfs
        while len(queue) > 0:
            p = queue.popleft()
            for q in g[p]:
                if q == i:
                    res_list = []
                    while p != -1:
                        res_list.append(p + 1)
                        p = parent[p]
                    return [len(res_list)] + res_list
                if parent[q] == -1:
                    parent[q] = p
                    queue.append(q)

    return [-1]


def main():
    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)
    res = solve_f(n, g)
    for r in res:
        print(r)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = list(map(int, input().split()))
v = N
n = M
es = [[int(x)-1 for x in input().split()] for _ in range(n)]
or_cop = [[] for i in range(N)]
for e in es:
    or_cop[e[1]].append(e[0])
e_list = [[] for i in range(N)]
for e in es:
    e_list[e[0]].append(e[1])

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)

if len(res)==N:
    print(-1)
else:
    marker = [0]*N
    for i in range(len(res)):
        marker[res[i]] = 1

    for i in range(N):
        if marker[i]==0:
            break
    
    vi = i #時と場合によってここを変える
    Q = deque([vi])
    prev_list = [-1 for i in range(N)]
    checked_list = [False for i in range(N)]
    checked_list[vi]=True
    #print(e_list)
    while len(Q)>0:
        v = Q.pop()
        #print(v)
        for v1 in e_list[v]:
            #print(v1)
            if v1==vi:
                break
            if not checked_list[v1]:
                checked_list[v1] = True
                Q.appendleft(v1)
                prev_list[v1] = v
    #print(prev_list)
    ans = []
    while v!=vi:
        #print(v)
        ans.append(v+1)
        v = prev_list[v]
    ans.append(vi+1)
    ans = ans[::-1]
    print(len(ans))
    for a in ans:
        print(a)

Submission status: Wrong Answer

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

n, m = list(map(int, input().split()))

edges = [[] for _ in range(n + 1)]
for _ in range(m):
	frm, to = list(map(int, input().split()))
	edges[frm].append(to)

def dfs(cur, visited, do_not_visit):
	#print(cur)
	if len(visited) > 0 and cur == visited[0]:
		print(len(visited))
		for x in visited:
			print(x)
		sys.exit()
	if len(edges[cur]) == 0:
		return
	else:
		if len(set(edges[cur]) & set(do_not_visit)) > 0:
			return
		for e in edges[cur]:
			if e not in do_not_visit:
				dfs(e, visited + [cur], do_not_visit + edges[cur])

for i in range(1, n + 1):
	dfs(i, [], [])

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:
    print("-1")
else:
    for i in range(1, v+1):
        dfs(i, [])

Submission status: Wrong Answer

Solution code:
def has_duplicates(seq):
    return len(seq) != len(set(seq))

inputs = input().split()
n = int(inputs[0])
m = int(inputs[1])
a = [0]*m
b = [0]*m
for i in range(m):
    inputs = input().split()
    a[i] = int(inputs[0])
    b[i] = int(inputs[1])

rec = []
copyl = []
flg = 0
exFlg = 0
ans = []
for i in range(m):
    copyl = []
    flg = 0
    for l in rec:
        if l[-1] == a[i]:
            lcopy = list(l)
            copyl.append(lcopy)
            l.append(b[i])
            flg = 1
    rec.append([a[i], b[i]])
    for e in copyl:
        rec.append(e)
    for l in rec:
        if has_duplicates(l):
            exFlg = 1
            for e in reversed(l[:-1]):
                ans.append(e)
                if e == l[-1]:
                    break
        if exFlg == 1:
            break
    if exFlg == 1:
        break
if exFlg == 1:
    print(len(ans))
    for e in ans:
        print(e)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq
def dijkstra(s,path):
    inf = float('inf')
    n = len(path)

    # 距離をinfで初期化
    d = [inf for i in range(n)]
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for cost,to in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p]+cost
                heapq.heappush(q,(d[to], to))
    return d

def path_recovery(e,d,path):
    # 経路
    route = [e]
    # 残りの距離
    a = d[e]
    while a!=0:
        for i in range(len(path[e])):
            if d[path[e][i][1]]+path[e][i][0]==a:
                route.append(path[e][i][1])
                a -= path[e][i][0]
                e = path[e][i][1]
                break
    route.reverse()
    return route

inf = float('inf')

n,m = map(int, input().split())
# s:始点, path[i]:[[cost,to]...] i=fromの隣接リスト
path = [[]for i in range(n)]
path2 = [[]for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    path[a-1].append([1,b-1])
    path2[b-1].append([1,a-1])

x = [[] for i in range(n)]

for i in range(n):
    d = dijkstra(i,path)
    x[i]=d

# e:終点, d[i]:始点から各頂点への最短距離, path[i]:[[cost,to]...] i=fromの隣接リスト

for i in range(n):
    for j in range(i+1,n):
        if x[i][j]!=inf and x[j][i]!=inf:
            ans = path_recovery(j,x[i],path2)
            ans2 = path_recovery(i,x[j],path2)
            print(len(ans)+len(ans2)-2)
            for k in range(len(ans)-1):
                print(ans[k]+1)
            for k in range(len(ans2)-1):
                print(ans2[k]+1)
            exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()

G = [[] for _ in range(N)]
rG = [[] for _ in range(N)]

for _ in range(M):
    a, b = inpl()
    G[a-1].append(b-1)
    rG[b-1].append(a-1)

def SCC(G, rG):
    N = len(G)
    def dfs(i):
        nonlocal t, rorder, searched
        searched[i] = True
        for j in G[i]:
            if not searched[j]:
                dfs(j)
        rorder[t] = i
        t += 1

    def rdfs(i):
        nonlocal t, group, g
        group[i] = g
        for j in rG[i]:
            if group[j] == -1:
                rdfs(j)

    t = 0
    rorder = [-1]*N
    searched = [0]*N
    group = [-1]*N

    for i in range(N):
        if not searched[i]:
            dfs(i)
    g = 0
    for i in range(N-1, -1, -1):
        if group[rorder[i]] == -1:
            rdfs(rorder[i])
            g += 1
    return group, g


def check(target):
    if len(target) == 1:
        return False

    init = list(target)[0]*1
    Q = [init]
    searched = [0] * len(G)
    searched[init] = 1
    
    while Q:
        p = Q.pop()
        for q in G[p]:
            if searched[q]:
                continue
            if not q in target:
                continue
            searched[q] = True
            Q.append(q)
    if not all([searched[x] for x in target]):
        return False
    
    Q = [init]
    searched = [0] * N
    searched[init] = 1

    while Q:
        p = Q.pop()
        for q in rG[p]:
            if searched[q]:
                continue
            if not q in target:
                continue
            searched[q] = True
            Q.append(q)

    return all([searched[x] for x in target])


group, g = SCC(G, rG)

units = defaultdict(set)

for i in range(N):
    units[group[i]].add(i)

for unit in units.values():
    if len(unit) == 1:
        continue
    target = unit | set()
    for u in unit:
        if check(target ^ set([u])):
            target = target ^ set([u])
    print(len(target))
    print(*[t+1 for t in target], sep="\n")
    break
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def has_duplicates(seq):
    return len(seq) != len(set(seq))

inputs = input().split()
n = int(inputs[0])
m = int(inputs[1])
a = [0]*m
b = [0]*m
for i in range(m):
    inputs = input().split()
    a[i] = int(inputs[0])
    b[i] = int(inputs[1])

rec = []
copyl = []
flg = 0
exFlg = 0
ans = []
for i in range(m):
    print(rec)
    copyl = []
    flg = 0
    for l in rec:
        if l[-1] == a[i]:
            lcopy = list(l)
            copyl.append(lcopy)
            l.append(b[i])
            flg = 1
    rec.append([a[i], b[i]])
    for e in copyl:
        rec.append(e)
    for l in rec:
        if has_duplicates(l):
            exFlg = 1
            for e in reversed(l[:-1]):
                ans.append(e)
                if e == l[-1]:
                    break
        if exFlg == 1:
            break
    if exFlg == 1:
        break
if exFlg == 1:
    print(len(ans))
    for e in ans:
        print(e)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
neighbours = [[] for i in range(N)]
for i in range(M):
    A, B = map(lambda x:int(x)-1,input().split())
    neighbours[A].append(B)
print()
visited = [False for i in range(N)]

def bfs(node):
    parents = [None for i in range(N)]
    stack = [node]
    while stack:
        item = stack.pop(0)
        orig = item
        for neighbour in neighbours[item]:
            if visited[neighbour]:
                try:
                    graph = {neighbour}
                    while item != neighbour:
                        graph.add(item)
                        item = parents[item]
                        if item == orig and item != neighbour:
                            1/0
                    print(len(graph))
                    for item in graph:
                        print(item+1)
                    return True
                except:
                    pass
            if not visited[neighbour]:
                parents[neighbour] = item
                visited[neighbour] = True
                stack.append(neighbour)
            
for i in range(N):
    if not visited[i]:
        if bfs(i):
            break
else:
   print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().strip().split())

v_list = [[] for _ in range(N)]
for _ in range(M):
	a, b = map(int, input().strip().split())
	v_list[a - 1].append(b - 1)

def check(start):
	queue = [start]
	prevs = [None] * N
	visited = [False] * N
	while queue:
		v = queue.pop()
		for nv in v_list[v]:
			if nv == start:
				route = [v]
				while True:
					prev = prevs[v]
					if prev == None:
						route.reverse()
						return route
					route.append(prev)
					v = prev
			elif not visited[nv]:
				prevs[nv] = v
				visited[nv] = True
				queue.append(nv)
	return None

def find():
	for start in range(N):
		route = check(start)
		if route != None:
			return route
		else:
			return None

def find_another_route(prev, cur, v_table):
	for nv in v_list[prev]:
		if nv != cur and (nv in v_table):
			return nv
	return None

def fix(route):
	v_table = set(route)
	prev = route[-1]
	for i in range(len(route)):
		cur = route[i]
		another = find_another_route(prev, cur, v_table)
		if another != None:
			new_route = [prev, another]
			j = 0
			while route[j] != another:
				j += 1
			while True:
				j += 1
				cur = route[j]
				if cur == prev:
					return new_route
				else:
					new_route.append(cur)
		prev = cur
	return None

route = find()
if route == None:
	print("-1")
else:
	while True:
		new_route = fix(route)
		if new_route != None:
			route = new_route
		else:
			break
	print(len(route))
	for v in route:
		print(v + 1)