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: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
INF = 10 ** 5

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)

mn = INF
for s in range(n):
    dq = deque([s])
    d = [-1] * n
    p = [-1] * n
    d[s] = 0
    last = []

    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                dq.append(v)

            if v == s:
                last.append(u)

    for v in last:
        route = [v]
        while p[v] != s:
            v = p[v]
            route.append(v)

        route.append(s)
        size = len(route)
        if size < mn:
            mn = size
            ans = route[::-1]

if mn != INF:
    print(mn)
    for e in ans:
        print(e + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
pathr= [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    path[a-1].add(b-1)
    pathr[b-1].add(a-1)

def bfs(start):
    que = deque()
    d = [1e100]*n
    for i in path[start]:
        que.append(i)
        d[i] = 1
    while que:
        p = que.popleft()
        for nxt in path[p]:
            if d[nxt] == 1e100:
                que.append(nxt)
            d[nxt] = min(d[nxt], d[p] + 1)
    if d[start] == 1e100:
        return [0] * (n+1)
    ret = [0]*d[start]
    ret[-1] = start
    now = start
    for i in range(d[start] - 1)[::-1]:
        for p in pathr[now]:
            if d[p] == i+1:
                now = p
                ret[i] = now
                break
    return ret
ans = [0]*(n+1)
for i in range(n):
    tmp = bfs(i)
    if len(ans) > len(tmp):
        ans = tmp
if len(ans) > n:
  print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = []
for sta in range(N):
    prev = [-1] * N
    que = deque([sta])

    while que:
        v = que.popleft()
        for w in edge[v]:
            if w == sta:
                path = []
                while v != -1:
                    path.append(v+1)
                    v = prev[v]
                if (not ans) or (len(ans) > len(path)):
                    ans = path
                break

            if prev[w] != -1: continue

            prev[w] = v
            que.append(w)

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

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
Edge = [list(map(int, input().split())) for i in range(m)]
adj = [[] for _ in range(n)]

for u, v in Edge:
    adj[u-1].append(v-1)

adj_bit = [0]*n
for i in range(n):
    for j in adj[i]:
        adj_bit[i] += 1 << j

for i in range(n):
    que = deque([(i, 0)])
    visited_a = [0] * n

    while que:
        v, visited = que.popleft()

        for dest in adj[v]:
            if visited_a[dest]:
                continue
            if dest == i:
                ans = [i+1]
                for j in range(1001):
                    if visited & 1:
                        ans.append(j+1)
                    visited >>= 1
                print(len(ans))
                print(*ans, sep='\n')
                exit()
            if visited & adj_bit[dest]:
                # print(i, v, dest, bin(visited), bin(adj_bit[dest]))
                continue
            visited_a[dest] = 1
            que.append((dest, visited + (1 << dest)))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

ans = []
for sta in range(N):
    prev = [-1] * N
    que = deque([sta])

    while que:
        v = que.popleft()
        for w in edge[v]:
            if w == sta: # 閉路発見
                path = []
                while v != -1:
                    path.append(v+1)
                    v = prev[v]
                if (not ans) or (len(ans) > len(path)):
                    ans = path
                break

            if prev[w] != -1: continue

            prev[w] = v
            que.append(w)

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

Submission status: Accepted

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

from collections import deque
mindist = N
opt = None
for g,tos in enumerate(es):
    for s in tos:
        q = deque([(s,0)])
        prev = [-1]*N
        dist = [N]*N
        dist[s] = 0
        while q:
            v,d = q.popleft()
            for to in es[v]:
                if to==g: break
                if d+1 >= dist[to]: continue
                dist[to] = d+1
                prev[to] = v
                q.append((to,d+1))
            else:
                continue
            break
        else:
            continue
        if d+1 >= mindist: continue
        mindist = d+1
        opt = [g,v]
        while prev[opt[-1]] >= 0:
            opt.append(prev[opt[-1]])
if opt:
    ans = [o+1 for o in opt]
    print(len(ans))
    print(*ans, sep='\n')
else:
    print(-1)

Submission status: Accepted

Solution code:
def dijkstra_back(s,t,n,w,cost):
    import heapq
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    q=[]
    heapq.heapify(q)
    heapq.heappush(q,(0,s))
    while q:
        c,v=heapq.heappop(q)
        if d[v]<c:
            continue

        for i in range(len(to[v])):
            k=to[v][i]
            if d[k]>d[v]+cost[v][k]:
                d[k]=d[v]+cost[v][k]
                heapq.heappush(q,(d[k],k))
                prev[k]=v

    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path

N,M=map(int,input().split())
fr={i:[] for i in range(1,N+1)}
to={i:[] for i in range(1,N+1)}
cost=[[float('inf') for i in range(0,N+1)] for i in range(0,N+1)]
for i in range(0,M):
    a,b=map(int,input().split())
    cost[a][b]=1
    fr[b].append(a)
    to[a].append(b)



ansc=10**10
ans=[]
for i in range(1,N+1):
    for j in fr[i]:
        test=dijkstra_back(i,j,N+1,M,cost)
        if len(test)==2:
            if cost[i][j]!=float('inf'):
                ansc=2
                ans=test
        elif len(test)<ansc:
            ansc=len(test)
            ans=test

if ansc!=10**10:
    print(ansc)
    for i in range(0,ansc):
        print(ans[i])
else:
    print(-1)

Submission status: Accepted

Solution code:
def dijkstra_back(s,t,n,w,cost):
    import heapq
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    q=[]
    heapq.heapify(q)
    heapq.heappush(q,(0,s))
    while q:
        c,v=heapq.heappop(q)
        if d[v]<c:
            continue

        for i in range(len(to[v])):
            k=to[v][i]
            if d[k]>d[v]+cost[v][k]:
                d[k]=d[v]+cost[v][k]
                heapq.heappush(q,(d[k],k))
                prev[k]=v

    path = [t]
    while prev[t] != s:
        path.append(prev[t])
        prev[t] = prev[prev[t]]
    path.append(s)
    path = path[::-1]
    return path



N,M=map(int,input().split())
fr={i:set([]) for i in range(1,N+1)}
to={i:set([]) for i in range(1,N+1)}
for i in range(0,M):
    a,b=map(int,input().split())
    fr[b].add(a)
    to[a].add(b)

delete=set([])
flag=1
while flag==1:
    flag=0
    for i in range(1,N+1):
        if (not i in delete) and (delete>=fr[i] or delete>=to[i]):
            delete.add(i)
            flag=1

node=[i for i in range(1,N+1)]
save=set(node)-delete
if save:
    hen=[]
    for i in save:
        fr[i]=fr[i]&save
        to[i]=to[i]&save
        fr[i]=list(fr[i])
        to[i]=list(to[i])

    for i in save:
        for j in fr[i]:
            hen.append((j,i))

    save=list(save)

    cost=[[float('inf') for i in range(0,N+1)] for i in range(0,N+1)]
    for i in range(0,len(hen)):
        a,b=hen[i]
        cost[a][b]=1

    ansc=10**10
    ans=[]
    for i in range(len(save)):
        for j in fr[save[i]]:
            test=dijkstra_back(save[i],j,N+1,len(hen),cost)
            if len(test)<ansc:
                ansc=len(test)
                ans=test

    print(ansc)
    for i in range(0,ansc):
        print(ans[i])

else:
    print(-1)

Submission status: Accepted

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 curr_path:
                    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-1,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: Accepted

Solution code:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)

from collections import deque

mindist = N
ans = None
for g in range(N):
    for s in es[g]:
        q = deque([s])
        dist = [N]*N
        dist[s] = 0
        prev = [-1]*N
        while q:
            v = q.popleft()
            if v==g:
                break
            for to in es[v]:
                if dist[to] <= dist[v] + 1: continue
                dist[to] = dist[v] + 1
                prev[to] = v
                q.append(to)
        else:
            continue
        if dist[g] >= mindist: continue
        mindist = dist[g]
        v = g
        tmp = [v+1]
        while prev[v] >= 0:
            v = prev[v]
            tmp.append(v+1)
        ans = tmp

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

Submission status: Accepted

Solution code:
from collections import deque

N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

shortest = N + 1
ans = []
for s in range(1, N + 1):
    D = [-1] * (N + 1)
    P = [-1] * (N + 1)

    D[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if D[c] < 0:
                D[c] = D[p] + 1
                P[c] = p
                Q.append(c)

    for t in range(1, N + 1):
        if t == s or D[t] < 0:
            continue

        for v in E[t]:
            if v != s:
                continue

            T = [s]
            cur = t
            while cur != s:
                T.append(cur)
                cur = P[cur]

            if shortest > len(T):
                shortest = len(T)
                ans = T

if shortest == N + 1:
    print(-1)
else:
    print(len(ans))
    print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cand1=set()
cand2=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  cand1.add(a)
  cand2.add(b)
cand=cand1&cand2
ans=-1
for i in range(1,n+1):
  if i not in cand:
    continue
  else:
    q=collections.deque()
    q.append((i,[i]))
    checked=[0]*(n+1)
    while len(q)!=0:
      v,chain=q.popleft()
      if v==i and len(chain)!=1:
        ans=chain[:-1]
      for u in g[v]:
        if u not in cand:
          continue
        elif checked[u]==0:
          checked[u]=1
          q.append((u,chain+[u]))
    cand.discard(i)
if ans==-1:
  print(ans)
else:
  print(len(ans))
  for v in ans:
    print(v)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
tree = dict(zip(range(1, N+1), [[] for i in range(N)]))
for i in range(M):
  a, b = map(int, input().split())
  tree[a].append(b)


is_visited = [False]*(N+1)
num_visited = 0
def find_cycle(d):
  global is_visited
  global num_visited
  cycle = []
  l = 1001
  while d:
    node = d[-1]
    if tree[node]:
      child = tree[node].pop()
      if not is_visited[child]:
        is_visited[child] = True
        num_visited += 1
      if child in cycle and node in cycle:
        idn = cycle.index(node)
        idc = cycle.index(child)
        cycle = cycle[:idn+1] + cycle[idc:]
        l = len(cycle)
      if child in d:
        idx = d.index(child)
        if len(d) - idx < l:
          cycle = d[idx:]
          l = len(cycle)
      else:
        d.append(child)
    else:
      d.pop()
  return cycle


is_visited[0] = True
num_visited += 1
i = 1
while num_visited < N+1:
  while is_visited[i]:
    i += 1
  d = [i]
  is_visited[i] = True
  num_visited += 1
  cycle = find_cycle(d)
  if cycle:
    print(len(cycle))
    print(*cycle, sep='\n')
    quit()

print(-1)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read

N, M = map(int, input().split())
if M != 0:
    AB = list(map(int, read().split()))
else:
    print(-1)
    exit()

graph = [[] for _ in range(N + 1)]
A = AB[::2]
B = AB[1::2]
A_s = set(A)
# 出次数が0の頂点はいらない。
needless = set(range(1, N + 1)) - A_s

for i, j in zip(A, B):
    if j not in needless:
        graph[i].append(j)


# cycleを少なくとも一つ検出する
def dfs(original_stack):
    checked = [False] * (N + 1)
    while original_stack:
        start = original_stack.pop()
        if checked[start]:
            continue
        checked[start] = True
        stack = [(start, [start])]
        while stack:
            v, route = stack.pop()
            for i in graph[v]:
                if i in route:
                    return route[route.index(i):]
                else:
                    stack.append((i, route + [i]))
                    checked[i] = True


v = dfs([i for i in range(1, N + 1) if graph[i]])
if not v:
    print(-1)
    exit()

while True:
    v_s = set(v)
    length = len(v)
    for i, (v_i, v_j) in enumerate(zip(v, v[1:] + [v[0]])):
        for j in graph[v_i]:
            if j != v_j and j in v_s:
                idx = v.index(j)
                if i < idx:
                    v = v[:i + 1] + v[idx:]
                else:
                    v = v[idx:i + 1]
                break
        else:
            continue
        break
    else:
        print(len(v))
        print('\n'.join(map(str, v)))
        exit()

Submission status: Accepted

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

from collections import deque
tmpdist = N
ans = None
for to in range(N):
    for fr in es[to]:
        dist = [N] * N
        dist[fr] = 0
        prev = [-1] * N
        q = deque([fr])
        while q:
            v = q.popleft()
            if v==to: break
            for w in es[v]:
                if dist[w] < N: continue
                if v==to and w==fr: continue
                dist[w] = dist[v] + 1
                prev[w] = v
                q.append(w)
        else:
            continue
        if dist[to] < tmpdist:
            tmpdist = dist[to]
            ans = set()
            v = to
            while 1:
                ans.add(v+1)
                if prev[v] < 0: break
                v = prev[v]
if ans is None:
    print(-1)
else:
    print(len(ans))
    print(*ans, sep='\n')

Submission status: Accepted

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

N, M = map(int, input().split())
adjL = [set() for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].add(B)

def getCycle(adjL):
    def dfs(vNow):
        if isAvails[vNow]:
            anss.append(vNow)
            return vNow
        useds[vNow] = True
        isAvails[vNow] = True
        for v2 in adjL[vNow]:
            vRet = dfs(v2)
            if vRet == vNow or vRet == numV:
                return numV
            elif vRet != -1:
                anss.append(vNow)
                return vRet
        isAvails[vNow] = False
        return -1

    numV = len(adjL)
    useds = [False] * numV
    anss = []
    for vSt in range(numV):
        isAvails = [False] * numV
        if useds[vSt]: continue
        vRet = dfs(vSt)
        if vRet == numV:
            return anss[::-1]
    return []

cycle = getCycle(adjL)

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

isAvails = [False] * N
v2s = [-1] * N
for i in range(len(cycle)):
    isAvails[cycle[i]] = True
    v2s[cycle[i-1]] = cycle[i]

while True:
    adjL2 = [set() for _ in range(N)]
    a, b = -1, -1
    for v in cycle:
        for v2 in adjL[v]:
            if isAvails[v2]:
                adjL2[v].add(v2)
                if v2s[v] != v2:
                    a, b = v, v2

    if (a, b) == (-1, -1):
        print(len(cycle))
        print('\n'.join(map(lambda x: str(x+1), cycle)))
        break

    adjL = adjL2

    cycle = []
    isAvails = [False] * N
    v2s[a] = b
    v = a
    while not isAvails[v]:
        cycle.append(v)
        isAvails[v] = True
        v = v2s[v]

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
reve = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  reve[v].append(u)
vis = set()
inc = [0] * (N + 1)
def dfs(x, l):
  global vis
  global inc
  vis.add(x)
  ok = 0
  for y in reve[x]:
    if y in vis: inc[x] += 1
  if inc[x] > 1:
    inc[x] = 0
    vis.discard(x)
    return
  for y in e[x]:
    if y == l:
      ok = 1
      continue
    if y in vis:
      inc[x] = 0
      vis.discard(x)
      return
  if ok:
    print(len(vis))
    for v in vis: print(v)
    #print(vis, inc)
    exit(0)
  for y in e[x]:
    dfs(y, l)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s, s)
print(-1)

Submission status: Accepted

Solution code:
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)

from collections import deque

d = N+1
flag = False
for i in range(N):
    for v in E[i]:
        q = deque()
        q.append(v)
        used = [N+1]*N
        used[v] = 1
        while q:
            temp = q.popleft()
            if used[temp] > d:
                break
            for u in E[temp]:
                if u == i and d > used[temp]+1:
                    d = used[temp]+1
                    memo = [temp, u]
                    q = deque()
                    flag = True
                    break
                elif u == i:
                    q = deque()
                    break
                if used[u] < N+1:
                    continue
                used[u] = used[temp]+1
                q.append(u)

import heapq
if flag:
    h = []
    dist = [N+1]*N
    dist[memo[1]] = 0
    for v in E[memo[1]]:
        heapq.heappush(h, (1, v))
    while True:
        temp = heapq.heappop(h)
        if dist[temp[1]] < N+1:
            continue
        dist[temp[1]] = temp[0]
        if temp[1] == memo[0]:
            break
        for v in E[temp[1]]:
            if dist[v] < N+1:
                continue
            heapq.heappush(h, (temp[0]+1, v))
    ans = [memo[0]]
    d = dist[memo[0]]-1
    prev = memo[0]
    while d >= 0:
        for i in range(N):
            if dist[i] == d and prev in E[i]:
                prev = i
                ans.append(i)
                d -= 1
                break
    print(len(ans))
    for i in ans:
        print(i+1)
else:
    print(-1)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def SCC(N, edges):
    """ 強連結成分分解 """

    nodes1 = [[] for i in range(N)]
    nodes2 = [[] for i in range(N)]
    for u, v in edges:
        nodes1[u].append(v)
        nodes2[v].append(u)

    T = []
    visited = [False] * N
    def rec1(cur):
        visited[cur] = True
        for nxt in nodes1[cur]:
            if not visited[nxt]:
                rec1(nxt)
        # 行き止まったところから順にTに入れていく
        T.append(cur)

    # グラフが連結とは限らないので全頂点やる
    for u in range(N):
        if not visited[u]:
            rec1(u)

    visited = [False] * N
    group = [0] * N
    grpcnt = 0
    def rec2(cur):
        group[cur] = grpcnt
        visited[cur] = True
        for nxt in nodes2[cur]:
            if not visited[nxt]:
                rec2(nxt)

    # 逆順で進めるところまで行く
    for u in reversed(T):
        if not visited[u]:
            rec2(u)
            grpcnt += 1
    return grpcnt, group

def bfs(N, nodes, src):
    """ BFS(一般グラフ、重みなし) """
    from collections import deque

    que = deque([(src, -1, 0)])
    dist = [()] * N
    mn = INF
    end = -1
    while que:
        u, prev, c = que.popleft()
        # 同じ強連結成分内のみでやる
        if group[u] != group[src]:
            continue
        if dist[u]:
            # 訪問済で始点に帰ってきたら、最短チェック
            if u == src:
                if c < mn:
                    mn = c
                    end = prev
            continue
        dist[u] = (c, prev)
        for v in nodes[u]:
            que.append((v, u, c+1))
    # 経路、始点に戻ってくる最短距離、その直前の頂点を返す
    return dist, mn, end

def get_route(s, t, res):
    """ s,t間の経路を取得 """
    prev = t
    StoT = [t]
    while prev != s:
        prev = res[prev][1]
        if prev == -1:
            return None
        StoT.append(prev)
    StoT = StoT[::-1]
    return StoT

N, M = MAP()
nodes = [[] for i in range(N)]
edges = []
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    edges.append((a, b))

# 強連結成分毎に見る
grpcnt, group = SCC(N, edges)
ans = INF
for i in range(N):
    # 経路、始点に戻ってくる最短距離、その直前の頂点
    dist, mn, end = bfs(N, nodes, i)
    if mn < ans:
        ans = mn
        route = get_route(i, end, dist)
if ans != INF:
    print(ans)
    [print(u + 1) for u in route]
else:
    # そもそも閉路なし
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**4)
def input():
	return sys.stdin.readline()[:-1]

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

seen = [False for _ in range(n)]
visited = [False for _ in range(n)]
begin = -1
hist = []

def dfs(x):
	global begin, hist
	if begin >= 0:
		return
	seen[x] = True
	hist.append(x)
	for v in adj[x]:
		if visited[v]:
			continue
		if seen[v] == True and visited[v] == False:
			begin = v
			return
		dfs(v)
		if begin >= 0:
			return
	visited[x] = True
	hist.pop()
	return

for i in range(n):
	if begin < 0:
		dfs(i)
	if begin >= 0:
		break

if begin < 0:
	print(-1)
	sys.exit()
else:
	cycle = []
	included = [False for _ in range(n)]
	included[begin] = True
	while hist and hist[-1] != begin:
		cycle.append(hist[-1])
		included[hist[-1]] = True
		hist.pop()
	cycle.append(begin)
	hist.pop()

	while True:
		meets = True
		l = len(cycle)
		ind = [-1 for _ in range(n)]
		for i in range(l):
			ind[cycle[i]] = i
		for i in range(l):
			if meets == False:
				break
			for v in adj[cycle[(i+1)%l]]:
				if included[v] == True and v != cycle[i]:
					meets = False
					new_start_id, new_end_id = ind[v], (i+1)%l
					break

		if meets:
			print(len(cycle))
			print(*[c+1 for c in cycle], sep="\n")
			break
		else:
			new_cycle = []
			included = [False for _ in range(n)]
			cur = new_end_id
			while cur != new_start_id:
				new_cycle.append(cycle[cur])
				included[cycle[cur]] = True
				cur = (cur+1)%l
			new_cycle.append(cycle[new_start_id])
			cycle = new_cycle

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
g = [list() for _ in range(n+1)]
en = [0]*(n+1)
for _ in range(m):
  u,v = map(int,input().split())
  g[u].append(v)
  en[v] += 1
q = deque(i for i in range(1,n+1) if en[i] == 0)
done = list()
while q:
  v = q.popleft()
  for x in g[v]:
    en[x] -= 1
    if not en[x]:
      q.append(x)
  done.append(v)
print(-1 if len(done) == n else 0)