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

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)

INF = 10**18

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

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in g.graph[node]:
            if adj == root: #閉路を検出する
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    else:
        continue
    #最小の閉路なら条件を満たす
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)

if loopsize != INF:
    print(loopsize)
    for node in path:
        print(node + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

class Graph(): #directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append(e[1] - indexed)

INF = 10**18

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

g = Graph(N, edge)

loopsize = INF

for i in range(N):
    root = i
    stack = [root]
    visited = [0 for _ in range(N)]
    visited[root] = 1
    while stack:
        node = stack.pop()
        for adj in g.graph[node]:
            if adj == root: #閉路を検出
                break
            if visited[adj]:
                continue
            visited[adj] = 1
            stack.append(adj)
        else:
            continue
        break
    else:
        continue
    #閉路があるとき
    queue = deque([root])
    dist = [INF for _ in range(N)]
    dist[root] = 0
    prev = [None for _ in range(N)]
    while queue:
        node = queue.popleft()
        for adj in g.graph[node]:
            if adj == root:
                dist[root] = dist[node] + 1
                prev[root] = node
                break
            if dist[adj] != INF:
                continue
            dist[adj] = dist[node] + 1
            prev[adj] = node
            queue.append(adj)
        else:
            continue
        break
    #最小サイズの閉路なら条件を満たす
    if loopsize > dist[root]:
        loopsize = dist[root]
        path = [root]
        node = root
        while prev[node] != root:
            node = prev[node]
            path.append(node)
        res = path

if loopsize != INF:
    print(loopsize)
    for node in res:
        print(node + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0 and prev[nv] == -1:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
sys.setrecursionlimit(10 ** 6)
from collections import deque
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    AB = [tuple(map(int,input().split())) for _ in range(M)]
    for a,b in AB:
        G[a-1].append(b-1)

    Ans = [1]*(N+1)
    
    # 全ての頂点から, 閉路が存在しないかを確認する
    for s in range(N):
        prev = [-1]*N
        dist = [-1]*N
        dist[s] = 0
        dq = deque([s])
        while dq:
            v = dq.popleft()
            for nv in G[v]:
                if dist[nv] == -1:
                    dist[nv] = dist[v] + 1
                    prev[nv] = v
                    dq.append(nv)
                # 次が 0番目(開始地点) なら閉路あり
                if dist[nv] == 0:
                    prev[nv] = v

        # 開始地点の前 が -1でない => 閉路あり
        if prev[s] != -1:
            v = prev[s]
            ans = set()
            for _ in range(max(dist)+1):
                ans.add(prev[v])
                v = prev[v]
            if len(Ans) > len(ans):
                Ans = list(ans)
    
    if len(Ans) == N+1:
        print(-1)
    else:
        print(len(Ans))
        Ans.sort()
        for v in Ans:
            print(v+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def solve():
    N, M = map(int, input().split())
    edges = [set() for _ in range(N+1)]
    for a, b in (map(int, line.split()) for line in sys.stdin):
        edges[a].add(b)

    # 答えが見つかるまで、スタート地点は全て試します
    for start in range(1, N+1):
        visited = [0]*(N+1)

        dq = deque([(start, {start})])
        visited[start] = 1

        while dq:
            # 点と、これまで通ってきた頂点を取り出す
            v, route = dq.popleft()
            # これまで通ってきた頂点集合と、行き先の頂点集合の積集合をとる
            s = route & edges[v]
            # s=={start}でなければuとおr sが空集合でも通る。sが何やらいろいろあると、通れない。
            if not (not s or s == {start}):
                continue
            for dest in edges[v]:
                # startに戻ってきたら出力して終了
                if dest == start:
                    print(len(route))
                    print(*route, sep='\n')
                    exit()
                # 訪問済みであれば、スルー
                if visited[dest]:
                    continue
                visited[dest] = 1
                # destを始点として、通ってきた頂点にdestを追加したもの
                dq.append((dest, route | {dest}))

    print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
# https://atcoder.jp/contests/abc142/submissions/7764934
# ほぼまんま。


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

    # スタート地点は全て試す
    for start in range(N):
        visited = [0]*N
        Q = deque([(start, {start})])
        append, popleft = Q.append, Q.popleft
        visited[start] = 1

        while Q:
            v, route = popleft()
            # これまで通ってきた頂点と行き先の積集合
            s = route & E[v]
            # sが空集合(ループでない)か、行き先に始点のみが含まれる場合は継続
            # 行き先に始点以外の場所が含まれるなら、もっと良い始点の選び方がある。
            # if not (not s or (s == {start})):
            if s and s != {start}:
                continue
            for dest in E[v]:
                if dest == start:
                    print(len(route))
                    print(*[n+1 for n in route], sep="\n")
                    return
                if visited[dest]:
                    continue
                visited[dest] = 1
                append((dest, route | {dest}))
    print(-1)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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)

c = [0] * n
ans = []
def search_path(p, temp):
    c[p] = 1
    for x in e[p]:
        if x in temp:
            print(-99999)
            exit()
        else:
            search_path(x, temp + [x])


t = 1
for i in range(n):
    if c[i] == 0:
        ans = search_path(i, [i])

print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque


def find_shortest_cycle(G, s):
    dq = deque()
    N = len(G)
    INF = float('inf')
    dist = [INF] * N
    dist[s] = 0
    parent = [-1] * N

    ans_last = None # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSでループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点vからいける頂点の中に開始点があったら、ループである
            if dist[n] == 0:
                ans_last = v
                parent[n] = v
                break
            # まだ探索していない頂点なら次の探索候補にする
            elif dist[n] == INF:
                dist[n] = d + 1
                parent[n] = v
                dq.append(n)

    # ループが見つかった場合
    if ans_last:
        # ループの最後の頂点から、元の頂点をたどり、そのルートを逆にする
        g = ans_last
        route = [g]
        while g != s:
            g = parent[g]
            route.append(g)
        return list(reversed(route))
    
    # 見つからなかった場合はNoneを返す
    return None

def main():
    N, M, *A = map(int, read().split())

    G = [[] for i in range(N+1)]
    for a, b in zip(A[::2], A[1::2]):
        G[a].append(b)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    min_route = None
    for s in range(1, N+1):
        # 各頂点を開始点にしてループを探す
        route = find_shortest_cycle(G, s)
        # ループが複数ある場合、短いほうを採用
        if route:
            if min_route is None or len(route) < len(min_route):
                min_route = route
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

def shorten_cycle(G, route):
    # ループだとすでに分かってるルートに対して、
    # ショートカットが存在する場合はショートカットを行い、
    # ルートを短くする

    _next = {k: v for k, v in zip(route, route[1:]+route[:1])}
    v = route[0]
    while True:
        # もしvからroute内の、次の点ではない点nにいける場合
        for n in G[v]:
            # v -> x -> y -> n としていたところを、
            # v -> n とする
            if n in route and n != _next[v]:
                new_route = [n]
                s = n
                while s != v:
                    s = _next[s]
                    new_route.append(s)
                _next[v] = n
                # 無駄な部分を削除した新しい経路に対して、調査を最初からやり直す
                route = new_route
                v = route[0]
                break
        # 点vにショートカットがない場合
        else:
            # 次の点が最初の点の場合は、もうこれ以上ショートカットできないので終わり
            v = _next[v]
            if v == route[0]:
                break
    
    return route

def find_cycle(G, s):
    dq = deque()
    N = len(G)
    INF = float('inf')
    dist = [INF] * N
    dist[s] = 0
    parent = [-1] * N

    ans_last = None # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSでループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点vからいける頂点の中に開始点があったら、ループである
            if dist[n] == 0:
                ans_last = v
                parent[n] = v
                break
            # まだ探索していない頂点なら次の探索候補にする
            elif dist[n] == INF:
                dist[n] = d + 1
                parent[n] = v
                dq.append(n)

    # ループが見つかった場合
    if ans_last:
        # ループの最後の頂点から、元の頂点をたどり、そのルートを逆にする
        g = ans_last
        route = [g]
        while g != s:
            g = parent[g]
            route.append(g)
        return list(reversed(route))
    
    # 見つからなかった場合はNoneを返す
    return None

def main():
    N, M, *A = map(int, read().split())

    G = [[] for i in range(N+1)]
    for a, b in zip(A[::2], A[1::2]):
        G[a].append(b)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    min_route = None
    for s in range(1, N+1):
        # 各頂点を開始点にしてループを探す
        route = find_cycle(G, s)
        # ループが見つかった場合、そこからショートカットできる経路を探して終了
        if route:
            min_route = shorten_cycle(G, route)
            break
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque


def find_shortest_cycle(G, s):
    dq = deque()
    N = len(G)
    INF = float('inf')
    dist = [INF] * N
    dist[s] = 0
    parent = [-1] * N

    ans_last = None # sからループを探して見つかった時の、ループの最後の頂点番号
    dq.append(s)
    # BFSで、最短のループを見つける
    while dq and ans_last is None:
        v = dq.popleft()
        d = dist[v]
        for n in G[v]:
            # 頂点vからいける頂点の中に開始点があったら、ループである
            if dist[n] == 0:
                ans_last = v
                parent[n] = v
                break
            # まだ探索していない頂点なら次の探索候補にする
            elif dist[n] == INF:
                dist[n] = d + 1
                parent[n] = v
                dq.append(n)

    # ループが見つかった場合
    if ans_last:
        # ループの最後の頂点から、元の頂点をたどり、そのルートを逆にする
        g = ans_last
        route = [g]
        while g != s:
            g = parent[g]
            route.append(g)
        return list(reversed(route))
    
    # 見つからなかった場合はNoneを返す
    return None

def main():
    N, M, *A = map(int, read().split())

    G = [[] for i in range(N+1)]
    for a, b in zip(A[::2], A[1::2]):
        G[a].append(b)

    # すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ
    # [すべての頂点の入次数が 1、出次数が 1 のグラフ] -> ループ

    # 有向グラフ G=(V,E) に対し、次のような条件を満たす有向グラフ G′=(V′,E′) を G の誘導部分グラフと呼ぶ。
    # V′ は V の (空でない) 部分集合である。
    # E′ は、E の辺であって両端点がともに V′ に含まれるものすべてを含む集合である。

    # -> ループでも、ショートカットできるようなループはだめ

    # 例: 1 -> 2 -> 3 -> 4 -> 5
    #     ^    |         ^    |
    #     |    ----------|    |
    #     ---------------------
    # V' = {1, 2, 3, 4, 5} としてしまうと、
    # E' = {(1->2), (2->3), (3->4), (2->4), (4->5), (5->1)}
    # となってしまい、この誘導部分グラフG'=(V', E')において、
    # 頂点2の出次数が2になってしまう。（頂点4の入次数も2になってしまう）
    # V' = {1, 2, 4, 5} とすれば、
    # E' = {(1->2), (2->4), (4->5), (5->1)}
    # となり、すべての頂点の入次数が 1、出次数が 1 となる
    
    # つまり、ショートカットできない最短のループを1つでも見つければよい
    
    min_route = None
    for s in range(1, N+1):
        # 各頂点を開始点にしてループを探す
        route = find_shortest_cycle(G, s)
        # ループが複数ある場合、短いほうを採用
        if route:
            if min_route is None or len(route) < len(min_route):
                min_route = route
    
    if min_route:
        print(len(min_route), *min_route, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

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)

ret = [0] * (n + 1)
for start in range(n):
    parent = [-1] * n
    q = [start]
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            if j == start:
                loop = [i]
                while i != start:
                    i = parent[i]
                    loop.append(i)
                if len(ret) > len(loop):
                    ret = loop
                break
            if parent[j] == -1:
                parent[j] = i
                q.append(j)

if len(ret) > n:
    print(-1)
else:
    print(len(ret))
    for i in reversed(ret):
        print(i + 1)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
link = [[] for _ in range(n)]
ab=[]
for i in range(m):
    a,b = list(map(int,input().split()))
    ab.append([a,b])
    link[a-1].append(b-1)

from collections import deque
def best_cycle(a,b):
    a,b=itm
    a-=1
    b-=1
    Q = deque()
    Q.append([b,[b]])
    visited=[-1]*n
    visited[b]=1

    while Q:
        now,path = Q.popleft()
        for nxt in link[now]:
            if nxt==a: # goal
                return True,path + [nxt]
            if visited[nxt]!=-1:
                continue
            visited[nxt]=1
            Q.append([nxt,path + [nxt]])
    return False,[]

mn = 10**10
ans=[]
found=False

for itm in ab:
    a,b = itm
    ret,path = best_cycle(a,b)
    if ret and len(path) < mn:
        ans=path
        mn = len(path)
        found=True

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline


def solve():
    N, M = map(int, input().split())
    d = {i:[] for i in range(1, N+1)}
    l = []
    INF = 10**12
    v = INF

    for _ in range(M):
        A, B = map(int, input().split())
        d[A].append(B)
        l.append((A, B))

    ans = []
    for i, j in l:
        INF = 10**12
        dist = [-1]*(N+1)
        prev = [-1]*(N+1)
        dist[j] = 0
        prev[j] = 0
        q = deque([j])

        while q:
            a = q.popleft()
            for b in d[a]:
                if dist[b]==-1:
                    dist[b] = dist[a]+1
                    prev[b] = a
                    q.append(b)

        if v>dist[i]+1 and dist[i]!=-1:
            v = dist[i]+1
            buf = i
            ans = []
            while buf:
                ans.append(buf)
                buf = prev[buf]

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
d = {i:[] for i in range(1, N+1)}
l = []
INF = 10**12
v = INF

for _ in range(M):
    A, B = map(int, input().split())
    d[A].append(B)
    l.append((A, B))

ans = []
for i, j in l:
    INF = 10**12
    dist = [-1]*(N+1)
    prev = [-1]*(N+1)
    dist[j] = 0
    prev[j] = 0
    q = deque([j])

    while q:
        a = q.popleft()
        for b in d[a]:
            if dist[b]==-1:
                dist[b] = dist[a]+1
                prev[b] = a
                q.append(b)

    if v>dist[i]+1 and dist[i]!=-1:
        v = dist[i]+1
        buf = i
        ans = []
        while buf!=0:
            ans.append(buf)
            buf = prev[buf]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from collections import deque,defaultdict,Counter
def main():
    N,M = map(int,input().split())
    G = [[] for _ in range(N)]
    G_rev = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G_rev[b].append(a)
    
    s,g = None,None
    ans = INF
    q = deque([])
    for i in range(N):
        q.append(i)
        dist = [-1] * N
        dist[i] = 0
        while q:
            v = q.popleft()
            for e in G[v]:
                if i == e:
                    if ans > dist[v] + 1:
                        ans = dist[v] + 1
                        s,g = i,v
                elif dist[e] < 0:
                    dist[e] = dist[v] + 1
                    q.append(e)

    if ans == INF:
        print(-1)
    else:
        print(ans)
        q.append(s)
        dist = [-1] * N
        dist[s] = 0
        while q:
            v = q.popleft()
            for e in G[v]:
                if e == g:
                    dist[g] = dist[v] + 1
                    q.clear()
                    break
                elif dist[e] < 0:
                    dist[e] = dist[v] + 1
                    q.append(e)
        route = [g + 1]
        now = g
        while now != s:
            for e in G_rev[now]:
                if dist[e] == dist[now] - 1:
                    now = e
                    break
            route.append(now + 1)
        print('\n'.join(map(str,route)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

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

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

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


def joint(v, visit):
    if impossible[v]:
        return None
    visit = visit + [v]
    for u in link[v]:
        if u in visit:
            i = visit.index(u)
            return visit[i:]
        t = joint(u, visit)
        if t is not None:
            return t
    impossible[v] = True
    return None


def solve(l):
    n = len(l)
    d = {l[i]: i for i in range(n)}
    for i in range(n):
        x = l[i]
        for y in link[x]:
            if y in d:
                j = d[y]
                if (i + 1) % n == j:
                    continue
                if j < i:
                    l = l[j : i + 1]
                else:
                    l = l[: i + 1] + l[j:]
                return solve(l)
    return l
            

def main():
    t = None
    for i in range(N):
        t = joint(i, [])
        if t is not None:
            break
    if t is None:
        print(-1)
        return
    
    ans = solve(t)
    print(len(ans))
    for x in ans:
        print(x + 1)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
infi = 10 ** 10


def bfs(start):
    # res = 頂点数, サイクル最後の頂点、で持つ
    res = (infi, -1)
    dist = [-1] * (n + 1)
    par = [-1] * (n + 1)
    que = deque([])
    que.append(start)
    dist[start] = 0
    while que:
        v = que.popleft()
        for u in graph[v]:
            if dist[u] >= 0:
                continue
            dist[u] = dist[v] + 1
            par[u] = v
            que.append(u)
    for i in range(1, n + 1):
        if i == start:
            continue
        if dist[i] == -1:
            continue
        if start in graph[i]:
            if res[0] > dist[i] + 1:
                res = (dist[i] + 1, i)
    if res[0] == infi:
        return -1, []
    cycle_num = res[0]
    v = res[1]
    CYCLE = deque([])
    while v > 0:
        CYCLE.appendleft(v)
        v = par[v]

    return cycle_num, CYCLE


jisho = {}
ans = (-1, [])
cycle_num = infi
kouho_v = -1
for i in range(1, n + 1):
    temp_num, temp_cycle = bfs(i)
    if temp_num == -1:
        continue
    if cycle_num > temp_num:
        cycle_num = min(cycle_num, temp_num)
        kouho_v = i
        jisho[i] = temp_cycle

if kouho_v == -1:
    print(-1)
    exit()
else:
    ans_num = cycle_num
    ans_list = jisho[kouho_v]
    print(cycle_num)
    print(*ans_list, sep="\n")

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 find_loop(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = find_loop(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
    processed = set()
    i = cycle[0]
    while i not in processed:
        processed.add(i)
        for j in edges[i]:
            if j in nxt:
                k = nxt[i]
                while k != j:
                    k = nxt.pop(k)
                nxt[i] = j
        i = nxt[i]
    start = i
    ret = [i]
    i = nxt[i]
    while i != start:
        ret.append(i)
        i = nxt[i]
    return ret

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = find_loop(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

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 find_loop(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = find_loop(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    nxt = {i: j for (i, j) in zip(cycle, cycle[1:] + cycle[:1])}
    processed = set()
    i = cycle[0]
    while i not in processed:
        processed.add(i)
        for j in edges[i]:
            if j in nxt:
                k = i
                while k != j:
                    l = nxt[k]
                    del nxt[k]
                    k = l
                nxt[i] = j
        i = nxt[i]
    start = i
    ret = [i]
    i = nxt[i]
    while i != start:
        ret.append(i)
        i = nxt[i]
    return ret

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = find_loop(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)

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 dfs(index, visited, cycle):
    visited[index] = True
    cycle.append(index)
    for i in edges[index]:
        if visited.get(i):
            return cycle[cycle.index(i):]
        ret = dfs(i, visited, cycle)
        if ret:
            return ret
    visited[index] = False
    cycle.pop(-1)
    return None

def find_local_minimum(cycle):
    n = len(cycle)
    ind = {v: i for (i, v) in zip(range(n), cycle)}
    ret = []
    i = 0
    while True:
        ret.append(i)
        nxt = 0
        for j in [ind[v] for v in edges[cycle[i]] if v in ind]:
            if j < i:
                j += n
            nxt = max(nxt, j)
        if nxt >= n:
            ret = ret[ret.index(nxt % n):]
            break
        i += 1
        while i < nxt:
            del ind[cycle[i]]
            i += 1
    return [cycle[i % n] for i in ret]

cycle = None
visited = {}
for start in range(n):
    if start not in visited:
        cycle = dfs(start, visited, [])
        if cycle:
            break

if cycle:
    ret = find_local_minimum(cycle)
    print(len(ret))
    for i in ret:
        print(i + 1)
else:
    print(-1)