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: Wrong Answer

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)

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)
                print(len(loop))
                for i in reversed(loop):
                    print(i + 1)
                exit(0)
            if parent[j] == -1:
                parent[j] = i
                q.append(j)

print(-1)

Submission status: Wrong Answer

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

def doit(src):
    visited = [False] * n
    q = [src]
    visited[src] = True
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            if not visited[j]:
                visited[j] = True
                q.append(j)

    indegree = [0] * n
    goals = set()
    for i in range(n):
        if visited[i]:
            for j in edges[i]:
                if visited[j]:
                    if j == src:
                        goals.add(i)
                    else:
                        indegree[j] += 1

    parent = [-1] * n
    q = [src]
    while len(q) > 0:
        i = q.pop(0)
        if i in goals:
            loop = set(edges[i])
            ret = [i + 1]
            while i != src:
                i = parent[i]
                ret.append(i + 1)
            return ret
        for j in edges[i]:
            if parent[j] < 0:
                parent[j] = i
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    return None

for src in range(n):
    ret = doit(src)
    if ret:
        print(len(ret))
        for i in reversed(ret):
            print(i)
        exit(0)
print(-1)

Submission status: Wrong Answer

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

def doit(src):
    indegree = [0] * n
    parent = [-1] * n
    goals = set()
    for i in range(n):
        for j in edges[i]:
            if j == src:
                goals.add(i)
            else:
                indegree[j] += 1
    q = [i for i in range(n) if indegree[i] == 0 and i != src]
    while len(q) > 0:
        i = q.pop(0)
        for j in edges[i]:
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    q = [src]
    while len(q) > 0:
        i = q.pop(0)
        if i in goals:
            loop = set(edges[i])
            ret = [i + 1]
            while i != src:
                i = parent[i]
                ret.append(i + 1)
            return ret
        for j in edges[i]:
            if parent[j] < 0:
                parent[j] = i
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    return None

for src in range(n):
    ret = doit(src)
    if ret:
        print(len(ret))
        for i in reversed(ret):
            print(i)
        exit(0)
print(-1)

Submission status: Wrong Answer

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

def doit(src):
    indegree = [0] * n
    parent = [-1] * n
    goals = set()
    for i in range(n):
        for j in edges[i]:
            if j == src:
                goals.add(i)
            else:
                indegree[j] += 1
    q = [src]
    while len(q) > 0:
        i = q.pop(0)
        if i in goals:
            loop = set(edges[i])
            ret = [i + 1]
            ok = True
            while i != src:
                if i in loop:
                    ok = False
                    break
                i = parent[i]
                ret.append(i + 1)
            if ok:
                return ret
        for j in edges[i]:
            if parent[j] < 0:
                parent[j] = i
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    return None

for src in range(n):
    ret = doit(src)
    if ret:
        print(len(ret))
        for i in reversed(ret):
            print(i)
        exit(0)
print(-1)

Submission status: Wrong Answer

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

def doit(src):
    indegree = [0] * n
    parent = [-1] * n
    goals = set()
    for i in range(n):
        for j in edges[i]:
            if j == src:
                goals.add(i)
            else:
                indegree[j] += 1
    q = [src]
    while len(q) > 0:
        i = q.pop(0)
        if i in goals:
            ret = [i + 1]
            while i != src:
                i = parent[i]
                ret.append(i + 1)
            return ret
        for j in edges[i]:
            if parent[j] < 0:
                parent[j] = i
            indegree[j] -= 1
            if indegree[j] == 0:
                q.append(j)
    return None

for src in range(n):
    ret = doit(src)
    if ret:
        print(len(ret))
        for i in reversed(ret):
            print(i)
        exit(0)
print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)


    def bfs(start):
        pre = [-1]*n
        d = deque([start])
        res = []

        while d:
            v = d.popleft()
            for nv in adj[v]:
                if nv == start:
                    path = []
                    while v != -1:
                        path.append(v+1)
                        v = pre[v]
                    if not res or len(res) > len(path):
                        res = path
                    break

                if pre[nv] != -1:
                    continue
                pre[nv] = v
                d.append(nv)

        return res
    
    res = [0]*(n+1)
    for i in range(n):
        temp = bfs(i)
        if temp and len(res) > len(temp):
            res = temp
    if res:
        print(len(res))
        print(*res, sep='\n')
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(m):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)

    # 始点, 今回見る点
    def dfs(s, v):
        for nv in adj[v]:
            if nv == s:
                return [v]
            if visited[nv] == 1:
                continue
            visited[nv] = 1
            res = dfs(s, nv)
            if res != -1:
                res.append(v)
                return res
        return -1


    for s in range(n):
        visited = [0]*n
        visited[s] = 1
        heiro = dfs(s, s)
        if heiro != -1:
            break
    else:
        print(-1)
        exit()
    heiro = heiro[::-1]

    def graph(s, g):
        res = [s]
        d = deque([s])
        for i in range(len(heiro)):
            if heiro[i] == s:
                idx = i
                break
        while d:
            v = d.popleft()
            for nv in adj[v]:
                if visited[nv] == 1 and nv == g:
                    res.append(nv)
                    return res
            d.append(heiro[idx+1])
            res.append(heiro[idx+1])
            idx += 1
            if res[-1] == heiro[-2]:
                return res

    while True:
        heiro.append(heiro[0])
        visited = [0]*n
        f = 0
        for i in heiro:
            visited[i] = 1
        new_heiro = [heiro[0]]
        for i in range(len(heiro)-1):
            for nv in adj[heiro[i]]:
                if visited[nv] == 1 and nv != heiro[i+1]:
                    new_heiro = graph(nv, heiro[i])
                    f = 1
                    break
            else:
                new_heiro.append(heiro[len(new_heiro)])
            if f:
                heiro = new_heiro
                break
        else:
            break

    print(len(heiro)-1)
    for i in heiro[:-1]:
        print(i+1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = queue.Queue()
	Q.put(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	while not Q.empty():
		v = Q.get()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.put(i)
	# print(prev)

	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return dist[g], path[::-1]
	else:
		return INF, []

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)

	ans = 100000
	path = None
	for i in range(M):
		predis, prepath = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath

	if ans == 100000:
		print(-1)
	else:
		print(ans)
		for i in path:
			print(i + 1)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.judge = "Yes"
		self.prev = [None] * N
		self.path = []
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.Q.put(i)
					self.visit[i] = "Yes"
					self.prev[i] = v
				else:
					if i == s:
						self.judge = "No"
						while True:
							self.path.append(v)
							v = self.prev[v]
							if v == None:
								break
						break

	def cycle(self):
		if self.judge == "No":
			return list(reversed(self.path))
		else:
			return []

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

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)

	cycle_dist = INF
	cycle_path = None
	for i in range(N):
		BF = BFS(G, i, N)
		dist_path = BF.cycle()
		dist_var = len(dist_path)
		if dist_path != []:
			if dist_var < cycle_dist:
				cycle_dist = dist_var
				cycle_path = dist_path

	if cycle_dist == INF:
		print(-1)
	else:
		print(cycle_dist)
		for i in cycle_path:
			print(i + 1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.judge = "Yes"
		self.prev = [None] * N
		self.path = []
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
					self.prev[i] = v
				else:
					if i == s:
						self.judge = "No"
						while True:
							self.path.append(v)
							v = self.prev[v]
							if v == None:
								break
						break

	def cycle(self):
		if self.judge == "No":
			return list(reversed(self.path))
		else:
			return []
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)

	cycle_dist = INF
	cycle_path = None
	for i in range(N):
		BF = BFS(G, i, N)
		dist_path = BF.cycle()
		dist_var = len(dist_path)
		if dist_path != []:
			if dist_var < cycle_dist:
				cycle_dist = dist_var
				cycle_path = dist_path

	if cycle_dist == INF:
		print(-1)
	else:
		print(cycle_dist)
		for i in cycle_path:
			print(i + 1)


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
graph = [[] for _ in range(n)]


for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append(y)

flag = 0
start = 0
stack = []
dist = [-1] * n
seen = [False] * n
finished = [False] * n
stack.append(start)
while stack:
    v = stack[-1]
    seen[v] = True
    if not graph[v]:
        # 帰りがけ
        _ = stack.pop()  # 頂点vを取り除く
        finished[v] = True
        continue
    for u in graph[v]:
        u = graph[v].pop()
        if seen[u] is True and finished[u] is False:
            flag = 1
            num = u
            break
        stack.append(u)
    if flag:
        break

if flag:
    k = len(stack)
    for i in range(k):
        if num == stack[i]:
            idx = i
        stack[i]+=1
    loop = stack[idx:]
    k-=idx
    print(k)
    print(*loop, sep="\n")
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
import copy
def myhash(v):
    r = 0
    for i in v:
        r += pow(2, i)
    return r
def myhash2(r):
    return bin(r)[2:]
def main():
    N, M  = map(int, input().split())
    l = [[] for _ in range(N)]
    r = []
    for _ in range(M):
        a, b = map(int, input().split())
        l[a-1].append(b-1)
    a = set()
    def cyclic(n, l, v):
        ans = []
        v.add(n)
        for i in  l[n]:
            if i in v:
                a.add(myhash(v))
                return
                #return True, v
        for i in l[n]:
            v2 = copy.deepcopy(v)
            cyclic(i, l, v2)
        return
    for i in range(N):
        v = set()
        cyclic(i, l, v)
    if a:
        m = 100000
        rr = None
        for i in a:
            x = myhash2(i).count('1')
            if m > x:
                m = x
                rr = i
        print(m)
        for i,v in enumerate(myhash2(rr)):
            if v == '1':
                print(N-i)
    else:
        print(-1)
    return -1
main()

Submission status: Wrong Answer

Solution code:
print(0)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
is_root = [True] * (N+1)
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)
    is_root[B] = False
visited = [False] * (N+1)
ancestors = set()

def dfs(v):
    visited[v] = True
    ancestors.add(v)
    for c in G[v]:
        if c in ancestors:
            return [v, c]
        ret = dfs(c)
        if ret:
            if v == ret[-1]:
                print(len(ret))
                print(*ret, sep='\n')
                exit()
            return [v] + ret
    ancestors.remove(v)


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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
from collections import deque

links_rev = [set() for _ in range(n+1)]
out = [0] * (n+1)
for _ in range(m):
    a,b = map(int, input().split())
    links_rev[b].add(a)
    out[a] += 1

ends = deque()
for i in range(1,n+1):
    if(out[i] == 0):
        ends.append(i)

while(ends):
    i = ends.pop()
    for j in links_rev[i]:
        out[j] -= 1
        if(out[j]==0):
            ends.append(j)
    links_rev[i] = set()

if(sum(out) == 0):
    print(-1)
    exit()

links = [[] for _ in range(n+1)]
start = 0
for i,tmp in enumerate(links_rev):
    if(tmp):
        now = i
        for j in tmp:
            links[j].append(i)

done = set()
while(True):
    if(now in done):
        break
    done.add(now)
    now = links[now][0]

done = set()
while(True):
    if(now in done):
        break
    done.add(now)
    now = links[now][0]

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

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる


    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる






n,k = m()

g = cl.defaultdict(set)

gb = cl.defaultdict(set)
for i in range(k):
    a,b = m()
    a -= 1
    b -= 1
    g[a].add(b)
    gb[b].add(a)

fl = [0 for i in range(n)]

ok = [1 for i in range(n)]

fr = 0

co = 0

while True:

    for i in range(n):
        fl[i] = 0

    for i in range(n):
        if fl[i] == 0 and ok[i]:
            de = cl.deque([i])
            fr = 0
            while len(de) != 0:
                po = de.popleft()
                for j in g[po]:
                    if (fl[j] == 0) and ok[j]:
                        fl[j] = fl[po] + 1
                        de.append(j)
                    elif not (fl[j] == 0):
                        fr = 1
                        break
                if fr:
                    break
            if fr:
                print(fl,j,po)
                start = po
                end = j
                de = cl.deque([[start]])
                fr = 0
                while len(de) != 0:
                    po = de.popleft()
                    for j in gb[po[-1]]:
                        print(start,fl[j]+1,fl[po[-1]])
                        if end == j:
                            po = po + [end]
                            for _ in range(n):
                                ok[_] = 0
                            for _ in po:
                                ok[_] = 1
                            fr = 1
                            break
                        elif fl[j]+1 == fl[po[-1]]:
                            de.append(po + [j])
                    if fr:
                        break
                break

    if not fr:
        if co == 0:
            print(-1)
            exit()
        else:
            print(sum(ok))
            for i in range(n):
                if ok[i]:
                    print(i+1)
    co += 1


print(list(Topo_sort(g,n)))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    if sum(co.values()) != 0:
        ans = []
        for i,j in co.items():
            if j == 1:
                ans.append(i)
        print(len(ans))
        for i in ans:
            print(i+1)
    else:
        print(-1)

    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる


n,k = m()

g = cl.defaultdict(set)
for i in range(k):
    a,b = m()
    a -= 1
    b -= 1
    g[a].add(b)



list(Topo_sort(g,n))

Submission status: Wrong Answer

Solution code:
def examA():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """
        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, L = LI()
    V, D = LI()
    X = [LI()for _ in range(N)]
    X.append([0,V,D])
    X.append([L,0,0])
    X.sort()
    V = [[]for _ in range(N+2)]
    for i in range(N+1):
        x1, v1, d1 = X[i]
        r = x1 + d1
        for j in range(i+1,N+2):
            x2, v2, d2 = X[j]
            if r<x2:
                break
            cost = (x2-x1)/v1
            V[i].append((j,cost))

    dij = Dijkstra(V, 0)
    ans = dij.dist[-1]
    if ans>=inf:
        print("impossible")
        return
    print('{:.18f}'.format(ans))
    return

def examB():
    N, K = LI()
    H = 11; W = 7
    S = [[0]*(W+1) for _ in range(H+3)]
    for h in range(H+2):
        for w in range(W):
            S[h+1][w+1] = (S[h][w+1] + S[h+1][w] - S[h][w] + (7*h+w+1))
    #print(S)
    base = 0
    for h in range(H):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                base += 1
                #print(h,w)
    ans = base * ((N-2)//11)
    #print(ans)
    rest = (N-2)%11
    for h in range(rest):
        for w in range(W-2):
            cur = S[h+3][w+3] - S[h+3][w] - S[h][w+3] + S[h][w]
            if cur%11==K:
                ans += 1
                #print(h,w)
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    loop = 2**N
    ans = inf
    for i in range(loop):
        cnt = 0
        need = 0
        highest = 0
        for j in range(N):
            if i&(1<<j)==0:
                if highest<A[j]:
                    need = inf
                    break
                continue
            cnt += 1
            if highest>=A[j]:
                need += (highest+1-A[j])
                highest = highest + 1
            else:
                highest = A[j]
        if cnt>=K and need<ans:
            ans = need
        #print(need)
    print(ans)
    return

def examD():
    # 参考 https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61
    def cycle(neighbor, start, ring_size, node, visitable):
        stack = []
        stack.append(start)
        path = [{} for _ in range(node)]
        path[start] = {start}
        while (stack):
            last = stack.pop()
            curr_path = path[last]
            if len(curr_path) > ring_size:
                continue
            for nei in neighbor[last]:
                if start == nei:
                    return curr_path
                if nei in curr_path:
                    return cycle(neighbor,nei,len(curr_path)-len(path[nei])+1,node, visitable)
                if (nei not in visitable) or len(curr_path)==ring_size:
                    continue
                path[nei] = curr_path | {nei}
                stack.append(nei)
        return -1
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a,b = LI()
        a -= 1; b -= 1
        V[a].append(b)
    #print(V)
    loop = -1
    visitable = set([i for i in range(N)])
    for i in range(N-1):
        loop = cycle(V,i,N-i,N,visitable)
        if type(loop) is set:
            break
        visitable.discard(i)
    if type(loop) is not set:
        print(-1)
        return
    #print(loop)
    while(True):
        visitable = deepcopy(loop)
        next = -1
        num = len(loop)-1
        for k in loop:
            next = cycle(V,k,min(num,len(visitable)),N,visitable)
            #print(len(visitable)-1,next)
            if type(next) is set:
                break
            visitable.discard(k)
        if type(next) is not set:
            break
        loop = deepcopy(next)

    ans = loop
    print(len(ans))
    for v in ans:
        print(v+1)
    return

import sys,bisect,itertools,heapq,math,random
from copy import copy,deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()