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 sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    global compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        global compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return


    cs = []
    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        c += 1
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)

    if len(cs) == 0:
        print(-1)
        sys.exit(0)
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print(len(l))
            print("\n".join([str(n + 1) for n in l]))
            sys.exit(0)
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

compo = []
cs = []
N = 0
M = 0
A = None
B = None
E = None

def main():
    global compo,cs,N,M,A,B,E
    N, M = rip()
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = rip()
        A[i] -= 1
        B[i] -= 1
    
    E = [[] for i in range(N)]
    for i in range(M):
        E[A[i]].append(B[i])
    
    compo = [-1] * N

    def dfs(cmp, route, hs):
        global compo,cs,N,M,A,B,E
        if(len(cs) > 0) : return
        now = route[len(route) - 1]
        for nxt in E[now]:
            if compo[nxt] == -1:
                compo[nxt] = cmp
                route.append(nxt)
                hs.add(nxt)
                dfs(cmp, route, hs)
                hs.remove(nxt)
                route.pop(-1)
            elif compo[nxt] == cmp:
                if nxt in hs:
                    cs = route[route.index(nxt):]
                return
            else:
                return


    cs = []
    c = 0
    for i in range(N):
        if(compo[i] != -1): continue
        c += 1
        a = []
        hs = set()
        a.append(i)
        hs.add(i)
        compo[i] = c
        dfs(c, a, hs)

    if len(cs) == 0:
        print(-1)
        sys.exit(0)
    
    l = cs
    while(True):
        di = dict()
        for i in range(len(l)):
            di[l[i]] = l[(i + 1) % len(l)]
        edx = -1
        for i in range(M):
            if A[i] in di and B[i] in di:
                if di[A[i]] != B[i]:
                    edx = i
                    break
        
        if edx == -1:
            print(len(l))
            print("\n".join([str(n + 1) for n in l]))
            sys.exit(0)
        
        di[A[edx]] = B[edx]
        nl = [A[edx], B[edx]]
        while True:
            nxt = di[nl[-1]]
            if nxt != nl[0]:
                nl.append(nxt)
            else:
                break
        l = nl

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
data=[[] for i in range(N+1)]
for i in range(M):
    A,B=map(int,input().split())
    data[A].append(B)
lst=[]
for i in range(1,N+1):
    flag=[0]*(N+1)
    parent=[0]*(N+1)
    que=[i]
    while que:
        h=[]
        for u in que:
            for v in data[u]:
                if flag[v]==0:
                    flag[v]=1
                    parent[v]=u
                    h.append(v)
        que=h
    if parent[i]==0:
        continue
    lsls=[i]
    zzz=i
    while True:
        zzz=parent[zzz]
        if zzz==i:
            break
        lsls.append(zzz)
    lst.append(lsls)
inf=float("inf")
k=inf
ans=None
for u in lst:
    if k>len(u):
        ans=u
        k=len(u)
if k==inf:
    print(-1)
else:
    print(k)
    for v in ans:
        print(v)

Submission status: Accepted

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

    # 各頂点から BFS を行い、全点間の距離をO(NM)で計算
    A=[None]*n
    for s in range(n):
        dist=[INF]*n
        dist[s]=0
        Q=deque([s])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(dist[nv]!=INF): continue
                dist[nv]=dist[v]+1
                if(nv!=s): Q.append(nv)
            if(v==s): dist[v]=INF
        A[s]=dist

    d,v0=min((A[v][v],v) for v in range(n))
    if(d==INF):
        print(-1)
        return

    print(d)
    # v から v の最小のループを求める
    prev=[None]*n
    used=[0]*n
    used[0]=1
    Q=deque([v0])
    while(Q):
        flag=True
        v=Q.popleft()
        for nv in E[v]:
            if(nv==v0):
                flag=False
                break
            if(used[nv]): continue
            used[nv]=1
            prev[nv]=v
            Q.append(nv)
        if(not flag): break

    ans=[]
    while(v!=v0):
        ans.append(v)
        v=prev[v]

    ans.append(v0)
    print(*map(lambda x:x+1,ans[::-1]),sep='\n')
resolve()

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    G[a-1].append(b-1)
K=[0 for i in range(N)]
for i in range(N):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(N) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
if len(res)==N:
    print(-1)
else:
    print(0)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10000)
N, M = map(int, input().split())
table = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    table[a-1].append(b-1)

visit = [False] * N
visit2 = [False] * N
g = []


def dfs(v):
    g.append(v)
    if visit[v]:
        return True
    visit[v] = True
    visit2[v] = True
    for u in table[v]:
        if dfs(u):
            return True
    g.pop()
    visit[v] = False
    return False


for i in range(N):
    g = []
    if not visit2[i]:
        if dfs(i):
            break
else:
    print(-1)
    exit()
print(0)
# ans = [v+1 for v in g[g.index(g[-1]):-1]]
# print(len(ans))
# print(*ans, sep="\n")

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[set() for _ in [0]*n]
    g2=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g2[b-1].add(a-1) for a,b in ab]

    def bfs(start,graph):
        temp=[[start,{start}]]
        while temp:
            temp2=[]
            for j,k in temp:
                for i in graph[j]:
                    if i in k:
                        return j,k
                    else:
                        temp2.append([i,k|{i}])
            temp=temp2
        return None,None

    return_set_pre=set(range(n))
    for i in range(n):
        now,return_set=bfs(i,g)
        if return_set!=None:
            break
    if return_set==None:
        print(-1)
        return 0
    while True:
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g2)
        for i in return_set_pre-return_set:
            g[i]={}
            g2[i]={}
        for i in return_set:
            g[i]=g[i]&return_set
            g2[i]=g2[i]&return_set
        l1=len([1 for i in range(n) if len(g[i])==1])
        l2=len([1 for i in range(n) if len(g2[i])==1])
        l=len(return_set)
        if l==l1 and l==l2:
            break
        return_set_pre=return_set
        now,return_set=bfs(now,g)
    print(len(return_set))
    for i in return_set:
        print(i+1)
main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = [0] * (n + 1)
import collections
g = collections.defaultdict(set)

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

def minCircle(s):
    f = [None] * n
    visited = set()
    q = []
    q.append(s)
    while q:
        node = q.pop()
        for nei in g[node]:
            if nei not in visited:
                f[nei] = node
                visited.add(nei)
                q.append(nei)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p is not None and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(n):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == n + 1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i+1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
N = 1010
ans = [0] * (N +1)
g = [[] for _ in range(N)]

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

#n, m = 6, 9
#g = [[], [2],[3],[4], [5], [1,6,2],[1,2]]
def minCircle(s):
    f = [0] * N
    visited = set()
    q = []
    q.append(s)
    while q:
        p = q.pop()
        for c in g[p]:
            if c not in visited:
                f[c] = p
                visited.add(c)
                q.append(c)
        if s in visited:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(1, n+1):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == N+1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
N = 1010
ans = [0] * (N +1)
g = [[] for _ in range(N)]

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

#n, m = 6, 9
#g = [[], [2],[3],[4], [5], [1,6,2],[1,2]]
def minCircle(s):
    f = [0] * N
    d = [0]* N
    q = []
    q.append(s)
    while q:
        p = q.pop()
        for c in g[p]:
            if not d[c]:
                f[c] = p
                d[c] = 1
                q.append(c)
        if d[s]:
            break
    p = f[s]
    ret = []
    ret.append(s)
    while p and p!= s:
        ret.append(p)
        p = f[p]
    return ret

for i in range(1, n+1):
    t = minCircle(i)
    if len(t) > 1 and len(t) < len(ans):
        ans = t
if len(ans) == N+1:
    print(-1)
else:
    print(len(ans))
    for i in ans:
        print(i)

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:
import sys
input = sys.stdin.readline

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

L = 10**14
num = -1
for n in range(N):
    q = [n]
    checked = [False]*N
    checked[n] = True
    before = [None]*N
    c = 0
    ok = False
    while q:
        c += 1
        qq = []
        for p in q:
            for np in graph[p]:
                if not checked[np]:
                    before[np] = p
                    qq.append(np)
                    checked[np] = True
                elif np == n:
                    before[np] = p
                    ok = True
                    break
        if ok: break
        q = qq
    
    if ok and c < L:
        L = c
        num = n
        ans = []
        k = n
        for _ in range(c):
            k = before[k]
            ans.append(k+1)

if num == -1:
    print(-1)
else:
    print(len(ans))
    for a in reversed(ans):
        print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

def nasu(x, e):
  D[x] = 1
  if x not in R:
    return []
  for i in R[x]:
    if i == e:
      return [i]
    if D[i] == 0:
      t = nasu(i, e)
      if t != []:
        return [i] + t
  return []

for i in range(1, N + 1):
  D = [0] * (N + 1)
  L = nasu(i, i)
  if L != []:
    break
else:
  print(-1)
  exit()

D = [0] * (N + 1)
for i in L:
  D[i] = 1

LEN = len(L)
L = L + L

i = 0
while i < LEN:
  for j in range(i + LEN - 1, i, -1):
    if D[L[j]] != 0 and L[j] in R[L[i]]:
      for k in range(j - 1, i, -1):
        D[L[k]] = 0
      i = j
      break

A = []
for i in range(LEN):
  if D[L[i]] == 1:
    A.append(L[i])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    _, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return

#F
def F():
    n,m = LI()
    edg = [[] for i in range(n)]
    redg = [[] for i in range(n)]
    
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        redg[b].append(a)

    def dijkstra(start):
        dist = [inf] * n
        dist[start] = 0
        q = [(0,start)]
        while q:
            du, u = heappop(q)
            for i in edg[u]:
                if du + 1 < dist[i]:
                    dist[i] = du + 1
                    heappush(q, (du + 1, i))
        return dist
    
    d = [None] * n
    for i in range(n):
        d[i] = dijkstra(i)

    tmp = inf
    tt = None
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if tmp > d[i][j] + d[j][i]:
                tt = (i, j)
                tmp = d[i][j] + d[j][i]

    if tmp != inf:
        print(tmp)
        s, g = tt
        ans1 = [s]
        ans2 = [g]
        q = deque([s])
        while q:
            a = q.pop()
            for ai in redg[a]:
                if g != ai and d[g][ai] + 1 == d[g][a]:
                    ans1.append(ai)
                    q.append(ai)
                    break
        q = deque([g])
        while q:
            a = q.pop()
            for ai in redg[a]:
                if s != ai and d[s][ai] + 1 == d[s][a]:
                    ans2.append(ai)
                    q.append(ai)
                    break
        ans = ans1 + ans2
        for a in ans:
            print(a+1)

    else:
        print(-1)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Accepted

Solution code:
import sys
import copy
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: # ENTER, EMPTY
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = copy.copy(chain)
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print(-1)
    exit()

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print(len(loop))
for l in loop:
    print(l+1)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
uv = [ set() for _ in range(N)]
vu = [ set() for _ in range(N)]
for _ in range(M):
    A, B = inpl()
    uv[A-1].add(B-1)
    vu[B-1].add(A-1)

EMPTY, LOOP, TREE = 0, 1, 2
ENTER, EXIT = 0, 1
status = [EMPTY] * N
for s in range(N):
    states_pool = [(s,[],ENTER)]
    while states_pool:
        u, chain, flag = states_pool.pop()
        if flag == EXIT or status[u] == TREE:
            status[u] = TREE
            continue
        elif status[u] == LOOP:
            break
        else: # ENTER, EMPTY
            status[u] = LOOP
            states_pool.append((u,chain,EXIT))
            new_chain = chain.copy()
            new_chain.append(u)
            for c in uv[u]:
                states_pool.append((c, new_chain, ENTER))
    else:
        continue
    break
else:
    print(-1)
    exit()

n = 0
while chain[n] != u:
    n += 1
chain = chain[n:]
L = len(chain)
nextnode = [None]*N
for i in range(L-1):
    nextnode[chain[i]] = chain[i+1]
nextnode[chain[L-1]] = chain[0]
pos = [None]*N
for p in range(len(chain)):
    pos[chain[p]] = p
i = 0
while i < L:
    h = 1
    c = chain[(i+1)%L]
    for j in uv[chain[i % L]]:
        p = pos[j]
        if p is None:
            continue
        else:
            if (p-i)%L > h:
                h = (p-i)%L
                c = j
    nextnode[chain[i % L]] = c
    i += 1
    while chain[i % L] != c:
        pos[chain[i % L]] = None
        i += 1

loop = [c]
k = c
while nextnode[k] != c:
    k = nextnode[k]
    loop.append(k)
print(len(loop))
for l in loop:
    print(l+1)

Submission status: Accepted

Solution code:
def find_cycle(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  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 = find_cycle(N, AB)
# print("cycle:", cycle)
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:
def dfs(N, AB):
  status = [-1] * N
  for i in range(N):
      if status[i] == 1:
          continue
      stack = [i]
      status[i] = 0
      while stack:
          print("stack:", 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)
                  print("stack:", stack, "n:", n, "idx:", idx)
                  cycle = stack[idx:]
                  
                  return cycle
          else:                  
              status[v] = 1
              stack.pop()
 
  return False

def dfs_2(N, AB):
  for c in range(N):
    stack = [(c, [])]
    while stack:
      # print("stack:", stack)
      curr, visited = stack.pop()
      if curr in visited:
        # print("cycle found:", curr)
        return visited
      else:
        # print("adding in visited:", curr)
        for i in AB[curr]:
          stack.append((i, visited+[curr]))
  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)

# print("AB:")
# for i in AB:
#   print(i)
cycle = dfs_2(N, AB)
# print("cycle:", cycle)
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:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M=map(int, raw_input().split())
al=[ [] for i in range(N+1) ]
edge=[]

for i in range(M):
	a,b=map(int, sys.stdin.readline().split())
	al[a].append(b)
	edge.append((a,b))


def bfs(start,end):
	Visit=[ 0 for _ in range(N+1) ]	#訪問
	d=[ float("inf") for _ in range(N+1)]	#距離
	prev=[ None for _ in range(N+1)]	#経路復元
	d[start]=0
	q=deque()
	q.append(start)
	Visit[start]=1

	while q:
		fro=q.popleft()
		for to in al[fro]:
			if Visit[to]==0:
				Visit[to]=1
				alt=d[fro]+1
				if alt<d[to]:
					d[to]=alt
					prev[to]=fro
				q.append(to)
	return d[end],prev


K=float("inf")
v=[]
start=None
end=None

for x,y in edge:
	kyori,keiro=bfs(y,x)
	if kyori<K:
		K=kyori+1
		v=keiro
		start=y
		end=x

if K==float("inf"):
	print -1
else:
	print K
	print end
	fro=end
	while fro!=start:
		fro=v[fro]
		print fro

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
edges = [[] for _ in range(n)]

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


def get_first_cycle(n, edges):
    seen = [-1] * n  # seen: -1: 未確認, 0: 非cycleのnode, 1: cycle候補
    for start in range(n):
        if seen[start] == 0:
            continue
        seen[start] = 1
        path = [start]
        while path:
            now = path[-1]
            if not edges[now]:
                path.pop()
                seen[now] = 0
                continue

            next_node = edges[now].pop()
            if seen[next_node] == -1:
                path.append(next_node)
                seen[next_node] = 1

            elif seen[next_node] == 1:
                idx = path.index(next_node)
                cycle = path[idx:]
                return cycle
    return False


cycle = get_first_cycle(n, edges)
if not cycle:
    print(-1)
    exit()

nodes = set(cycle)
length = len(cycle)
i = 0
while i < length:
    now = cycle[i]
    routes = edges[now]
    while routes:
        to = routes.pop()
        if to in nodes:
            update = True
            idx = cycle.index(to)
            cycle = cycle[:i+1] + cycle[idx:]
            nodes = set(cycle)
            length = len(cycle)
            break
    i += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC142 F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
edge = [[] for _ in range(n)]
for _ in range(m):
    a,b = LI()
    edge[a-1].append(b-1)

visited = [False]*n
def dfs(s):
    if visited[s]:
        return True
    visited[s] = True
    for i in edge[s]:
        if dfs(i):
            return True
    visited[s] = False
    return False

for i in range(n):
    if dfs(i):
        print(0)
        break
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import*
n,m,*t=map(int,open(0).read().split())
i=[0]*n
o=[[]for _ in i]
for a,b in zip(*[iter(t)]*2):
  o[a-1]+=b-1,
  i[b-1]+=1
q,r=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))