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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
graph = {i:[] for i in range(N)}
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  
Q = [i for i in range(N)]
p = [None for i in range(N)]
heiro = []
while Q:
  deru = [False for i in range(N)]
  Flag = 0
  s = Q.pop()
  if p[s] != None: continue
  p[s] = -1
  q = deque([s])
  while q:
    flag = 0
    x = q.popleft()
    for y in graph[x]:
      deru[x] = True
      if not deru[y]:
        p[y] = x
        q.append(y)
      else:
        p[y] = x
        now = x
        while now != y:
          heiro.append(now)
          now = p[now]
        heiro.append(y)
        flag = 1
        break
    if flag:
      Flag = 1
      break
  if Flag:
    break

def graph_size(g):
  ret = 0
  for k in g:
    ret += len(g[k])
  return ret
def squeeze(l):
  global graph
  edges = []
  subgraph = {k:[] for k in l}
  data = DD(lambda:DD(int))
  i = 0
  for k in l:
    for y in graph[k]:
      if y in l:
        subgraph[k].append(y)
        edges.append([0,k,y])
        data[k][y] = i
        i += 1
  graph = subgraph
  s = l[0]
  i = data[p[s]][s]
  edges[i][0] = 1
  now = p[s]
  heiro = [s]
  while now != s:
    heiro.append(now)
    i = data[p[now]][now]
    edges[i][0] = 1
    now = p[now]
  if len(heiro)==len(edges):
    print(len(heiro))
    for x in heiro:
      print(x+1)
    exit()
  else:
    for b,k,y in edges:
      if not b:
        p[y] = k
        now = p[y]
        heiro = [y]
        while now != y:
          heiro.append(now)
          now = p[now]
        squeeze(heiro)

if not heiro:
  print(-1)
else:
  squeeze(heiro)

Submission status: Time Limit Exceeded

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

def solve(G, p, ans, st, fst):
    cnt_1 = 0
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            return False
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst):
            return True
        st.remove(nxt)
    return False

def main():
    n, m = map(int, input().split())
    G = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].append(b)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def solve(G, p, ans, st, fst):
    cnt_1 = 0
    for nxt in G[p]:
        if nxt in st:
            cnt_1 += 1
    cnt_2 = 0
    for v in st:
        if p in G[v]:
            cnt_2 += 1
    if cnt_1 > 1 or cnt_2 > 1:
        return False
    elif cnt_1 == 1 and cnt_2 == 1:
        if fst in G[p]:
            for v in st:
                ans.append(v)
            return True
        else:
            return False
    for nxt in G[p]:
        st.add(nxt)
        if solve(G, nxt, ans, st, fst):
            return True
        st.remove(nxt)
    return False

def main():
    n, m = map(int, input().split())
    G = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        G[a].add(b)
    ans = []
    f = False
    st = set()
    for i in range(1, n+1):
        st.add(i)
        if solve(G, i, ans, st, i):
            f = True
            break
        st.remove(i)
    if f:
        print(len(ans))
        ans.sort()
        for v in ans:
            print(v)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


class Edge():

    def __init__(self, _to, _cost):
        self.to = _to
        self.cost = _cost


class Dijkstra():
    def __init__(self, V):

        self.G = [[] for i in range(V+1)]
        self._E = 0
        self._V = V

    @property
    def E(self):
        """ 辺数 """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        self.G[_from].append(Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):

        que = []
        heapq.heapify(que)
        d = [10**10] * (self._V+1)
        par = [-1] * (self._V + 1)
        d[s] = 0
        heapq.heappush(que, (0, s))

        while que:
            cost, v = heapq.heappop(que)
            if d[v] < cost:
                continue

            for e in self.G[v]:
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost
                    par[e.to] = v
                    heapq.heappush(que, (d[e.to], e.to))
        return d, par


N, M = map(int, input().split())
G = []
ans = []
now_dis = 10**6
for i in range(M):
    a, b = map(int, input().split())
    G.append((a, b))
for i in range(M):
    graph = Dijkstra(N)
    for j in range(M):
        if j != i:
            graph.add(G[j][0], G[j][1], 1)
    S, T = G[i][0], G[i][1]
    d, par = graph.shortest_path(T)
    if d[S]+1 < now_dis:
        now_dis = d[S]+1
        sub = []
        node = S
        while node != T:
            sub.append(node)
            node = par[node]
        sub.append(T)
        ans = sub

K=len(ans)
if K==0:
    print(-1)
    exit()
print(K)
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
# あっとこ
# ぴゅあ
from collections import deque
import sys
import heapq
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline().rstrip()

def negative_circle(s, G, n):
    dist = [10**20 for i in range(n+1)]
    dist[s] = 0
    for i in range(1, n+1):
        flag = False
        for some in G:
            a, b = some[0], some[1]
            newlen = dist[a] - 1
            if newlen < dist[b]:
                flag = True
                dist[b] = newlen

        if not flag:
            break
        if i == n:
            return True
    return False


N, M = map(int, input().split())
G = []
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    G.append((a, b))
    graph[a].append(b)

have_circle = negative_circle(1, G, N)


if not have_circle:
    print(-1)
    sys.exit()

visited = [False for i in range(N + 1)]
parent = [-1 for i in range(N+1)]
circle_part = []


def dfs(node):
    if visited[node]==True: pass
    visited[node] = True
    for child in graph[node]:
        if visited[child] == True:
            parent[child] = node
            circle_part.append(child)
            return
        else:
            parent[child] = node
            dfs(child)


for i in range(1,N+1):
    if visited[i] == False:
        dfs(i)

now_node = circle_part[0]
A = deque([])

now_node = circle_part[0]
A = deque([now_node])
while parent[now_node] != A[0]:
    now_node = parent[now_node]
    A.append(now_node)
A.reverse()
A.appendleft(A.pop())
def make_graph(G, A):
    A_set = set(A)
    graph_A = {A_node: [] for A_node in A}
    edge_A = []
    for x, y in G:
        if x in A_set and y in A_set:
            graph_A[x].append(y)
            edge_A.append((x, y))
    return graph_A, edge_A


graph_A, edge_A = make_graph(G, A)

while len(edge_A) != len(graph_A):
    # 条件を満たさない間
    P = set([(A[i-1], A[i]) for i in range(len(A))])
    S, E = 0, 0
    for pair in edge_A:
        if pair not in P:
            S, E = pair
            break
    visited = [False for i in range(N + 1)]
    circle_part = []
    dfs(E)
    A.clear()
    A = deque([S, E])
    now_node = S
    while parent[now_node] != E:
        now_node = parent[now_node]
        A.append(now_node)
    A.reverse()
    A.appendleft(A.pop())
    graph_A, edge_A = make_graph(G, A)

print(len(A))
for x in A:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    # 入次数0の節点を列挙
    in_deg = [0]*N
    for i in range(N):
        for to in E[i]:
            in_deg[to] += 1

    head = 0
    ans = [v for v in range(N) if in_deg[v] == 0]

    # 入次数0のものを順番に走査。同時に入次数を更新
    while head < len(ans):                  # O(V+E)
        v = ans[head]
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
        head += 1
    if len(ans) != N:
        return False
    return ans


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

    # print(rE)
    loop = Topological_sorting(E)
    if loop is not False:
        print(-1)
        return

    need = [1]*N
    while True:
        # 閉路を一つ探す。
        # グラフの単純化から始める
        # 入次数0の子はいらない子。
        # 出次数0の子はいらない子。

        in_deg = [0]*N
        out_deg = [0]*N
        for i in range(N):
            out_deg[i] = len(E[i])
            for to in E[i]:
                in_deg[to] += 1
        for i in range(N):
            if in_deg[i] == 0 or out_deg[i] == 0:
                need[i] = 0
        for i in range(N):
            if need[i] == 0:
                E[i] = []
            else:
                E[i] = [u for u in E[i] if need[u] == 1]

        # 答えがすでに得られているなら、
        # breakする。
        in_deg = [0]*N
        for i in range(N):
            for to in E[i]:
                in_deg[to] += 1
        cand = [i for i in range(N) if in_deg[i] > 1]
        # print("cand", cand, need)
        # print(E)
        if len(cand) == 0:
            break

        # 用いられない辺が存在するとのこと。
        # その終点からスタートする
        # 簡単に、入次数が1以上の点だ
        start = cand[0]
        q = [start]
        hist = set()
        while q:
            v = q[-1]
            hist.add(v)
            q.extend(E[v])
            if v == q[-1]:
                q.pop()
                hist.remove(v)
            loop = False
            for u in E[v]:
                if u in hist:
                    loop = True
                    break
            if loop:
                break
        # print("hist", hist)
        for i in range(N):
            if i not in hist:
                need[i] = 0
        # print(need)

    ans = [i for i, n in enumerate(need, start=1) if n == 1]
    print(len(ans))
    print(*ans, sep="\n")
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    # 入次数0の節点を列挙
    in_deg = [0]*N
    for i in range(N):
        for to in E[i]:
            in_deg[to] += 1

    head = 0
    ans = [v for v in range(N) if in_deg[v] == 0]

    # 入次数0のものを順番に走査。同時に入次数を更新
    while head < len(ans):                  # O(V+E)
        v = ans[head]
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
        head += 1
    if len(ans) != N:
        return False, ans
    return True, ans


def reversed_graph(E):
    rev = [[] for _ in E]
    for i, dest in enumerate(E):
        for t in dest:
            rev[t].append(i)
    return rev


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

    rE = reversed_graph(E)
    # print(rE)

    looped1, order1 = Topological_sorting(E)
    looped2, order2 = Topological_sorting(rE)
    # print(looped1, order1)
    # print(looped2, order2)

    if looped1 and looped2:
        print(-1)
        return

    nodes = set(range(N))-set(order1)-set(order2)
    # nodes内部でlevel-order-likeな探索が必要
    q = [list(nodes)[0]]
    seen = [0]*N
    prev = [-1]*N
    head = 0
    while head < len(q):
        v = q[head]
        seen[v] = 1
        poi = set()
        for u in E[v]:
            if u not in nodes:
                continue
            if seen[u] == 1:
                # ループ
                poi.add(u)
                prev[u] = v
                continue
            q.append(u)
            prev[u] = v
        if poi:
            # print(poi, v)
            ans = []
            while v not in poi:
                ans.append(v)
                v = prev[v]
            ans.append(v)
            break

        head += 1
    print(len(ans))
    print(*[a+1 for a in ans], sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    
    for i in range(M):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
    
    import queue
    use=[0]*N

    
    def bfs(a):
        #a=>aの最短距離を求める
        q=queue.Queue()
        q.put((a,-1,0))
        use[a]=1
        for i in range(N):
            use[i]=0
        
        while not(q.empty()):
            v,p,d=q.get()
            
            for nv in adj[v]:
                if nv==a:
                    return d+1
                else:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        return -1
    
    def bfs2(a):
        #aからaまでの
        #経路復元も
        P=[-1]*N
        q=queue.Queue()
        q.put((a,-1,0))
        for i in range(N):
            use[i]=0
        use[a]=1
        flag=0
        
        while not(q.empty()):
            if flag:
                break
            v,p,d=q.get()
            #print(v,p,d)
            P[v]=p

            for nv in adj[v]:
                #print("nv:",nv)
                if nv==a:
                    flag=1
                    break
                if nv!=p:
                    if use[nv]==0:
                        use[nv]=1
                        q.put((nv,v,d+1))
                            
        L=[]
        flag=1
        for i in range(N):
            #print(v)
            L.append(v)
            v=P[v]
            if v==a:
                L.append(a)
                break
        return L
        
                        
                        
        

    
    ans=N+1
    ansi=0

    for i in range(N):#全ての辺をなめる
        temp=bfs(i)#ここはab間の最短距離をbfsで求める
        if temp!=-1:
            if temp<ans:
                ans=temp
                ansi=i

    
    if ans==N+1:
        print(-1)
    else:
        print(ans)
        ans=bfs2(ansi)
        for i in ans:
            print(i+1)
        
        
        

main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    A=[0]*M
    B=[0]*M
    
    for i in range(M):
        A[i],B[i]=MI()
        A[i]-=1
        B[i]-=1
        adj[A[i]].append(B[i])
    
    import queue

    
    def bfs(a):
        #a=>aの最短距離を求める
        q=queue.Queue()
        q.put((a,-1,0))
        use=[0]*N
        use[a]=1
        while not(q.empty()):
            v,p,d=q.get()
            
            for nv in adj[v]:
                if nv==a:
                    return d+1
                else:
                    if nv!=p:
                        if use[nv]==0:
                            use[nv]=1
                            q.put((nv,v,d+1))
                            
        return -1
    
    def bfs2(a):
        #aからaまでの
        #経路復元も
        P=[-1]*N
        q=queue.Queue()
        q.put((a,-1,0))
        use=[0]*N
        use[a]=1
        flag=0
        
        while not(q.empty()):
            if flag:
                break
            v,p,d=q.get()
            #print(v,p,d)
            P[v]=p

            for nv in adj[v]:
                #print("nv:",nv)
                if nv==a:
                    flag=1
                    break
                if nv!=p:
                    if use[nv]==0:
                        use[nv]=1
                        q.put((nv,v,d+1))
                            
        L=[]
        flag=1
        for i in range(N):
            #print(v)
            L.append(v)
            v=P[v]
            if v==a:
                L.append(a)
                break
        return L
        
                        
                        
        

    
    ans=N+1
    ansi=0

    for i in range(N):#全ての辺をなめる
        temp=bfs(i)#ここはab間の最短距離をbfsで求める
        if temp!=-1:
            if temp<ans:
                ans=temp
                ansi=i

    
    if ans==N+1:
        print(-1)
    else:
        print(ans)
    
    
        
        ans=bfs2(ansi)
        for i in ans:
            print(i+1)
        
        
        

main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():    
    mod=10**9+7
    N,M=MI()
    adj=[[]for _ in range(N)]
    A=[0]*M
    B=[0]*M
    
    for i in range(M):
        A[i],B[i]=MI()
        A[i]-=1
        B[i]-=1
        adj[A[i]].append(B[i])
    
    def loop(n, X, i0,p0):
        # i0が根
        ans=[]
        
        st = [(~i0,p0), (i0,~p0)]

        while st:
            #頂点 i を見る
            
            (i,p) = st.pop()
            #print(i,ans,usedf,st)
            
            #帰り際の処理，ここを入れる場合，
            if i < 0:
                ans.pop()
                continue
            
            #行きがけの処理
            if i >= 0:
                if i==p0:
                    ans.append(p0)
                    break
                
                ans.append(i)
                
            for a in X[i][::-1]:
                if a!=p and a!=~p:
                    st.append((~a,(abs(i))))
                    st.append((a,abs(i)))
                    
        return ans

    ans=[1]*(N+1)
    la=N+1
    for i in range(M):
        temp=loop(N,adj,B[i],A[i])
        if temp!=[]:
            lt=len(temp)
            if lt<la:
                ans=[]
                la=lt
                for i in range(lt):
                    ans.append(temp[i])

    
    if la==(N+1):
        print(-1)
    else:
        print(la)
        for i in ans:
            print(i+1)
        
        

main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit, s):
    if impossible[v]:
        return []
    s = s | {v}
    visit = visit + [v]
    if len(visit) > n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in s:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit, s)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [], set())
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N
n = [N]


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    if len(visit) > n[0]:
        return []
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < n[0]:
                ans = t
                n[0] = len(ans)
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

# input
N, M = LI()
AB = [LI() for _ in range(M)]

# params
link = [[] for _ in range(N)]
for a, b in AB:
    link[a - 1].append(b - 1)
impossible = [False] * N


def joint(v, visit):
    if impossible[v]:
        return []
    visit = visit + [v]
    ans = []
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        impossible[v] = True
    return ans


def main():
    ans = []
    for i in range(N):
        t = joint(i, [])
        if 0 < len(t):
            if ans == [] or 0 < len(t) < len(ans):
                ans = t
    if ans == []:
        print(-1)
        return
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

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

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                if ns[u]&us-set([nu]):
                    for v in ns[u]&us-set([nu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update or len(us)==len(hist):
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)

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

seen = [False] * n
done = [False] * n
hist = []
def dfs(u, pos):
    # uからdfs
    seen[u] = True
    hist.append(u)
    for v in ns[u]:
        if done[v]:
            continue
        elif seen[v]:
            # サイクルを検出
            pos = v
            return pos
        else:
            pos = dfs(v, pos)
            if pos>=0:
                return pos
    done[u] = True
    hist.pop()
    return pos
    
for u in range(n):
    pos = dfs(u, -1)
    if pos>=0:
        while True:
            us = set(hist)
            update = False
            for i,u in enumerate(hist):
                nu = hist[(i+1)%len(hist)]
                if ns[u]&us-set([nu]):
                    for v in ns[u]&us-set([nu]):
                        break
                    j = hist.index(v)
                    if i<j:
                        hist = hist[i:] + hist[:j+1]
                    else:
                        hist = hist[j:i+1]
                    update = True
                    break
            if not update:
                break
        print(len(hist))
        write("\n".join(map(lambda x: str(x+1), hist)))
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

graph=[set() for _ in range(N+1)]
for _ in range(M):
  A,B=map(int,input().split())
  graph[A].add(B)
#print(graph)

visited=[False]*(N+1)
def dfs(path):
  u=path[-1]
  visited[u]=True
  for v in graph[u]:
    if visited[v]:
      if path[0]==v:
        cycle_list.append(path+[v])
    else:
      dfs(path+[v])
  visited[u]=False

cycle_list=[]
for i in range(1,N+1):
  dfs([i])
  
#print(cycle_list)
for cycle in cycle_list:
  #print(cycle)
  cycle_set=set(cycle)
  for c in cycle:
    edge_subs=set()
    if len(cycle_set&graph[c])>1:
      break
  else:
    print(len(cycle)-1)
    for i in range(len(cycle)-1):
      print(cycle[i])
    break
else:
  print(-1)