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:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)

E = [[e for e in edge[i]] for i in range(N)]

search = [[i, []] for i in range(N)]
searched = [False for i in range(N)]
base = None
while len(search) > 0:
    s = search.pop()
    n, path = s[0], s[1]
    new_path = [i for i in path]
    new_path.append(n)
    for e in E[n]:
        if e == new_path[0]:
            base = new_path
            break
        else:
            search.append([e, new_path])

if base == None:
    print(-1)
    exit()
def delete_edge(base):
    set_base = set(base)
    for b in base:
        edge[b] = list(set_base & set(edge[b]))

def find_irr_edge(base):
    n = len(base)
    for i in range(n):
        if len(edge[i]) > 1:
            for e in edge[i]:
                if e != base[(i+1) % n]:
                    return (base[i],e)
    return None

delete_edge(base)
e = find_irr_edge(base)
N = len(base)
while e != None:
    s,t = e[0], e[1]
    new_base = [s,t]
    flag = False
    for i in range(2*N):
        n = base[i % N]
        if not flag:
            if n == t:
                flag = True
            continue
        else:
            if n != s:
                new_base.append(n)
            else:
                break
    base = new_base
    N = len(base)
    delete_edge(base)
    e = find_irr_edge(base)

print(N)
for i in base:
    print(i+1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
edge = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)

E = [[e for e in edge[i]] for i in range(N)]

search = [[i, []] for i in range(N)]
searched = [False for i in range(N)]
base = None
while len(search) > 0:
    s = search.pop()
    n, path = s[0], s[1]
    new_path = [i for i in path]
    new_path.append(n)
    for e in E[n]:
        if e in new_path:
            for i in range(len(new_path)):
                if new_path[i] != e:
                    continue
                else:
                    base = new_path[i:]
                    break
            break
        else:
            search.append([e, new_path])
    E[n] = []

if base == None:
    print(-1)
    exit()
def delete_edge(base):
    set_base = set(base)
    for b in base:
        edge[b] = list(set_base & set(edge[b]))

def find_irr_edge(base):
    n = len(base)
    for i in range(n):
        if len(edge[i]) > 1:
            for e in edge[i]:
                if e != base[(i+1) % n]:
                    return (base[i],e)
    return None

delete_edge(base)
e = find_irr_edge(base)
N = len(base)
while e != None:
    s,t = e[0], e[1]
    new_base = [s,t]
    flag = False
    for i in range(2*N):
        n = base[i % N]
        if not flag:
            if n == t:
                flag = True
            continue
        else:
            if n != s:
                new_base.append(n)
            else:
                break
    base = new_base
    N = len(base)
    delete_edge(base)
    e = find_irr_edge(base)

print(N)
for i in base:
    print(i+1)

Submission status: Wrong Answer

Solution code:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

for h in range(N):
    r = DFS(h,0)
    if r > 0:
        for i, v in enumerate(visit):
            if v < r:
                S.discard(i)
            elif i in S:
                for j in to[i]:
                    if j in S:
                        if j < i:
                            for k in range(j):
                                S.discard(k)
                            for k in range(i+1, N):
                                S.discard(k)
                        else:
                            for k in range(i+1, j):
                                S.discard(k)
        print(len(S))
        for i in list(S):
            print(i+1)
        break
    if h == N-1:
        print(-1)

Submission status: Wrong Answer

Solution code:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

flag = True
for i in range(N):
    r = DFS(i,0)
    if r > 0:
        for i, v in enumerate(visit):
            if v < r:
                S.discard(i)
            elif i in S:
                for j in to[i]:
                    if j in S:
                        if j < i:
                            for k in range(j):
                                S.discard(k)
                            for k in range(i+1, N):
                                S.discard(k)
                        else:
                            for k in range(i+1, j):
                                S.discard(k)
        print(len(S))
        for i in list(S):
            print(i+1)
        break
    if i == N-1:
        print(-1)

Submission status: Wrong Answer

Solution code:
print()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if not m:
    print(-1)
    exit()
e=[[]for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
f=[None]*n
f[0]=-1
s=[0]
while s:
    v=s.pop()
    for w in e[v]:
        if f[w]!=None:
            print(0)
            exit()
        else:
            f[w]=v
            s+=w,
print(-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
if not m:
    print(-1)
    exit()
e=[[]for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
f=[None]*n
f[0]=-1
s=[0]
while s:
    v=s.pop()
    for w in e[v]:
        if f[w]!=None:
            ans=[]
            while v!=w:
                if len(ans)>n or v==None:
                    print(-1)
                    exit()
                ans+=v+1,
                v=f[v]
            ans+=w+1,
            if len(ans)<3:
                print(-1)
            else:
                print(0)
                #print(len(ans))
                #print(*ans[::-1],sep='\n')
            exit()
        else:
            f[w]=v
            s+=w,
print(-1)

Submission status: Wrong Answer

Solution code:
print("""0""")

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 i in range(M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)


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


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

node_list = deque([last])
while True:
	loc = parent[node_list[0]]
	if loc == -1:
		break
	else:
		node_list.appendleft(loc)

node_set = set([node_list[0]])


for i in range(1, len(node_list)):
	max_depth = -1
	for edge in graph[node_list[i]]:
		if edge in node_set:
			for j in range(i):
				if edge == node_list[j]:
					max_depth = max(max_depth, j)
	if max_depth >= 0:
		start = max_depth
		end = i
	node_set.add(node_list[i])

#print(node_set, node_list, depth)
print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 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 i in range(M):
	A, B = list(map(int, input().split()))
	A -= 1
	B -= 1
	graph[A].append(B)


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


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

node_list = deque([last])
while True:
	loc = parent[node_list[0]]
	if loc == -1:
		break
	else:
		node_list.appendleft(loc)

node_set = set([node_list[0]])

for i in range(1, len(node_list)):
	max_depth = -1
	for edge in graph[node_list[i]]:
		if edge in node_set:
			for j in range(i):
				if edge == node_list[j]:
					max_depth = max(max_depth, j)
	if max_depth >= 0:
		start = max_depth
		end = i
	node_set.add(node_list[i])

print(end + 1 - start)
for node in range(start, end + 1):
	print(node_list[node] + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from copy import deepcopy


# detection of a cycle
def detect_cycle(N, repn):
    color = ['WHITE'] * (N + 1)
    unfinished_vertex = set([i for i in range(1, N + 1)])
    cycle = []
    Repn = deepcopy(repn)

    def dfs(u0):
        deq = deque([u0])
        color[u0] = 'GRAY'

        while deq != deque([]) and cycle == []:
            u = deq[-1]
            if len(Repn[u]) != 0:
                v = Repn[u].popleft()
                if color[v] == 'WHITE':
                    color[v] = 'GRAY'
                    deq.append(v)
                elif color[v] == 'GRAY':
                    cycle.append(v)
            else:
                deq.pop()
                color[u] = 'BLACK'
                unfinished_vertex.remove(u)

        return deq

    while cycle == [] and unfinished_vertex != set([]):
        u = unfinished_vertex.pop()
        unfinished_vertex.add(u)
        deq = dfs(u)
        #print('deq = {}, cycle = {}'.format(deq, cycle))
    #print('deq = {}'.format(deq))
    if cycle != []:
        v = cycle.pop()
        while True:
            u = deq.pop()
            cycle.append(u)
            if u == v:
                break
        cycle.reverse()
        return cycle # cycle = [v -> ... -> u (-> v)]
    else:
        return []

# one-step minimization of a cycle
def minimize_cycle(cycle, repn):
    length = len(cycle)
    cycle_idx = {u : i for i, u in enumerate(cycle)}
    minimized = False

    for i, u in enumerate(cycle):
        if minimized == True:
            break
        else:
            for v in repn[u]:
                if v in cycle_idx.keys():
                    j = cycle_idx[v]
                    if i + 1 == j:
                        continue
                    elif i == length - 1 and j == 0:
                        continue
                    elif i < j:
                        reduced_cycle = cycle[:(i + 1)] + cycle[j:]
                        minimized = True
                        break
                    else:
                        reduced_cycle = cycle[j:(i + 1)]
                        minimized = True
                        break

    if minimized == True:
        return reduced_cycle, minimized
    else:
        return cycle, minimized


def main():
    N, M = map(int, input().split())
    repn = [deque([]) for i in range(N + 1)]
    for _ in range(M):
        a, b = map(int, input().split())
        repn[a].append(b)

    cycle = detect_cycle(N, repn)
    #print('cycle detected: {}'.format(cycle))
    if cycle == []:
        print(-1)
        exit()

    minimized = True
    while minimized == True:
        cycle, minimized = minimize_cycle(cycle, repn)
        #print('cycle minimized: {}, {}'.format(minimized, cycle))

    for u in cycle:
        print(u)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import copy

n, m = map(int, sys.stdin.readline().split())
adj = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    adj[a].append(b)


def searchRoute(i):
    global adj
    nexts = deque()
    route = [i]
    visited = set()
    result = []
    for x in adj[i]:
        if x < i:
            continue
        nroute = copy.copy(route)
        nvisited = copy.copy(visited)
        nexts.append((x, nroute, nvisited))
    while len(nexts) > 0:
        error = False
        found = False
        x, xroute, xvisited = nexts.popleft()
        xroute.append(x)
        xvisited.add(x)
        for y in adj[x]:
            if y < i:
                continue
            if y == i:
                found = True
                continue
            if y in xvisited:
                error = True
                break
            yroute = copy.copy(xroute)
            yvisited = copy.copy(xvisited)
            nexts.append((y, yroute, yvisited))
        if error:
            continue
        if found:
            result = xroute
            break
    return result


for i in range(1, n+1):
    res = searchRoute(i)
    if len(res) > 0:
        print(len(res))
        for j in res:
            print(j)
        exit()

print(-1)

Submission status: Wrong Answer

Solution code:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1


flag = True
for i in range(N):
    if DFS(i,0) > 0:
        break
    if i == N - 1:
        flag = False
        print(-1)

if flag:
    for i, v in enumerate(visit):
        if v <= 0:
            S.discard(i)
        elif i in S:
            for j in to[i]:
                if j in S:
                    if j < i:
                        for k in range(j):
                            S.discard(k)
                        for k in range(i+1, N):
                            S.discard(k)
                    else:
                        for k in range(i+1, j):
                            S.discard(k)
    print(len(S))
    for i in list(S):
        print(i+1)

Submission status: Wrong Answer

Solution code:
import queue

import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
S = set(range(N))

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

visit = [0] * N
def DFS(p, n):
    if visit[p] != 0:
        return visit[p]
    else:
        visit[p] = n + 1
        for i in to[p]:
            r = DFS(i, n + 1)
            if r > 0:
                return r
        visit[p] = -1
        return -1

if DFS(0,0) == -1:
    print(-1)
else:
    for i, v in enumerate(visit):
        if v <= 0:
            S.discard(i)
        elif i in S:
            for j in to[i]:
                if j in S:
                    if j < i:
                        for k in range(j):
                            S.discard(k)
                        for k in range(i+1, N):
                            S.discard(k)
                    else:
                        for k in range(i+1, j):
                            S.discard(k)
    print(len(S))
    for i in list(S):
        print(i+1)

Submission status: Wrong Answer

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

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

EIN=[0]*N
EOUT=[0]*N

EINLIST=[[] for i in range(N)]
EOUTLIST=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1

    EOUT[x]+=1
    EIN[y]+=1

    EOUTLIST[x].append(y)
    EINLIST[y].append(x)

from collections import deque

Q=deque()
USE=[1]*N

for i in range(N):
    if EIN[i]==0 or EOUT[i]==0:
        Q.append(i)
        USE[i]=0

while Q:
    x=Q.pop()

    for to in EOUTLIST[x]:
        if USE[to]==0:
            continue
        EIN[to]-=1
        if EIN[to]==0:
            Q.append(to)
            USE[to]=0

    for fr in EINLIST[x]:
        if USE[fr]==0:
            continue
        EOUT[fr]-=1
        if EOUT[fr]==0:
            Q.append(fr)
            USE[fr]=0

def shortcut(ANS):
    #print(ANS)

    ANSSET=set(ANS)
    LEN=len(ANS)
    flag=0

    for i in range(LEN):
        for to in EOUTLIST[ANS[i]]:
            if to in ANSSET and ANS[(i+1)%LEN]!=to:
                flag=1
                x=ANS.index(to)

                #print(ANS,i,x)

                break
        if flag:
            break
    #print(flag)

    if flag:
        if x<i:
            return shortcut(ANS[x:i+1])
        else:
            return shortcut(ANS[x:]+ANS[:i+1])

    else:
        return ANS

ANS=[i for i in range(N) if USE[i]==1]
ANS=shortcut(ANS)
if len(ANS)==0:
    print(-1)
else:
    print(len(ANS))
    for ans in ANS:
        print(ans+1)

Submission status: Wrong Answer

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []

t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])
        if len(ans) != 0:
            break

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

check = 1
while check == 1:
    check = 0
    #print(ans)
    for x in e[ans[0]]:
        if x == ans[1]:
            continue
        elif x in ans:
            ans = [] + ans[:ans.index(x)+1]
            check = 1
            break
    if check == 1:
        continue
    else:
        e[ans[0]] = []
    for i in range(1, len(ans)-1):
        for x in e[ans[i]]:
            if x == ans[0]:
                ans = [] + ans[:i+1]
                check = 1
                break
            elif x in ans[:i]:
                ans = [] + ans[ans.index(x):i+1]
                check = 1
                break
        if check == 1:
            break
    if check == 1:
        continue
    for x in e[ans[-1]]:
        if x in ans[1:len(ans)-1]:
            ans = [] + ans[ans.index(x):]
            check = 1
            break

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

Submission status: Wrong Answer

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []

t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])
        if len(ans) != 0:
            break

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

check = 1
while check == 1:
    check = 0
    #print(ans)
    for x in e[ans[0]]:
        if x == ans[1]:
            continue
        elif x in ans:
            ans = [] + ans[:ans.index(x)+1]
            check = 1
            break
    if check == 1:
        continue
    for i in range(1, len(ans)-1):
        for x in e[ans[i]]:
            if x == ans[0]:
                ans = [] + ans[:i+1]
                check = 1
                break
            elif x in ans[:i]:
                ans = [] + ans[ans.index(x):i+1]
                check = 1
                break
        if check == 1:
            break
    if check == 1:
        continue
    for x in e[ans[-1]]:
        if x in ans[1:len(ans)-1]:
            ans = [] + ans[ans.index(x):]
            check = 1
            break

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    
print(-99999)

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(0, [0])
        if len(ans) != 0:
            break

if len(ans) == 0:
    print(-1)
    exit()
else:
    print(-222)

Submission status: Wrong Answer

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(0, [0])
        if len(ans) != 0:
            break

print(-222)
exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        if len(newkeiro) == len(set(newkeiro)):
          query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            return temp[temp.index(x):]
        else:
            ret = search_path(x, temp + [x])
            if len(ret) != 0:
                return ret
    return []

t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(0, [0])
        if len(ans) != 0:
            break

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

check = 1
while check == 1:
    check = 0
    #print(ans)
    for x in e[ans[0]]:
        if x == ans[1]:
            continue
        elif x in ans:
            ans = [] + ans[:ans.index(x)+1]
            check = 1
            break
    if check == 1:
        continue
    for i in range(1, len(ans)-1):
        for x in e[ans[i]]:
            if x == ans[0]:
                ans = [] + ans[:i+1]
                check = 1
                break
            elif x in ans[:i]:
                ans = [] + ans[ans.index(x):i+1]
                check = 1
                break
        if check == 1:
            break
    if check == 1:
        continue
    for x in e[ans[-1]]:
        if x in ans[1:len(ans)-1]:
            ans = [] + ans[ans.index(x):]
            check = 1
            break

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

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        if len(ans) == len(set(ans)):
          visit[parent] = True
          query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  query2 = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  visit = [False]*(n+2)
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        visit[parent] = True
        query2.append((len(ans),ans))
      else:
        newkeiro = keiro +str(chil)
        query.append((chil,newkeiro))
      if visit[parent]:
        break
  if not query2:
    print(-1)
  else:
    query2.sort()
    n,ans = query2[0]
    print(len(ans))
    for i in ans:
      print(int(i)+1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  array = [[] for _ in range(n)]
  query = deque([])
  for i in range(m):
    a,b = (int(i) for i in input().split())
    array[a-1].append(b-1)
    query.append((a-1,str(a-1)))
  while query:
    parent,keiro = query.popleft()
    for i in range(len(array[parent])):
      chil = array[parent][i]
      if str(chil) in keiro:
        #終了
        temp = keiro
        n = len(keiro)
        ans = ""
        ju = False
        for i in range(n):
          if keiro[i] == str(chil):
            ju = True
          if ju:
            ans += keiro[i]
        print(len(ans))
        for j in range(len(ans)):
          print(int(ans[j])+1)
        exit()
      newkeiro = keiro +str(chil)
      query.append((chil,newkeiro))
  print(-1)
solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
nowindex=-1
nowmin=114514
#print(G)
X=set()
for st in range(N):
    q=deque([st])
    before=[-1 for i in range(N)]
    dist=[-1 for i in range(N)]
    dist[st]=0
    flag=0
    while(len(q)>0):
        r=q.popleft()
        for p in G[r]:
            if dist[p]==-1:
                dist[p]=dist[r]+1
                before[p]=r
                q.append(p)
            elif dist[p]<=dist[r] and before[r]!=p:
                wt=dist[p]+dist[r]+1
                if nowmin>wt and wt>=3:
                    nowmin=wt
                    nowindex=st
                    #print(p,r,dist,before)
                    flag=1
                    X={st}
                    while(r!=st):
                        X.add(r)
                        r=before[r]
                    while(p!=st):
                        X.add(p)
                        p=before[p]
                    break
        if flag==1:
            break
print(len(X))
for i in X:
    print(i+1)