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:
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 = []
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)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def hersCode(L, n):
  #if L[-1] < n:
  #  return len(L)
  ok = 0
  ng = len(L)
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] <= n:
      ok = mid
    else:
      ng = mid
  return ok

def answer(T):
  print(len(T))
  for i in T:
    print(i)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

L = {}
R = {}
for i in range(M):
  a, b = AB[i]
  if a in L:
    L[a].append(b)
  else:
    L[a] = [b]
  if b in R:
    R[b].append(a)
  else:
    R[b] = [a]

def nasu(g, n, r, P):
  if n in R:
    for i in R[n]:
      if i in P and i != r:
        return None
  if n not in L:
    return None
  k = L[n]
  for i in k:
    if i in P and i != g:
      return None
  if g in k:
    return P
  for i in k:
    if i < g:
      continue
    if i in P:
      continue
    T = nasu(g, i, n, P + [i])
    if T:
      return T
  return None

  

for i in range(1, N):
  T = nasu(i, i, 0, [i])
  if T:
    answer(T)
    exit()
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)
    rg = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        rg[b].add(a)
    
    def ok(v):
        v = set(v)
        for u in v:
            if not(len(v & g[u]) == 1 and len(v & rg[u]) == 1):
                return False
        return True

    def dfs(u):
        su = set(u)
        for v in g[u[-1]]:
            if v == u[0]:
                if ok(u):
                    return u
                else:
                    return []
            elif v in su:
                return []
            u.append(v)
            ret = dfs(u)
            if ret:
                return ret
            u.pop()
        
        return []

    for i in range(1, N+1):
        v = dfs([i])
        if v:
            print(len(v))
            for u in v:
                print(u)
            return

    print(-1)


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    (slv(N, M, AB))

    # N = 1000
    # M = 2000
    # AB = set()
    # while len(AB) != M:
    #     AB.add((random.randint(1, N+1), random.randint(1, N+1)))
    # print('start')
    # (slv(N, M, AB))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

    route.reverse()
    return route

inf = float('inf')

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

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

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

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

kouho = []
z = inf
for i in range(n):
    for j in range(i+1,n):
        if x[i][j]!=inf and x[j][i]!=inf:
            ans = path_recovery(j,x[i],path2)
            ans2 = path_recovery(i,x[j],path2)
            if ans==0 or ans2==0:
                continue
            else:
                kouho.append([len(ans)+len(ans2)-2,ans[:-1]+ans2[:-1]])
                z = min(z,kouho[-1][0])
if len(kouho)>0:
    kouho.sort()
    print(kouho[0][0])
    for i in range(len(kouho[0][1])):
        print(kouho[0][1][i]+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def answer(T):
  print(len(T))
  for i in T:
    print(i)

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]

L = {}
R = {}
for i in range(M):
  a, b = AB[i]
  if a in L:
    L[a].append(b)
  else:
    L[a] = [b]
  if b in R:
    R[b].append(a)
  else:
    R[b] = [a]

def nasu(g, n, r, P):
  if n in R:
    for i in R[n]:
      if i in P and i != r:
        return None
  if n not in L:
    return None
  k = L[n]
  for i in k:
    if i in P and i != g:
      return None
  if g in k:
    return P
  for i in k:
    if i < g:
      continue
    if i in P:
      continue
    T = nasu(g, i, n, P + [i])
    if T:
      return T
  return None

  

for i in range(1, N):
  T = nasu(i, i, 0, [i])
  if T:
    answer(T)
    exit()
else:
  print(-1)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

inf = float('inf')

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

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

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

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

kouho = []

for i in range(n):
    for j in range(i+1,n):
        if x[i][j]!=inf and x[j][i]!=inf:
            ans = path_recovery(j,x[i],path2)
            ans2 = path_recovery(i,x[j],path2)
            kouho.append([len(ans)+len(ans2)-2,ans[:-1]+ans2[:-1]])
if len(kouho)>0:
    kouho.sort()
    print(kouho[0][0])
    for i in range(len(kouho[0][1])):
        print(kouho[0][1][i]+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def search(N, M, adj):
    reachable = [[set() for i in range(N)] for _ in range(N)]
    reachable[0] = adj
    start = -1
    for m in range(1, N):
        prev = reachable[m-1]
        cur = reachable[m]
        for i in range(N):
            cur[i] = set(prev[i])
        for i in range(N):
            for nxt in adj[i]:
                if i in prev[nxt]:
                    return (i, reachable, m+1)
                for p in prev[nxt]:
                    cur[i].add(p)
    return None


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
    result = search(N, M, adj)
    if not result:
        print(-1)
        return
    start, reachable, cnt = result
    ans = [-1] * cnt
    x = start
    for i in range(cnt):
        ans[i] = x+1
        for nxt in adj[x]:
            if start in reachable[cnt-i-1][nxt]:
                x = nxt
                break
    print(len(ans))
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    prev = [0] * len(adj)
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                prev[v_to[0]] = v_from
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist, prev


N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    adj[A].append([B, 1])

ans_best = []
len_ans = N+1
flg = 1
see = [0] * (N + 1)
for start in range(1, N+1):
    if flg == 0:
        if see[start] == 0:
            continue
    ans = []
    adj_new = copy.deepcopy(adj)
    adj_new.append(adj[start])
    dist, prev = dijkstra(adj_new, N + 1)
    if dist[start] < 10 ** 10:
        k = start
        while k != N + 1:
            ans.append(k)
            k = prev[k]
        if len(ans) < len_ans:
            ans_best = ans
            len_ans = len(ans)
            if flg:
                for a in ans:
                    see[a] = 1
                flg = 0

if len_ans == N+1:
    print(-1)
else:
    print(len_ans)
    for a in ans_best:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    g = defaultdict(set)
    rg = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        rg[b].add(a)
    
    def ok(v):
        v = set(v)
        for u in v:
            if not(len(v & g[u]) == 1 and len(v & rg[u]) == 1):
                return False
        return True

    def dfs(s):
        # print(s)
        q = [[s]]
        while q:
            u = q.pop()
            for v in g[u[-1]]:
                if v == s:
                    if ok(u):
                        return u
                    else:
                        return []
    
                t = u[:]
                t.append(v)
                q.append(t)
        return None
    for i in range(1, N+1):
        v = dfs(i)
        if v:
            print(len(v))
            for u in v:
                print(u)
            return

    print(-1)


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    (slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
N, M = map(int, input().split())
E = [[] for i in range(N)]
for i in range(M):
  A, B = map(int, input().split())
  A, B = A-1, B-1
  E[A].append(B)
def sub():
  V = [False]*N
  while not all(V):
    q = queue.Queue()
    c = min(range(N), key=lambda i: not V[i])
    q.put((c, [c]))
    V[c] = True
    while not q.empty():
      c, l = q.get()
      ns = E[c]
      for n in ns:
        V[n] = True
        if n in l:
          return l
        q.put((n, l+[n]))
  return []
L = sub()
if L == []:
  print(-1)
  exit()
#print(L)
I = { L[i]: i for i in range(len(L)) }
#print(I)
c = L[-1]
ns = E[c]
imax = -1
for n in ns:
  if n not in I:
    continue
  imax = max(imax, I[n])
L = L[imax:]
#print(L)
print(len(L))
for i in L:
  print(i+1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    prev = [0] * len(adj)
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                prev[v_to[0]] = v_from
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist, prev


N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    adj[A].append([B, 1])

ans_best = []
len_ans = N+1
for start in range(1, N+1):
    ans = []
    adj_new = copy.deepcopy(adj)
    adj_new.append(adj[start])
    dist, prev = dijkstra(adj_new, N + 1)
    if dist[start] < 10 ** 10:
        k = start
        while k != N + 1:
            ans.append(k)
            k = prev[k]
        if len(ans) < len_ans:
            ans_best = ans
            len_ans = len(ans)

if len_ans == N+1:
    print(-1)
else:
    print(len_ans)
    for a in ans_best:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def show_result(arr):
    print(max(arr)+1)
    for i in range(max(arr)+1):
        print(arr.index(i)+1)

def main():

    n, m = map(int, input().split())
    arr_ab = []
    for i in range(m):
        arr_ab.append(list(map(int, input().split())))

    tbl = [ [ -1 if i != arr_ab[j][0] else 0 for i in range(n) ] for j in range(len(arr_ab)) ]

    for stp in range(n):
        ntbl = []
        for ab in arr_ab:
            for tgt in tbl:
                if tgt[ab[0]-1] == stp and tgt[ab[1]-1] == 0:
                    show_result(tgt)
                    return
                if tgt[ab[0]-1] == stp and tgt[ab[1]-1] == -1:
                    ntbl.append(tgt[:])
                    ntbl[-1][ab[1]-1] = stp+1
        tbl = ntbl[:]
    print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    prev = [0] * len(adj)
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to in v_tos:
            if min_dist + v_to[1] < dist[v_to[0]]:
                dist[v_to[0]] = min_dist + v_to[1]
                prev[v_to[0]] = v_from
                heapq.heappush(q, [dist[v_to[0]], v_to[0]])
    return dist, prev


N, M = map(int, input().split())
adj = [[] for _ in range(2 * N + 1)]
for _ in range(M):
    A, B = map(int, input().split())
    adj[A].append([B, 1])
    adj[A].append([B + N, 1])

ans_best = []
len_ans = N+1
for start in range(1, N+1):
    ans = []
    dist, prev = dijkstra(adj, start)
    if dist[start + N] < 10 ** 10:
        k = start + N
        while k != start:
            k = prev[k]
            ans.append(k)
        if len(ans) < len_ans:
            ans_best = ans
            len_ans = len(ans)

if len_ans == N+1:
    print(-1)
else:
    print(len_ans)
    for a in ans_best:
        print(a)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)

import sys
sys.setrecursionlimit(10**7)

def func(loop):
    sl=set(loop)
    k=len(loop)
    for i in range(k):
        v=loop[i]
        for nv in g[v]:
            if nv not in sl:continue
            if nv==loop[(i+1)%k]:continue
            j=[j for j in range(k) if loop[j]==nv][0]
            if i<j:
                ary=loop[:i+1]+loop[j:]
            else:
                ary=loop[j:i+1]
            func(ary)
    print(len(loop))
    for x in loop:
        print(x+1)
    exit()

mi=set(range(n))
def dfs(v,par):
    mi.discard(v)
    for nv in g[v]:
        if par[nv]==-1:
            par[nv]=v
            dfs(nv,par)
            par[nv]=-1
        else:
            loop=[v]
            while v!=nv:
                loop.append(par[v])
                v=par[v]
            loop.reverse()
            func(loop)
while mi:
    v=mi.pop()
    dfs(v,[-1]*n)
print(-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
indeg = [0] * (n+1)
outdeg = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indeg[b] += 1
    outdeg[a] += 1

is_valid = [indeg[i] * outdeg[i] for i in range(n+1)]
u = n+10
ans = []
from collections import deque
for start in range(1, n+1):
    if not is_valid[start]:
        continue

    # print("start: ", start, "---------")
    q = deque([start])
    visited = [False] * (n+1)
    prev = [-1] * (n+1)
    visited[start] = True

    has_ans = False
    while q:
        now = q.popleft()
        # print("now", now)
        for node in graph[now]:
            if node == start:
                # print("roop")
                prev[node] = now
                has_ans = True
                break
            if visited[node] or not is_valid[node]:
                continue
            # print("  to: ", node)
            prev[node] = now
            visited[node] = True
            q.append(node)
        if has_ans:
            break

    if not has_ans:
        continue
    cnt = 0
    tmp = []
    now = start
    for _ in range(n):
        tmp.append(now)
        cnt += 1
        now = prev[now]
        if now == start or now == -1:
            break
    if cnt < u:
        u = cnt
        ans = tmp

if ans:
    print(u)
    for t in ans:
        print(t)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    ans = []
    for i in range(N):
        queue = deque([i])
        dist = [-1] * N
        dist[i] = 0
        prev = [-1] * N
        while queue:
            v = queue.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    queue.append(nv)
        for j in range(N):
            if i == j or dist[j] == -1 or i not in G[j]:
                continue
            tmp = []
            k = j
            while k != -1:
                tmp.append(k)
                k = prev[k]

            if not ans or len(ans) > len(tmp):
                ans = tmp

    if ans:
        print(len(ans))
        for v in ans:
            print(v + 1)
    else:
        print(-1)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)

    def dfs(v, p, seen, finished, hist):
        seen[v] = True
        hist.append(v)
        for nv in G[v]:
            if nv == p:
                continue
            if finished[nv]:
                continue
            if seen[nv] and not finished[nv]:
                return nv

            pos = dfs(nv, v, seen, finished, hist)
            if pos != -1:
                return pos
        hist.pop()
        finished[v] = True
        return -1

    for i in range(N):
        seen = [False] * N
        finished = [False] * N
        hist = []
        pos = dfs(i, -1, seen, finished, hist)
        if pos != -1:
            break

    if pos == -1:
        print(-1)
        return

    cycle = []
    while hist:
        t = hist.pop()
        cycle.append(t)
        if t == pos:
            break

    cycle.reverse()

    while True:
        order = [-1] * N
        for i, v in enumerate(cycle):
            order[v] = i

        for i, v in enumerate(cycle):
            ord_from = ord_to = -1
            for nv in G[v]:
                if v == nv or order[nv] == -1 or order[nv] == (order[v] + 1) % len(cycle):
                    continue
                ord_from, ord_to = i, order[nv]
                break
            if ord_from != -1:
                break

        if ord_from == -1:
            break

        if ord_from < ord_to:
            cycle = cycle[: ord_from + 1] + cycle[ord_to:]
        else:
            cycle = cycle[ord_to : ord_from + 1]

    print(len(cycle))
    for v in cycle:
        print(v + 1)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  G[a].append(b)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in G[v]:
    nxt[v] = nv
    if seen[nv]:
      return nv
    s = dfs(nv)
    if s != -1:
      return s
  seen[v] = False
  return -1
for i in range(n):
  nxt = [-1]*n
  s = dfs(i)
  if s != -1:
    break
else:
  print(-1)
  exit()
while True:
  used = set()
  L = []
  while s not in used:
    used.add(s)
    L.append(s)
    s = nxt[s]
  L.append(s)
  for i in range(len(L)-1):
    a, b = L[i], L[i+1]
    for nv in G[a]:
      if nv != b and nv in used:
        nxt[a] = nv
        s = a
        break
    else:
      continue
    break
  else:
    print(len(used))
    for v in used:
      print(v+1)
    break

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
INF = float('inf')
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)

res = []
shortest = n + 1
for s in range(n):
    dist = [-1] * n
    prev = [-1] * n
    q = deque()
    q.append(s)
    dist[s] = 0
    while len(q) != 0:
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                prev[nv] = v
                q.append(nv)
    for t in range(n):
        if t == s:
            continue
        if dist[t] == -1:
            continue
        for nt in g[t]:
            if nt == s:
                temp = [s]
                cur = t
                while cur != s:
                    temp.append(cur)
                    cur = prev[cur]
                if shortest > len(temp):
                    shortest = len(temp)
                    res = temp
if shortest == n + 1:
    print(-1)
    exit()
print(len(res))
for v in res:
    print(v + 1)

# def bfs(sv):
#     dist = [INF] * n
#     pre = [-1] * n
#     q = deque()
#     q.append(sv)
#     dist[sv] = 0
#     while q:
#         v = q.popleft()
#         for nv in g[v]:
#             if dist[nv] == INF:
#                 continue
#             pre[nv] = v
#             dist[nv] = dist[v] + 1
#             q.append(nv)
#     print(dist)
#     best = (INF, -1)
#     for v in range(n):
#         if v == sv:
#             continue
#         for nv in g[v]:
#             if nv == sv:
#                 best = min(best, (dist[nv], nv))
#                 print(sv, best)
#                 # print(best)
#     if best[0] == INF:
#         return [0] * (n + 1)
#     print(pre)
#     v = best[1]
#     print('v', v)
#     res = []
#     while v != -1:
#         res.append(v)
#         v = pre[v]
#     print('res', res)
#     return res


# ans = [0] * (n + 1)
# for s in range(n):
#     now = bfs(s)
#     if len(now) < len(ans):
#         print('aa')
#         ans = now
#         print(ans)
# if len(ans) == n + 1:
#     print(-1)
#     exit()
# print(len(ans))
# for v in ans:
#     print(v)

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque, defaultdict

N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
g = [set() for _ in range(N)]
for a, b in AB:
    g[a - 1].add(b - 1)


def find_loop(s, subnode):
    q = deque([(s, {s})])
    visited = defaultdict(lambda: math.inf)
    while len(q) > 0:
        node, p = q.popleft()
        for to_node in g[node] & subnode:
            if to_node == s:
                return p
            if visited[to_node] > len(p):
                visited[to_node] = len(p)
                q.append((to_node, p | {to_node}))
    return -1


V = set(range(N))
for i in range(N):
    subnode = find_loop(i, V)
    if subnode != -1:
        break
if subnode == -1:
    print(-1)
    sys.exit()


while True:
    # 条件判定
    flg = True
    for i in subnode:
        if len(g[i] & subnode) != 1:
            flg = False
            s = i
            break
    if flg:
        break
    subnode = find_loop(s, subnode)

print(len(subnode))
for node in subnode:
    print(node+1)

Submission status: Accepted

Solution code:
import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

from collections import deque
INF = 10**18
temp= INF
for a, b in edge:
    q = deque([])
    q.append(b)
    visit = [INF]*n
    visit[b] = 0
    par = [-1]*n
    while q:
        v = q.popleft()
        for u in g[v]:
            if visit[u] == INF:
                visit[u] = visit[v]+1
                par[u] = v
                q.append(u)
    if visit[a]+1 <= temp:
        ans = []
        v = a
        ans.append(v+1)
        while par[v] != -1:
            v = par[v]
            ans.append(v+1)
        temp =  visit[a]+1

if temp == INF:
    print(-1)
else:
    if ans:
        print(len(ans))
        print(*ans, sep='\n')
    else:
        print(-1)