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:
def examA():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """
        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]
    X.append([0,V,D])
    X.append([L,0,0])
    X.sort()
    V = [[]for _ in range(N+2)]
    for i in range(N+1):
        x1, v1, d1 = X[i]
        r = x1 + d1
        for j in range(i+1,N+2):
            x2, v2, d2 = X[j]
            if r<x2:
                break
            cost = (x2-x1)/v1
            V[i].append((j,cost))

    dij = Dijkstra(V, 0)
    ans = dij.dist[-1]
    if ans>=inf:
        print("impossible")
        return
    print('{:.18f}'.format(ans))
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    # 参考 https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61
    def cycle(neighbor, start, ring_size, node):
        visited = [False]*node
        stack = []
        stack.append([start])
        visited[start] = True
        while (stack):
            curr_path = stack.pop()
            check = deepcopy(curr_path)
            check = set(check)
            if len(curr_path) > ring_size:
                continue
            # print curr_path
            last = curr_path[-1]
            for nei in neighbor[last]:
                if nei in check:
                    if len(curr_path)==0:
                        continue
                    if (len(curr_path) <= ring_size) and (curr_path[0] == nei):
                        new_path = copy(curr_path)
                        return new_path
                    elif (len(curr_path) < ring_size):
                        return cycle(neighbor,nei,ring_size,node)
                if visited[nei]:
                    continue
                visited[nei] = True
                new_path = copy(curr_path)
                new_path.append(nei)
                stack.append(new_path)
        return -1
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
    #print(V)
    loop = -1
    for i in range(N):
        loop = cycle(V,i,N,N)
        if loop!=-1:
            break
    if loop==-1:
        print(-1)
        return
    while(True):
        next = -1
        for k in loop:
            next = cycle(V,k,len(loop)-1,N)
            if next != -1:
                break
        if next==-1:
            break
        loop = next

    ans = loop
    print(len(ans))
    for v in ans:
        print(v+1)
    return

import sys,bisect,itertools,heapq,math,random
from copy import copy,deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """
        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]
    X.append([0,V,D])
    X.append([L,0,0])
    X.sort()
    V = [[]for _ in range(N+2)]
    for i in range(N+1):
        x1, v1, d1 = X[i]
        r = x1 + d1
        for j in range(i+1,N+2):
            x2, v2, d2 = X[j]
            if r<x2:
                break
            cost = (x2-x1)/v1
            V[i].append((j,cost))

    dij = Dijkstra(V, 0)
    ans = dij.dist[-1]
    if ans>=inf:
        print("impossible")
        return
    print('{:.18f}'.format(ans))
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    # 参考 https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61
    def cycle(neighbor, start, ring_size):
        stack = []
        stack.append([start])
        while (stack):
            curr_path = stack.pop()
            check = set(curr_path)
            if len(curr_path) > ring_size:
                continue
            # print curr_path
            last = curr_path[-1]
            for nei in neighbor[last]:
                if nei in check:
                    if (0 < len(curr_path) < ring_size) and (curr_path[0] == nei):
                        new_path = copy(curr_path)
                        new_path.append(nei)
                        return new_path

                new_path = copy(curr_path)
                new_path.append(nei)
                stack.append(new_path)
        return -1
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
    loop = -1
    for i in range(N):
        loop = cycle(V,i,N+1)
        if loop!=-1:
            break
    if loop==-1:
        print(-1)
        return
    while(True):
        next = -1
        for k in loop:
            next = cycle(V,k,len(loop)-1)
            if next != -1:
                break
        if next==-1:
            break
        loop = next

    ans = loop
    print(len(ans)-1)
    for v in ans[:len(ans)-1]:
        print(v+1)
    return

import sys,bisect,itertools,heapq,math,random
from copy import copy,deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

Submission status: Time Limit Exceeded

Solution code:
def examA():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """
        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]
    X.append([0,V,D])
    X.append([L,0,0])
    X.sort()
    V = [[]for _ in range(N+2)]
    for i in range(N+1):
        x1, v1, d1 = X[i]
        r = x1 + d1
        for j in range(i+1,N+2):
            x2, v2, d2 = X[j]
            if r<x2:
                break
            cost = (x2-x1)/v1
            V[i].append((j,cost))

    dij = Dijkstra(V, 0)
    ans = dij.dist[-1]
    if ans>=inf:
        print("impossible")
        return
    print('{:.18f}'.format(ans))
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    # 参考 https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61
    def cycle(neighbor, start, ring_size):
        stack = []
        stack.append([start])
        while (stack):
            curr_path = stack.pop()
            if len(curr_path) > ring_size:
                continue
            # print curr_path
            last = curr_path[-1]
            for nei in neighbor[last]:
                if nei in curr_path:
                    if (0 < len(curr_path) < ring_size) and (curr_path[0] == nei):
                        new_path = copy(curr_path)
                        new_path.append(nei)
                        return new_path

                new_path = copy(curr_path)
                new_path.append(nei)
                stack.append(new_path)
        return -1
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
    loop = -1
    for i in range(N):
        loop = cycle(V,i,N+1)
        if loop!=-1:
            break
    if loop==-1:
        print(-1)
        return
    while(True):
        next = -1
        for k in loop:
            next = cycle(V,k,len(loop)-1)
            if next != -1:
                break
        if next==-1:
            break
        loop = next

    ans = loop
    print(len(ans)-1)
    for v in ans[:len(ans)-1]:
        print(v+1)
    return

import sys,bisect,itertools,heapq,math,random
from copy import copy,deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
c = [[[] for i in range(n)] for j in range(n)]
ans = [-1]
cycle = [0]*(n+1)
for k in range(m):
  a, b = map(int, input().split())
  c[a-1][b-1] = [b]
  for i in range(n):
    if c[i][a-1] != [] and (c[i][b-1]==[] or len(c[i][b-1]) > len(c[i][a-1])+1):
      c[i][b-1] = c[i][a-1] + [b]
  d = c[b-1][b-1]
  if d != [] and len(d) < len(cycle):
    cycle = d
if len(cycle) < n+1:
  ans = [len(cycle)] + cycle
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
c = [[[] for i in range(n)] for j in range(n)]
ans = [-1]
for k in range(m):
  a, b = map(int, input().split())
  c[a-1][b-1] = [b]
  for i in range(n):
    if c[i][b-1] == []:
      for j in range(n):
        if c[i][j] != [] and c[i][j][-1] == a:
          c[i][b-1] = c[i][j] + [b]
          break
    if c[b-1][b-1] != []:
      ans = [len(c[b-1][b-1])] + c[b-1][b-1]
      break
[print(i) for i in ans]

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):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)


def bfs(node):
    seen = [0] * n
    todo = deque([])
    for to in edges[node]:
        todo.append([to, 1, {to}])

    while todo:
        now, distance, path = todo.popleft()
        seen[now] = distance
        if now == node:
            return distance, path

        for next_node in edges[now]:  # type: int
            if seen[next_node] != 0:
                continue
            new_path = path | {next_node}
            todo.append([next_node, distance + 1, new_path])

    return float('INF'), set()


cycle_size = [float('INF')] * n
cycle_nodes = [set()] * n

for i in range(n):
    cycle_size[i], cycle_nodes[i] = bfs(i)

mini_cycle = min(cycle_size)
if mini_cycle == float('INF'):
    print(-1)
else:
    idx = cycle_size.index(mini_cycle)
    ans = cycle_nodes[idx]
    print(mini_cycle)
    for node in ans:
        print(node+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1;
        A[a][b]=1
    next=[list(range(n)) for _ in range(n)]
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        if(A[i][j]>A[i][k]+A[k][j]):
            A[i][j]=A[i][k]+A[k][j]
            next[i][j]=next[i][k]
    length=n+1
    v=-1
    for i in range(n):
        if(length>A[i][i]):
            length=A[i][i]
            v=i
    if(v==-1):
        print(-1)
        return
    print(length)
    print(v+1)
    u=next[v][v]
    while(u!=v):
        print(u+1)
        u=next[u][v]
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    A=[[INF]*n for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        A[a][b]=1
    # Warshall-Floyd
    B=[a[:] for a in A] # deep copy
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    # output
    length=INF
    index=-1
    for i in range(n):
        if(length>B[i][i]):
            length=B[i][i]
            index=i
    if(length==INF):
        print(-1)
        return
    # path restroration
    u=v=index
    path=[]
    while(B[u][v]!=A[u][v]):
        for w in range(n):
            if(B[u][v]==A[u][w]+B[w][v]):
                u=w
                path.append(w)
                break
    path.append(v)
    print(len(path))
    for v in path: print(v+1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

g = [[] for _ in range(1005)]

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

vis = [0] * 1005


def dfs(x, p):
    if vis[x]:
        return []
    p.append(x)
    vis[x] = 1
    for v in g[x]:
        if v in p:
            return p
        t = dfs(v, p)
        if len(t):
            return t
    p.pop()
    return []


tmp = 0
ans = 10 ** 10
tmpp = []
p = []
vs = [0] * 1005


def dfs2(x):
    global ans, p, tmp, tmpp
    if len(p) >= ans:
        return
    p.append(x)
    for v in g[x]:
        if v == tmp:
            ans = len(p)
            tmpp = p[:]
            continue
        if not vs[v]:
            vs[v] = 1
            dfs2(v)
            vs[v] = 0
    p.pop()


a = []
for i in range(1, 1 + n):
    tmp = i
    p = []
    dfs2(i)
    if len(tmpp) == ans:
        a = tmpp[:]

if not len(a):
    print(-1)
    exit(0)

print(len(a))
for i in a:
    print(i)

#
# pre = t[0]
# next = [0] * 1005
# for i in range(1, len(t)):
#     now = t[i]
#     next[pre] = now
#     pre = now
# next[t[-1]] = t[0]
# s = set()
# for i in t:
#     s.add(i)
#
# cnt = 0
# now = t[0]
# while cnt < len(s):
#     cnt += 1
#     for i in g[now]:
#         if i == next[now]:
#             continue
#         if i in s:
#             cnt = 0
#             k = next[now]
#             while k != i:
#                 s.remove(k)
#                 k = next[k]
#             next[now] = i
#     now = next[now]
#
# print(len(s))
# for i in s:
#     print(i)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
A = []
S = [[] for _ in range(M)]
q = [[] for _ in range(N)]
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  S[m] = a
  q[a-1].append(b)

S = set(S)
A = [a for a in A if (a[0] in S) and (a[1] in S)]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N-1):
  for x in X:
    for v in q[x[-1]-1]:
      if v in x:  
          ans.append(x+[v])
          ans[0] = [len(ans[0])-1] + ans[0]
          print(*ans[0][:-1])
          import sys
          sys.exit()
      else:
          #XX.append(x + [v[1]])
          XX[i] = x + [v]
          i += 1
      X = [x for x in XX if x]


print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = map(int,input().split())
A = []
S = [[] for _ in range(M)]
 
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  S[m] = a

S = set(S)
A = [a for a in A if (a[0] in S) and (a[1] in S)]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N-1):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        ans[0] = [len(ans[0])-1] + ans[0]
        print(*ans[0][:-1])
        import sys
        sys.exit()
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


print(-1)

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 = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
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]])
        ans[0] = [len(ans[0])-1] + ans[0]
        print(*ans[0][:-1])
        import sys
        sys.exit()
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


print(-1)

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 = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
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]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.group = None
    self.active = False

  def search(self, group, path=[]):
    self.group = group
    self.active = True
    path.append(self)

    for edge in self.edges:
      if edge.active:
        return path[path.index(edge):]
      elif edge.group is not None:
        continue

      cycle = edge.search(path)

      if cycle is not None:
        return cycle

    self.active = False
    path.pop()

    return None

  def __hash__(self):
    return self.idx

  def __repr__(self):
    return str(self)

  def __str__(self):
    return 'node({})'.format(self.idx + 1)


def main():
  n, m = map(int, input().split())
  nodes = [Node(i) for i in range(n)]

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

  for i, node in enumerate(nodes):
    if node.group is None:
      cycle = node.search(i)

    if cycle is not None:
      break

  if cycle is None:
    print(-1)
    return

  while True:
    nodes = set(cycle)
    found = None

    for i, node in enumerate(cycle):
      node.edges = [e for e in node.edges if e in nodes]

      if found is None and len(node.edges) != 1:
        found = i

    if found is None:
      break

    edge = cycle[found].edges[0]

    if edge == cycle[(found + 1) % len(cycle)]:
      edge = cycle[found].edges[1]

    index = cycle.index(edge)

    if index < found:
      cycle = cycle[index:found + 1]
    else:
      cycle = cycle[found:index + 1]

  print(len(cycle))
  for node in cycle:
    print(node.edges[0].idx + 1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.group = None
    self.active = False

  def search(self, group, path=[]):
    self.group = group
    self.active = True
    path.append(self)

    for edge in self.edges:
      if edge.active:
        return path[path.index(edge):]
      elif edge.group is not None:
        continue

      cycle = edge.search(path)

      if cycle is not None:
        return cycle

    self.active = False
    path.pop()

    return None

  def __repr__(self):
    return str(self)

  def __str__(self):
    return 'node({})'.format(self.idx + 1)


def main():
  n, m = map(int, input().split())
  nodes = [Node(i) for i in range(n)]

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

  for i, node in enumerate(nodes):
    if node.group is None:
      cycle = node.search(i)

    if cycle is not None:
      break

  if cycle is None:
    print(-1)
    return

  while True:
    nodes = set(cycle)
    found = None

    for i, node in enumerate(cycle):
      node.edges = [e for e in node.edges if e in nodes]

      if found is None and len(node.edges) != 1:
        found = i

    if found is None:
      break

    edge = cycle[found].edges[0]

    if edge == cycle[(found + 1) % len(cycle)]:
      edge = cycle[found].edges[1]

    index = cycle.index(edge)

    if index < found:
      cycle = cycle[index:found + 1]
    else:
      cycle = cycle[found:index + 1]

  print(len(cycle))
  for node in cycle:
    print(node.edges[0].idx + 1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.group = None
    self.active = False

  def search(self, group, path=[]):
    self.group = group
    self.active = True
    path.append(self)

    for edge in self.edges:
      if edge.active:
        return path[path.index(edge):]
      elif edge.group is not None:
        continue

      cycle = edge.search(path)

      if cycle is not None:
        return cycle

    self.active = False
    path.pop()

    return None

  def __repr__(self):
    return str(self)

  def __str__(self):
    return 'node({})'.format(self.idx + 1)


def main():
  n, m = map(int, input().split())
  nodes = [Node(i) for i in range(n)]

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

  for i, node in enumerate(nodes):
    if node.group is None:
      cycle = node.search(i)

    if cycle is not None:
      break

  if cycle is None:
    print(-1)
    return

  while True:
    nodes = set(cycle)
    found = None

    for i, node in enumerate(cycle):
      node.edges = [e for e in node.edges if e in nodes]

      if found is None and len(node.edges) != 1:
        found = i

    if found is None:
      break

    edge = [e for e in cycle[found].edges if e != cycle[(found + 1) % len(cycle)]][0]
    index = cycle.index(edge)

    if index < found:
      cycle = cycle[index:found + 1]
    else:
      cycle = cycle[found:index + 1]

  print(len(cycle))
  for node in cycle:
    print(node.edges[0].idx + 1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import bellman_ford
N, M = [int(i) for i in input().split()]
rows = []
cols = []
weights = []

for _ in range(M):
    # u v 間のコスト
    u, v = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(-1)

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
for i in range(N):
    try:
        d1 = bellman_ford(graph, indices = [i], directed=True, unweighted=False)
    except:
        print(0)
        exit()
else:
    print(-1)

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 m,v in itertools.product(range(len(X)),A):
    if X[m][-1] == v[0]:
      if v[1] in X[m]:
        ans.append(X[m]+[v[1]])
        break
      else:
        XX.append(X[m] + [v[1]])
  if len(XX) == 0:break
  X = XX

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