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: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  #X[m] = X[m] + [a] + [b]

ans = []
XX = []
X = A.copy()
for _ in range(N):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        break
      else:
        XX.append(x + [v[1]])
    X = XX

if ans == []:
  print(-1)
else:
  ans[0] = [len(ans[0])-1] + ans[0]
  print(*ans[0][:-1])

Submission status: Time Limit Exceeded

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

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

vs = set()
def dfs_w(v, d):
    # dfs while版 
    vs.add(v)
    pvs = set([v])
    stack = [v]
    path = []
    while True:
        if len(stack) == 0:
            break
        v = stack.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                vs.add(u)
                pvs.add(u)
                stack += [-v, u]
    return False

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

for i in range(N):
    i += 1
    if i in vs:
        continue
    loop = dfs_w(i, d)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

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

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float('inf')

n, m = map(int, raw_input().strip().split())

g = [[] for i in xrange(n + 1)]

for _ in xrange(m):
    u, v = map(int, raw_input().strip().split())
    g[u].append(v)

ans = INF

# run bfs from eaxch vertex to
# determine the smallest cycle containing that vertex
# TC = O(|V| * |E|)

vis = [0] * (n + 1)
dist = [0] * (n + 1)
par = [0] * (n + 1)

cycle = []

def bfs(v):
    global ans, vis, dist, cycle
    
    flag = 0 # cycle not found
    
    q = deque([v])
    vis[v] = 1

    while q:
        u = q.popleft()
        for child in g[u]:
            if (vis[child]):
                if (child == v):

                    cur = dist[u] + 1
                    if cur < ans:
                        ans = cur

                        # fill the cycle list
                        cycle = []
                        
                        cycle.append(str(u))
                        vertex = u
                        while vertex != v:                            
                            vertex = par[vertex]
                            cycle.append(str(vertex))

                    else: pass

                    # cycle found, break                    
                    flag = 1
                    break
            
            vis[child] = 1
            dist[child] = dist[u] + 1
            par[child] = u
            
            q.append(child)

        if flag: break

for v in xrange(1, n + 1):
    bfs(v)

    if (v == n): break
    
    for i in xrange(n + 1): vis[i] = dist[i] = par[i] = 0

if (ans == INF):
    print -1
else:
    print ans
    print '\n'.join(cycle)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)

for start in range(N):
    st = deque([(start, True)])
    L = deque()
    V = set()

    while st:
        now, isFirst = st.pop()
        if isFirst:
            L.append(now)

            if now in V:
                if now == start:
                    break

            V.add(now)

            st.append((now, False))

            for to in edges[now]:
                st.append((to, True))
        else:
            L.pop()
            V.remove(now)
    else:
        continue

    if L[-1] != L[0]:
        continue

    L.pop()
    print(len(L))
    ans = [v + 1 for v in L]
    print(*ans, sep='\n')
    exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
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, src, dst, weight=1):
        self.graph[src].append((dst, weight))

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


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        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, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]


for i in range(M):
    u, v = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, 1)
    g.add_edge(u-1+N, v-1, 1)
    g.add_edge(u-1, v-1+N, 1)

d = Dijkstra(g, 0)

ans_n = 10 ** 6
ans_index = -1
for i in range(N):
    d = Dijkstra(g, i)
    ans_n_ = d.dist[i+N]

    if ans_n_ < ans_n:
        ans_index = i
        ans_n = ans_n_

if ans_n == 10 ** 6:
    print(-1)
else:
    d = Dijkstra(g, ans_index)
    ans = d.shortest_path(ans_index + N)
    ans.sort()
    print(ans_n)
    for j in range(ans_n):
        print(ans[j]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
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
                break
            if y in xvisited:
                break
            yroute = copy.copy(xroute)
            yvisited = copy.copy(xvisited)
            nexts.append((y, yroute, yvisited))
        if found:
            result = xroute
            break
    return result

heiro = []
for i in range(1, n+1):
    res = searchRoute(i)
    if len(res) > 0:
        heiro = res
        break

if len(heiro) == 0:
    print(-1)
    exit()
while True:
    visited = set()
    bp = [-1, -1]
    rt = defaultdict(int)
    for i in range(len(heiro)):
        visited.add(heiro[i])
        rt[heiro[i]] = i
        for j in adj[heiro[i]]:
            if j in visited and not (i == len(heiro) - 1 and j == heiro[0]):
                bp = [i, rt[j]]
                break
        if bp[0] != -1:
            break
    if bp[0] == -1:
        print(len(heiro))
        for i in heiro:
            print(i)
        exit()
    heiro = heiro[bp[1]:bp[0]+1]

Submission status: Time Limit Exceeded

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
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            ans = [] + temp[temp.index(x):]
            check = 1
            while check == 1:
                check = 0
                #print(ans)
                for i in range(len(ans)-1):
                    for z in e[ans[i]]:
                        if z == ans[i+1]:
                            continue
                        elif z in ans:
                            t = ans.index(z)
                            if t < i:
                                ans = [] + ans[t:i+1]
                            else:
                                ans = [] + ans[i:t+1]
                            #print(ans, z)
                            check = 1
                            break
                    if check == 1:
                        break
                    else:
                        e[ans[i]] = []
                if check == 1:
                    continue
                for z in e[ans[-1]]:
                    if z == ans[0]:
                        continue
                    elif z in ans:
                        ans = [] + ans[ans.index(z):]
                        check = 1
                        #print(z, ans)
                        break
            print(len(ans))
            for z in ans:
                print(z+1)
            exit()
        else:
            search_path(x, temp + [x])


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

print(-1)

Submission status: Time Limit Exceeded

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
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            ans = [] + temp[temp.index(x):]
            check = 1
            while check == 1:
                check = 0
                #print(ans)
                for i in range(len(ans)-1):
                    for z in e[ans[i]]:
                        if z == ans[i+1]:
                            continue
                        elif z in ans:
                            t = ans.index(z)
                            if t < i:
                                ans = [] + ans[t:i+1]
                            else:
                                ans = [] + ans[i:t+1]
                            #print(ans, z)
                            check = 1
                            break
                    if check == 1:
                        break
                if check == 1:
                    continue
                for z in e[ans[-1]]:
                    if z == ans[0]:
                        continue
                    elif z in ans:
                        ans = [] + ans[ans.index(z):]
                        check = 1
                        #print(z, ans)
                        break
            print(len(ans))
            for z in ans:
                print(z+1)
            exit()
        else:
            search_path(x, temp + [x])


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

print(-1)

Submission status: Time Limit Exceeded

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
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            ans = [] + temp[temp.index(x):]
            check = 1
            while check == 1:
                check = 0
                #print(ans)
                for i in range(len(ans)-1):
                    for z in e[ans[i]]:
                        if z == ans[i+1]:
                            continue
                        elif z in ans:
                            t = ans.index(z)
                            if t < i:
                                ans = [] + ans[t:i+1]
                            else:
                                ans = [] + ans[i:t+1]
                            #print(ans, z)
                            check = 1
                            break
                    if check == 1:
                        break
                if check == 1:
                    continue
                for z in e[ans[-1]]:
                    if z in ans[1:]:
                        ans = [] + ans[ans.index(z):]
                        check = 1
                        #print(z, ans)
                        break
            print(len(ans))
            for z in ans:
                print(z+1)
            exit()
        else:
            search_path(x, temp + [x])


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

print(-1)

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
flg = 0
lst = list(range(N))
ans = -1
for i in range(N):
    for w in lst:
        vis = [1] * N
        s = dfs(w)
        if s != -1:
            flg = 1
            dq = deque()
            p = [-1] * N
            for v in es[s]:
                dq.append(v)
                p[v] = s
            while len(dq) > 0:
                v = dq.popleft()
                if v == s:
                    break
                for u in es[v]:
                    if p[u] == -1:
                        dq.append(u)
                        p[u] = v
            tmp = [s]
            v = p[v]
            while v != s:
                tmp.append(v)
                v = p[v]
            if ans == -1 or len(tmp) < len(ans):
                ans = tmp
                lst = tmp[1:]
if flg:
    print(len(ans))
    for x in ans:
        print(x+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import queue
N, M = map(int, input().split())
E = [set() for i in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  E[A].add(B)
def sub():
  for start in range(N):
    q = queue.Queue()
    q.put((start, {start}))
    while not q.empty():
      c, s = q.get()
      ns = E[c]
      s2 = s&ns
      if s2 and s2 != {start}:
        continue
      for n in ns:
        if n == start:
          return s
        q.put((n, s|{n}))
  return {}
S = sub()
if S == {}:
  print(-1)
  exit()
print(len(S))
for i in S:
  print(i+1)

Submission status: Time Limit Exceeded

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

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([v])
    nvs = [v]
    path = [v]
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

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

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()
v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = -1
    for u in d[v]:
        if u in pvs:
            f = True
            nloop.append(u)
            break
        if v2i[v] > v2i[u]:
            continue
        max_i = max(v2i[u], max_i)
    if f:
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
def DFS(graph, loc, visited=[], ans=[]):
    if loc in visited:
#         print(visited)
        if loc == visited[0]:
#             return visited
            ans.append(visited)
            return True
        else:
            return False
    
    new_visited = [it for it in visited]
    new_visited.append(loc)
    next_locs = graph[loc]
    
    for it in next_locs:
        DFS(graph, it, new_visited, ans=ans)

    return []


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

total_ans = []
for i in range(n):
    ans = []
    DFS(graph, i, ans=ans)
    total_ans += ans

if len(total_ans) == 0:
    print(-1)
else:
    min_cycle = total_ans[0]
    for it in total_ans:
        if len(min_cycle) > len(it):
            min_cycle = it
    print(len(min_cycle))
    for it in min_cycle:
        print(it+1)

Submission status: Time Limit Exceeded

Solution code:
def DFS(graph, loc, visited=[]):
    if loc in visited:
#         print(visited)
        if loc == visited[0] and checkGraph(graph, visited):
            return visited
        else:
            return []
    
    new_visited = [it for it in visited]
    new_visited.append(loc)
    next_locs = graph[loc]
    
    for it in next_locs:
        ret = DFS(graph, it, new_visited)
        if len(ret) > 0:
            return ret
        
    return []

def checkGraph(graph, nodes):
    for node in nodes:
        cnt = 0
        for it in graph[node]:
            if it in nodes:
                cnt+=1
        if cnt!=1:
            return False
    return True


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

ans = -1
for i in range(n):
    ret = DFS(graph, i)
    if len(ret) > 0:
        ans = ret
        break
        
if ans==-1:
    print(ans)
else:
    print(len(ans))
    for it in ans:
        print(it+1)

Submission status: Time Limit Exceeded

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-1].add(A-1)

for s in range(N):
    states_pool = deque()
    states_pool.append((s,set({}),set(range(N))-set({s})))
    while states_pool:
        u, chain, remain = states_pool.pop()
        if s in uv[u] and len(chain):
            print(len(chain)+1)
            for c in chain:
                print(c+1)
            print(u+1)
            exit()
        else:
            new_remain = remain.copy()
            if u != s: new_remain -= vu[u]
            candidates = new_remain & uv[u]
            new_remain -= uv[u]
            new_chain = chain.copy()
            new_chain.add(u)
            for c in candidates:
                states_pool.append((c, new_chain, new_remain))
    for i in range(s+1,N):
        uv[i].discard(s)
print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
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-1].add(A-1)

for s in range(N):
    dfs_stack = [(s,set({}),set(range(N))-set({s}))]
    while dfs_stack:
        u, chain, remain = dfs_stack.pop()
        if s in uv[u] and len(chain):
            print(len(chain)+1)
            for c in chain:
                print(c+1)
            print(u+1)
            exit()
        else:
            new_remain = remain.copy()
            if u != s: new_remain -= vu[u]
            candidates = new_remain & uv[u]
            new_remain -= uv[u]
            new_chain = chain.copy()
            new_chain.add(u)
            for c in candidates:
                dfs_stack.append((c, new_chain, new_remain))
    for i in range(s+1,N):
        uv[i].discard(s)
print(-1)

Submission status: Time Limit Exceeded

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

e_list = [[] for i in range(N)]
es = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a,b = a-1,b-1
    es.append((a,b))
    e_list[a].append((b,1))

import heapq
flag=False
min_d = 10**27
for vg,vi in es:
    #dijkstra
    #you need to prepare e_list = [[orient,dist]]
    
    min_d_list = [10**27 for i in range(N)]
    min_d_list[vi] = 0
    prev_list = [-1 for i in range(N)]
    q = []
    for i in range(N):
        heapq.heappush(q,[min_d_list[i],i])
    
    while len(q)>0:
        d,v = heapq.heappop(q)
        for e in e_list[v]:
            v1,d1=e
            if v!=vg or v1!=vi:
                if min_d_list[v1]>d+d1:
                    min_d_list[v1]=d+d1
                    prev_list[v1]=v
                    heapq.heappush(q,[d+d1,v1])
    if min_d_list[vg]<min_d:
        flag=True
        min_vi = vi
        min_vg = vg
        min_d = min_d_list[vg]
        min_prev = prev_list
            
#print(min_d_list)
if flag:
    ans = []
    v = min_vg
    while v!=min_vi:
        ans.append(v+1)
        v=min_prev[v]
    ans.append(min_vi+1)
    ans = ans[::-1]
    
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

e_list = [[] for i in range(N)]

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

import heapq
flag=False
min_d = 10**27
for vg in range(N):
    for vi,_ in e_list[vg]:
        #dijkstra
        #you need to prepare e_list = [[orient,dist]]
        
        min_d_list = [10**27 for i in range(N)]
        min_d_list[vi] = 0
        prev_list = [-1 for i in range(N)]
        q = []
        for i in range(N):
            heapq.heappush(q,[min_d_list[i],i])
        
        while len(q)>0:
            d,v = heapq.heappop(q)
            for e in e_list[v]:
                v1,d1=e
                if v!=vg or v1!=vi:
                    if min_d_list[v1]>d+d1:
                        min_d_list[v1]=d+d1
                        prev_list[v1]=v
                        heapq.heappush(q,[d+d1,v1])
        if min_d_list[vg]<min_d:
            flag=True
            min_vi = vi
            min_vg = vg
            min_d = min_d_list[vg]
            min_prev = prev_list
            
#print(min_d_list)
if flag:
    ans = []
    v = min_vg
    while v!=min_vi:
        ans.append(v+1)
        v=min_prev[v]
    ans.append(min_vi+1)
    ans = ans[::-1]
    
    print(len(ans))
    for a in ans:
        print(a)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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


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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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 = [tuple([i]) for i in range(n)]
    res = []
    tank = []
    res2 = -1

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

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    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 = []
    tank = []
    res2 = -1

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

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

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

if __name__ == '__main__':
    main()