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:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)
    # bfs
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    break # for loop
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            else:
                continue
            break # while loop
        else:
            return [0]*(n+1)
        loop=[]
        while(v!=-1):
            loop.append(v)
            v=prev[v]
        loop.reverse()
        return loop
    # calculate
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(lambda x:int(x)-1,input().split())
        E[a].append(b)

    # bfs
    def bfs(sv):
        prev=[-1]*n
        flag=False
        from collections import deque
        Q=deque([sv])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(nv==sv):
                    flag=True
                    break
                elif(prev[nv]==-1):
                    prev[nv]=v
                    Q.append(nv)
            if(flag): break
        if(not flag):
            return [0]*(n+1)
        else:
            loop=[]
            while(v!=-1):
                loop.append(v)
                v=prev[v]
            loop.reverse()
            return loop

    # calculate
    ans=[0]*(n+1)
    for i in range(n):
        loop=bfs(i)
        if(len(loop)<len(ans)):
            ans=loop
    if(len(ans)==n+1):
        print(-1)
    else:
        print(len(ans))
        for v in ans: print(v+1)
resolve()

Submission status: Accepted

Solution code:
#input
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())

#output

C = [[]] * N
for a in A:
    C[a-1] = [b-1 for i, b in enumerate(B) if A[i] == a]

#iを出発して、ループが形成できるか確認。
search_stack = [[]] * N
visited = [[]] * N
next_position = [-1] * N

for i in range(N):
    search_stack[i] = [i]
    visited[i] = []
    while search_stack[i] != []:
        next_position[i] = search_stack[i].pop(0)
        visited[i].append(next_position[i])
        for node in C[next_position[i]]:
            if node == i:
                visited[i].append(node)
                search_stack[i] = []
                break
            elif node in visited[i]:
                continue
            elif node in search_stack[i]:
                continue
            elif C[node] == []:
                continue
            else:
                search_stack[i].append(node)

short = None
for v in visited:
    if len(v) >= 2 and v[0] == v[-1]:
        if not short or len(v) < len(short):
            short = v

#結果の出力            
if short:
    del short[-1]
    print(len(short))
    for s in short:
        print(s+1)
else:
    print(-1)

Submission status: Accepted

Solution code:
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].pop()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                elif status[n] == 0:
                    idx = stack.index(n)
                    cycle = stack[idx:]
                    
                    return cycle
            else:                  
                status[v] = 1
                stack.pop()

    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].pop()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


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

AB = [[] for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Submission status: Accepted

Solution code:
from collections import deque

     
def dfs(N, AB):
    status = [-1] * N
    for i in range(N):
        if status[i] == 1:
            continue
        stack = [i]
        status[i] = 0
        while stack:
            v = stack[-1]
            if AB[v]:
                n = AB[v].popleft()
                if status[n] == -1:
                    stack.append(n)
                    status[n] = 0
                else:
                    if n in stack:
                        idx = stack.index(n)
                        cycle = stack[idx:]
                        return cycle
            else:                  
                status[v] = 1
                stack.pop()
    return False


def find_smaller_cycle(cycle, AB):
    i = 0
    while i < len(cycle):
        v = cycle[i]
        if AB[v]:
            n = AB[v].popleft()
            if n in cycle:
                r = cycle.index(n)
                if i < r:
                    cycle = cycle[:i+1] + cycle[r:]
                else:
                    cycle = cycle[r:i+1]
                i = cycle.index(v)
        else:
            i += 1
            
    return cycle


N, M = [int(i) for i in input().split()]
AB = [deque() for _ in range(N)]
for _ in range(M):
    A, B = [int(i) - 1 for i in input().split()]
    AB[A].append(B)
                      
cycle = dfs(N, AB)
if not cycle:
    print(-1)
else:
    cycle = find_smaller_cycle(cycle, AB)
            
    print(len(cycle))
    for v in cycle:
        print(v + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(i) :
    dist = [float('inf')] * N
    pre = [-1] * N
    
    queue = deque([(i, 0)])
    while queue :
        cur, cost = queue.popleft()
        if dist[cur] < cost :
            continue
        for nex in v[cur] :                
            if cost + 1 < dist[nex] :
                dist[nex] = cost + 1
                pre[nex] = cur
                queue.append((nex, cost + 1))
    
    return dist[i], pre

mi = -1
mv = float('inf')
mp = []
for i in range(N) :
    m, pre = bfs(i)
    if m < mv :
        mi, mv, mp = i, m, pre

if mi >= 0 :
    print(mv)
    cur = mi
    while mp[cur] != mi :
        print(cur + 1)
        cur = mp[cur]
    print(cur + 1)
else :
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""



def bfs(n):
    clsd = set()
    opnd = collections.deque()        
    root = [None]*N
    d_list = [0]*N
    opnd.append(n)
    
    #print("Let's BFS (", n, " times)")
    while len(opnd) != 0:

        #print("clsd: ", clsd)
        #print("opnd: ", opnd)
        
        now = opnd.popleft()
        clsd.add(now)
        
        for e in E[now]:
            if e in clsd:
                if e == n:
                    res = [now]
                    #print("root: ", root)
                    #print("d_list: ", d_list)
                    dist = d_list[now] + 1
                    while len(res) != dist:
                        #   print(res, dist)
                        res.append(root[res[-1]])
                    return [list(reversed(res)), dist]
                
            else:
                opnd.append(e)
                root[e] = now
                d_list[e] = d_list[root[e]]+1
    return [[], inf] 


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

E = [[] for n in range(N)]

 
for m in range(M):
    e = list(map(int, input().split()))
    E[e[0]-1].append(e[1]-1)

inf = 10**9

    
def main(): 
    res = []
    d_min = inf
    for n in range(N):
        graph, dist = bfs(n)
        if dist < d_min:
            d_min = dist
            res = graph
    if d_min != inf:
       print(d_min)
       for n in range(d_min):
           print(res[n]+1)
    else:
       print(-1)
        
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def serp(s):
  prev = [-1]*n
  q=deque([s])
  while q:
    v = q.pop()
    for nv in e[v]:
      if nv==s: prev[nv]=v; return(s,prev)
      if prev[nv]<0: q+=nv,; prev[nv] =v
  return(-1,prev)
n,m,*t=map(int,open(0).read().split())
e,ab = [[] for i in range(n)],[]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+= b-1,
  ab += [(a-1,b-1)]
for v in range(n):
  v0,prev = serp(v)
  if v0>=0: break
if v0<0: print(-1); sys.exit()
c=set()
c.add(v0)
pv = prev[v0]
while pv!=v0:
  c.add(pv)
  pv=prev[pv]
for a,b in ab:
  if a in c and b in c and prev[b]!=a:
    pv = prev[b]
    while pv !=a:
      c.remove(pv)
      pv=prev[pv]
    prev[b]=a
print(len(c))
for i in c: print(i+1)

Submission status: Accepted

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o,r=[0]*n,[[]for _ in'_'*n],[]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q=deque(v for v in range(n)if i[v]<1)
while q:
  v=q.popleft()
  r+=v,
  for w in o[v]:
    i[w]-=1
    if i[w]==0:q+=w,
print(-(len(r)==n))

Submission status: Accepted

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

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

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

vis = [0] * 1005


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


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


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


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

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

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

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

Submission status: Accepted

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o,r=[0]*n,[[]for _ in'_'*n],[]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q=deque(v for v in range(n)if i[v]<1)
while q:
  v=q.popleft()
  r+=v,
  for w in o[v]:
    i[w]-=1
    if i[w]==0:q+=w,
print(-(len(r)==n))

Submission status: Accepted

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

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

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

vis = [0] * 1005


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


t = []
for i in range(1, 1 + n):
    t = dfs(i, [])
    if len(t):
        print(0)
        exit(0)

print(-1)

Submission status: Accepted

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
i,o=[0]*n,[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q=deque(v for v in range(n)if i[v]<1)
r=[]
while q:
  v=q.popleft()
  r+=v,
  for w in o[v]:
    i[w]-=1
    if i[w]==0:q+=w,
print(-(len(r)==n))

Submission status: Accepted

Solution code:
# -*- Coding: utf-8 -*-
INF = 1001001001
n, m = map(int, input().split())
 
def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[i]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    
 
to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
if len(to) == 0:
  print(-1)
else:  
  c = [bfs(i, to) for i in range(n)]
  ans = [1 for i in range(n+1)]
  for i in range(n):
    if len(ans) > len(c[i]):
      ans = c[i]
  if len(ans) == n + 1:
    print(-1)
  else:
    print(len(ans))
    for v in ans[::-1]:
      print(v+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def shave(fwd_link, bwd_link):
    # Vertices having no leaving link
    q = [v for v, links in enumerate(fwd_link) if not links]
    while q:
        v = q.pop()
        for u in bwd_link[v]:
            fwd_link[u].remove(v)
            if not fwd_link[u]:
                q.append(u)
    # Vertices having no entering link
    q = [v for v, links in enumerate(bwd_link) if not links]
    while q:
        v = q.pop()
        for u in fwd_link[v]:
            bwd_link[u].remove(v)
            if not bwd_link[u]:
                q.append(u)


def bfs(s, fwd_link):
    predecessors = [-1] * n
    q = deque()
    for v in fwd_link[s]:
        predecessors[v] = s
        q.append((v, s))
    visited = set()
    while q:
        v, p = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        predecessors[v] = p

        if v == s:
            break

        for u in fwd_link[v]:
            if u not in visited:
                q.append((u, v))

    circuit = {s}
    v = predecessors[s]
    while v != s:
        circuit.add(v)
        v = predecessors[v]

    return predecessors, circuit


def check(predecessors, circuit, fwd_link):
    for v in circuit:
        fwd_link[v].intersection_update(circuit)
        if len(fwd_link[v]) == 1:
            continue
        for u in fwd_link[v]:
            if predecessors[u] != v:
                return u
    return -1


def print_ans(circuit):
    print(len(circuit))
    print(*(v + 1 for v in circuit))


def solve(fwd_link, bwd_link):
    shave(fwd_link, bwd_link)
    s = -1
    for s, (f, b) in enumerate(zip(fwd_link, bwd_link)):
        if f and b:
            break
    else:
        print(-1)
        return

    while True:
        predecessors, circuit = bfs(s, fwd_link)
        res = check(predecessors, circuit, fwd_link)
        if res == -1:
            print_ans(circuit)
            break
        s = res


n, m = map(int, input().split())
fwd_link = [set() for _ in range(n)]
bwd_link = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    fwd_link[a].add(b)
    bwd_link[b].add(a)

solve(fwd_link, bwd_link)

Submission status: Accepted

Solution code:
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)
vis = {}
def dfs(i):
    if i in vis:
        return vis[i]
    vis[i] = True
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    return False
for i in range(n):
    if dfs(i):
        print(0)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
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)
vis = {}
vs = []
def dfs(i):
    if i in vis:
        if vis[i]:
            del vs[:vs.index(i)]
        return vis[i]
    vis[i] = True
    vs.append(i)
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    vs.pop()
    return False
for i in range(n):
    if dfs(i):
        break
else:
    print(-1)
    exit()
dist = {v: i for i, v in enumerate(vs)}
vis = set()
ws = []
nxt = 0
for i in vs:
    if dist[i] < nxt:
        continue
    k = -1
    for j in g[i]:
        if j not in dist or dist[j]<dist[i] and j not in vis:
            continue
        if k == -1:
            k = j
            continue
        dj = (dist[j]-dist[i])%len(vs)
        dk = (dist[k]-dist[i])%len(vs) 
        if dj > dk:
            k, j = j, k
    nxt = dist[k]
    vis.add(i)
    ws.append(i)
    if k in vis:
        del ws[:ws.index(k)]
        break
print(len(ws))
for i in ws:
    print(i)

Submission status: Accepted

Solution code:
def cycle_detection(V, E, s):
    prev = [-1] * len(V)
    stack = [s]
    while stack:
        v = stack.pop()
        for u in E[v]:
            if u == s:
                prev[u] = v
                return (s, prev)
            if prev[u] == -1:
                stack.append(u)
                prev[u] = v
    return (-1, prev)

N, M = map(int, input().split())
V = list(range(N))
E = [[] for _ in range(N)]
edges = []
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    edges.append((a-1, b-1))

dag = False
for v in range(N):
    s, prev = cycle_detection(V, E, v)
    if s != -1: break
else:
    dag = True

if dag: print(-1)
else:
    # construct a directed cycle
    cycle = set()
    cycle.add(s)
    pv = prev[s]
    while pv != s:
        cycle.add(pv)
        pv = prev[pv]
    # shrink the directed cycle
    for a, b in edges:
        if a in cycle and b in cycle and prev[b] != a:
            pv = prev[b]
            while pv != a:
                cycle.remove(pv)
                pv = prev[pv]
            prev[b] = a
    print(len(cycle))
    print(*[v + 1 for v in cycle], sep='\n')

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque


def main():
    node_num, edge_num = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(edge_num)]

    graph_data = defaultdict(set)
    jisuu_list = [0 for i in range(node_num + 1)]
    for i in range(edge_num):
        a, b = data[i]
        graph_data[a].add(b)
        jisuu_list[b] += 1


    now_set = set()
    next_set = set()
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            now_set.add(i)

    while len(now_set) > 0:
        for now_node in now_set:
            for next_node in graph_data[now_node]:
                jisuu_list[next_node] -= 1
                if jisuu_list[next_node] == 0:
                    next_set.add(next_node)
        now_set = next_set
        next_set = set()

    if max(jisuu_list) == 0:
        print(-1)
        sys.exit()

    ans = []
    dist = 10 ** 10
    for i in range(1, node_num + 1):
        if jisuu_list[i] == 0:
            continue

        parent_node = [0 for i in range(node_num + 1)]
        now_set = set()
        next_set = set()
        now_set.add(i)
        dist_kari = 0
        fin_flg = 0
        while len(now_set) > 0:
            dist_kari += 1
            # print(now_set, graph_data, fin_flg, parent_node)
            for now_node in now_set:
                for next_node in graph_data[now_node]:
                    # print('uuu', next_node)
                    if next_node == i:
                        parent_node[next_node] = now_node
                        fin_flg = 1
                        break
                    if jisuu_list[next_node] == 0:
                        continue
                    if parent_node[next_node] == 0:
                        parent_node[next_node] = now_node
                        next_set.add(next_node)
                if fin_flg:
                    break
            if fin_flg:
                break
            now_set = next_set
            next_set = set()

        if dist_kari < dist and fin_flg:
            dist = dist_kari
            ans = []
            now_node = parent_node[i]
            ans.append(i)
            # print(parent_node)
            while now_node != i:
                ans.append(now_node)
                now_node = parent_node[now_node]

    print(len(ans))
    for ele in ans:
        print(ele)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import*
n,m=map(int,input().split())
outs=defaultdict(list)
ins=defaultdict(int)
for _ in range(m):
    a,b=map(int,input().split())
    outs[a-1]+=b-1,
    ins[b-1]+=1
q=deque(i for i in range(n)if ins[i]==0)
res=[]
while q:
    v=q.popleft()
    res+=v,
    for w in outs[v]:
        ins[w]-=1
        if ins[w]==0:
            q.append(w)
print(-(len(res)==n))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

from collections import deque

inf = float("inf")
ans = inf
ss = []
def bfs(i):
    global ans, ss
    dist = [inf]*n
    prev = [None]*n
    que = deque()
    # 一個先から始める
    for to in G[i]:
        que.append(to)
        dist[to] = 1
        prev[to] = i
    while que:
        cur = que.popleft()
        if cur == i:
            break
        for to in G[cur]:
            if dist[to] != inf:
                continue
            dist[to] = dist[cur]+1
            prev[to] = cur
            que.append(to)

    if dist[i] < ans:
        ans = dist[i]
        ss = [i]
        for _ in range(ans-1):
            ss.append(prev[ss[-1]])
        #print(ss)

for i in range(n):
    bfs(i)

if ans == inf:
    print(-1)
else:
    print(0)
    exit()
    print(ans)
    #print(ss)
    for i in reversed(ss):
        print(i+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

from collections import deque

inf = float("inf")
ans = inf
ss = []
def bfs(i):
    global ans, ss
    dist = [inf]*n
    prev = [None]*n
    que = deque()
    # 一個先から始める
    for to in G[i]:
        que.append(to)
        dist[to] = 1
        prev[to] = i
    while que:
        cur = que.popleft()
        if cur == i:
            break
        for to in G[cur]:
            if dist[to] != inf:
                continue
            dist[to] = dist[cur]+1
            prev[to] = cur
            que.append(to)

    if dist[i] < ans:
        ans = dist[i]
        ss = [i]
        for _ in range(ans-1):
            ss.append(prev[ss[-1]])
        #print(ss)

for i in range(n):
    bfs(i)

if ans == inf:
    print(-1)
else:
    print(ans)
    #print(ss)
    for i in reversed(ss):
        print(i+1)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()

Submission status: Accepted

Solution code:
# -*- Coding: utf-8 -*-
INF = 1001001001
n, m = map(int, input().split())

def bfs(sv, to_list):
  dist = [INF for i in range(n)]
  hist = [-1 for i in range(n)]
  q = []
  dist[sv] = 0
  q.append(sv)
  while len(q) > 0:
    v = q[0]
    del q[0]
    for j in to_list[v]:
      if dist[j] != INF:
        continue
      hist[j] = v
      dist[j] = dist[v] + 1
      q.append(j)
  min_cycle = INF
  min_hist = -1
  for i in range(n):
    if i == sv:
      continue
    for j in to[i]:
      if j == sv:
        if min_cycle > dist[j]:
          min_cycle = dist[i]
          min_hist = i
  res = []
  temp_v = min_hist
  if min_cycle < INF:
    while temp_v > -1:
      res.append(temp_v)
      temp_v = hist[temp_v]
  else:
    res = [1 for i in range(n+1)]
  return res
    

to = [[] for i in range(m)]
for i in range(m):
  a, b = map(int, input().split())
  to[a-1].append(b-1)
if len(to) == 0:
  print(-1)
else:  
  c = [bfs(i, to) for i in range(n)]
  ans = [1 for i in range(n+1)]
  for i in range(n):
    if len(ans) > len(c[i]):
      ans = c[i]
  if len(ans) == n + 1:
    print(-1)
  else:
    print(len(ans))
    for v in ans[::-1]:
      print(v+1)