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:
import sys
N,M=map(int,input().split())
d=[set()for _ in range(N+1)]
def f(v,h,q):
 if d[v]&q:
  l=[]
  for x in h[::-1]:
   l+=[x]
   if x in d[v]:break
  print("\n".join(str(x)for x in[len(l)]+l[::-1]));sys.exit()
 for u in d[v]:f(u,h+[u],q|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;f(v,[v],{v});"*N)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.add(v)
    if d[v]&pvs:
        l=[]
        for x in path[::-1]:
            l+=[x]
            if x in d[v]:break
        print("\n".join(str(x)for x in[len(l)]+l[::-1]));sys.exit()
    for u in d[v]:dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
dfs(1,[1],{1})
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.add(v)
    for u in d[v]:
        if u in pvs:
            xs=[]
            c = 0
            for x in path[::-1]:
                c+=1
                xs.append(x)
                if x in d[v]:break
            print(c)
            for x in xs:
                print(x)
            sys.exit()
        if u in vs:continue
        dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
dfs(1,[1],{1})
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.add(v)
    for u in d[v]:
        if u in pvs:
            r=""
            c = 0
            for x in path[::-1]:
                c+=1
                r+="\n%d"%x
                if x in d[v]:break
            print(("%s\n%d"%(r,c))[::-1].strip());sys.exit()
        if u in vs:continue
        dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
dfs(1,[1],{1})
print(-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
vs=set()
def dfs(v,path,pvs):
    lp=l=N+1
    for u in d[v]:
        if u in pvs:
            for i, c in enumerate(path):
                if c == u:
                    break
            nlp = path[i+1:]+[u]
            nl = len(nlp)
            if nl < l:
                lp, l = nlp, nl
        if u in vs:
            continue
        vs.add(u)
        nl, nlp = dfs(u,path+[u],pvs|{u})
        if nl < l:
            lp, l = nlp, nl
    return l,lp
d = [set() for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    d[a].add(b)

l,lp=dfs(1,[1],{1})
if l<=N:
	print("\n".join(str(x) for x in[l]+lp))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.add(v)
    for u in d[v]:
        if u in pvs:
            r=""
            c = 0
            for x in path[::-1]:
                c+=1
                r+="\n%d"%x
                if x in d[v]:break
            print(("%s\n%d"%(r,c))[::-1].strip());sys.exit()
        if u in vs:continue
        dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;dfs(v,[v],{v});"*N)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.add(v)
    if d[v]&pvs:
        r=""
        for x in path[::-1]:
            r+="\n%d"%x
            if x in d[v]:break
        print(("%s\n%d"%(r,len(r.split())))[::-1]);sys.exit()
    for u in d[v]:
        if u in vs:continue
        dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;dfs(v,[v],{v});"*N)
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
vs,d=set(range(N+1)),[set()for _ in range(N+1)]
def dfs(v,path,pvs):
    vs.discard(v)
    if d[v]&pvs:
        r=""
        for x in path[::-1]:
            r+="\n%d"%x
            if x in d[v]:break
        print(("%s\n%d"%(r,len(r.split())))[::-1]);sys.exit()
    for u in d[v]:dfs(u,path+[u],pvs|{u})
for _ in range(M):a,b=map(int,input().split());d[a].add(b)
v=0;exec("v+=1;dfs(v,[v],{v});"*N)
print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def find_cycle(graph, vst):
    que = deque([vst])
    dist = [-1] * n
    pre = [-1] * n
    dist[vst] = 0
    flag = False
    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
            if pre[cur] != nxt and nxt == vst:
                flag = True
                break
            if dist[nxt] != -1:
                continue
            pre[nxt] = cur
            dist[nxt] = dist[cur] + 1
            que += [nxt]
        if flag:
            v = cur
            cycle = []
            while v != -1:
                cycle += [v]
                v = pre[v]
            return cycle


ret_len = INF
n, m = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a - 1] += [b - 1]


min_cycle = 0
for vst in range(n):
    cycle = find_cycle(graph, vst)
    if cycle and len(cycle) < ret_len:
        min_cycle = cycle
        ret_len = len(cycle)


if min_cycle:
    print(ret_len)
    for i in min_cycle:
        print(i + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def find_cycle(graph, vst):
    que = deque([vst])
    dist = [-1] * n
    pre = [-1] * n
    dist[vst] = 0
    flag = False
    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
            if pre[cur] != nxt and nxt == vst:
                flag = True
                break
            if dist[nxt] != -1:
                continue
            pre[nxt] = cur
            dist[nxt] = dist[cur] + 1
            que += [nxt]
        if flag:
            v = cur
            cycle = []
            while v != -1:
                cycle += [v]
                v = pre[v]
            return cycle


ret_len = INF
n, m = LI()
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    graph[a - 1] += [b - 1]


min_cycle = 0
for vst in range(n):
    cycle = find_cycle(graph, vst)
    if cycle and len(cycle) < ret_len:
        min_cycle = cycle
        ret_len = len(cycle)


if min_cycle:
    print(ret_len)
    for i in min_cycle:
        print(i + 1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    exit()
while True:
    circle = [False]*N
    circle[v0] = True
    l = 1
    pv = prev[v0]
    while pv != v0:
        circle[pv] = True
        pv = prev[pv]   
        l+=1
    update = False
    for v in range(l):
        if circle[v]:
            for nv in edges[v]:
                if circle[nv] and prev[nv] != v:
                    prev[nv] = v
                    v0 = v
                    update = True
    if not update:
        break
print(l)
for i in range(N):
    if circle[i]:
        print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>=0:
        break
if v0<0:
    print(-1)
    exit()
print(v0, prev)
while True:
    circle = [False]*N
    circle[v0] = True
    l = 1
    pv = prev[v0]
    while pv != v0:
        circle[pv] = True
        pv = prev[pv]   
        l+=1
    update = False
    for v in range(l):
        if circle[v]:
            for nv in edges[v]:
                if circle[nv] and prev[nv] != v:
                    prev[nv] = v
                    v0 = v
                    update = True
    if not update:
        break
print(l)
for i in range(N):
    if circle[i]:
        print(i+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
edges = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
def BFS(s):
    prev = [-1]*N
    que = deque([s])
    while que:
        v = que.pop()
        for nv in edges[v]:
            if nv == s:
                return (s, prev)
            if prev[nv]<0:
                que.append(nv)
                prev[nv] = v
    return (-1, prev)
for v in range(N):
    v0, prev = BFS(v)
    if v0>0:
        break
if v0<0:
    print(-1)
    exit()

while True:
    circle = [False]*N
    circle[v0] = True
    l = 1
    pv = prev[v0]
    while pv != v0:
        circle[pv] = True
        pv = prev[pv]   
        l+=1
    update = False
    for v in range(l):
        if circle[v]:
            for nv in edges[v]:
                if circle[nv] and prev[nv] != v:
                    prev[nv] = v
                    v0 = v
                    update = True
    if not update:
        break
print(l)
for i in range(N):
    if circle[i]:
        print(i+1)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([])
    nvs = [1]
    path = []
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        if max_i_l < 0:
            1/0
        nloop.append(loop[max_i_l])
        break
    if max_i < 0:
        1/0
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
from collections import deque
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]


def bfs(n):
    Q = deque()
    Q.append(n)
    L = [-1] * N
    BACK = [-1] * N
    L[n] = 0
    while len(Q) != 0:
        cur = Q.pop()
        len_and_idx = (-INF, -1)
        for nxt in to[cur]:
            if nxt != n and BACK[nxt] == -1:
                BACK[nxt] = cur
            if L[nxt] != -1 and L[nxt] < L[cur]:
                len_and_idx = max(len_and_idx, (L[nxt], cur))
            else:
                Q.append(nxt)
                L[nxt] = L[cur] + 1

        if len_and_idx[0] >= 0:
            ret = []
            c = len_and_idx[1]
            for _ in range(L[cur] - len_and_idx[0] + 1):
                ret.append(c)
                c = BACK[c]
            return ret
    return None


N, M = [int(x) for x in input().split()]
to = [set() for _ in range(N)]

for _ in range(M):
    A, B = [int(x) for x in input().split()]
    A -= 1
    B -= 1
    to[A].add(B)


for i in range(N):
    L = bfs(i)

    if L:
        print(len(L))
        L.reverse()
        for l in L:
            print(l+1)
        sys.exit()

print(-1)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([])
    nvs = [1]
    path = []
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        if v2i[u] > v2i[v]:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([])
    nvs = [1]
    path = []
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = max_i_l = -1
    for u in d[v]:
        if v2i[u] == -1:
            continue
        if v2i[v] > v2i[u] and u in pvs:
            f = True
            max_i_l = max(max_i_l, v2i[u])
        else:
            max_i = max(max_i, v2i[u])
    if f:
        nloop.append(loop[max_i_l])
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Wrong Answer

Solution code:
N, M = [int(x) for x in input().strip().split(" ")]

def dfs(v):
    pvs = set([v])
    path = [v]
    def _dfs(v, path):
        for u in d[v]:
            if u in pvs:
                for i, c in enumerate(path):
                    if c == u:
                        break
                return path[i+1:]  + [u]
            if u in vs:
                continue
            pvs.add(u)
            vs.add(u)
            loop = _dfs(u, path + [u])
            pvs.remove(u)
            if loop:
                return loop
        return False
    return _dfs(v, path)

def dfs_w(v):
    # dfs while版 
    pvs = set([])
    nvs = [1]
    path = []
    while True:
        if len(nvs) == 0:
            break
        v = nvs.pop()
        if v < 0:
            pvs.remove(path[-1])
            path.pop()
        else:
            path.append(v)
            pvs.add(v)
            vs.add(v)
            for u in d[v]:
                if u in pvs:
                    for i, c in enumerate(path):
                        if c == u:
                            break
                    return path[i+1:]  + [u]
                if u in vs:
                    continue
                nvs += [-v, u]
    return False

d = [set() for _ in range(N+1)]
for _ in range(M):
    a, b = [int(x) for x in input().strip().split(" ")]
    d[a].add(b)

vs = set()
for i in range(N):
    i += 1
    if i in vs:
        continue
    vs.add(i)
    loop = dfs_w(i)
    if loop:
        break

if not loop:
    print(-1)
    import sys
    sys.exit()

v2i = [-1 for _ in range(N+1)]
for i, v in enumerate(loop):
    v2i[v] = i

nloop, pvs = [], set()
v = loop[0]
f = False
while True:
    nloop.append(v)
    pvs.add(v)
    max_i = -1
    for u in d[v]:
        if u in pvs:
            f = True
            nloop.append(u)
            break
        if v2i[v] > v2i[u]:
            continue
        max_i = max(v2i[u], max_i)
    if f:
        break
    v = loop[max_i]

for i, x in enumerate(nloop):
    if x == nloop[-1]:
        break
nloop = nloop[i+1:]
print(len(nloop))
for v in nloop:
    print(v)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

def dfs(v):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            k = dfs(u)
            if k != -1:
                return k
            vis[u] = 1
        else:
            return u
    return -1

N, M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
for i in range(N):
    vis = [1] * N
    s = dfs(i)
    if s != -1:
        dq = deque()
        p = [-1] * N
        for u in es[s]:
            dq.append(u)
            p[u] = s
        while len(dq) > 0:
            v = dq.popleft()
            if v == s:
                break
            for u in es[v]:
                if p[u] == -1:
                    dq.append(u)
                    p[u] = v
        path = [s+1]
        v = p[s]
        while v != s:
            path.append(v+1)
            v = p[v]
        print(len(path))
        print(*path, sep = '\n')
        exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from queue import Queue

INF = 10 * 9
n = 0
g = []


def bfs(s):
    dist = [INF for _ in range(n)]
    pre = [-1 for _ in range(n)]
    q = Queue()
    dist[s] = 0
    q.put(s)
    while not q.empty():
        f = q.get()
        for i in g[f]:
            if dist[i] != INF:
                continue
            pre[i] = f
            dist[i] = dist[f] + 1
            q.put(i)

    best = INF, -1
    for i in range(n):
        if i == s:
            continue
        for j in g[i]:
            if j == s:
                best = min(best, (dist[i], i))

    if best[0] == INF:
        return [INF for _ in range(n + 1)]
    t = best[1]
    res = []
    while t != -1:
        res.append(t)
        t = pre[t]

    return res


def main():
    global n, g
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)

    ans = [INF for _ in range(n + 1)]
    for i in range(n):
        now = bfs(i)
        if len(now) < len(ans):
            ans = now

    if len(ans) == n + 1:
        print(-1)
        return

    print(len(ans))
    for e in ans:
        print(e + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
0

Submission status: Wrong Answer

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

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

dist = [[-1] * n for _ in range(n)]
for i in range(n):
    queue = deque([(i, 0)])
    while queue:
        v, c = queue.popleft()
        for v_next in graph[v]:
            if dist[i][v_next] == -1 or dist[i][v_next] > c + 1:
                dist[i][v_next] = c + 1
                queue.append((v_next, c+1))

# print(dist)
ans_len = n + 1
for i in range(n):
    if dist[i][i] != -1:
        ans_len = min(ans_len, dist[i][i])
if ans_len == n + 1:
    print(-1)
else:
    ans = []
    for i in range(n):
        if dist[i][i] == ans_len:
            ans.append(i+1)

    print(ans_len)
    print(*ans, sep='\n')

Submission status: Wrong Answer

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

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

dist = [[-1] * n for _ in range(n)]
for i in range(n):
    queue = deque([(i, 0)])
    while queue:
        v, c = queue.popleft()
        for v_next in graph[v]:
            if dist[i][v_next] == -1:
                dist[i][v_next] = c + 1
                queue.append((v_next, c+1))

ans_len = n + 1
for i in range(n):
    if dist[i][i] != -1:
        ans_len = min(ans_len, dist[i][i])
if ans_len == n+1:
    print(-1)
else:
    ans = []
    for i in range(n):
        if dist[i][i] == ans_len:
            ans.append(i+1)

    print(ans_len)
    print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit = 10 ** 9
N, M = map(int, input().split())
V = {i: [] for i in range(1,N+1)}
for _ in range(M):
    a, b = map(int, input().split())
    V[a].append(b)
INF = float('inf')

def get_cycle(s):
    H = deque()
    seen = {i: False for i in range(1,N+1)}
    finished = {i: False for i in range(1,N+1)}
    last = [0]
    def dfs(u):
        H.append(u)
        seen[u] = True
        for v in V[u]:
            if finished[v]:
                continue
            if seen[v] and not finished[v]:
                last[0] = v
                return
            dfs(v)
            if last[0]:
                return
        H.pop()
        finished[u] = True
    
    dfs(s)
    cycle = []
    while H:
        cycle.append(H.pop())
        if cycle[-1] == last[0]:
            break
        
    return cycle[::-1]

ans = get_cycle(1)

has_smaller_cycle = True
while has_smaller_cycle:
    has_smaller_cycle = False
    for i in range(len(ans)):
        for v in V[ans[i]]:
            if v != ans[(i+1)%len(ans)]:
                if v in ans:
                    short_cut = (i, ans.index(v))
                    has_smaller_cycle = True
                    break
        if has_smaller_cycle:
            break
    if has_smaller_cycle:
        a, b = short_cut
        if a < b:
            ans = ans[:a+1] + ans[b:]
        else:
            ans = ans[b:a+1]

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

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()



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


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

for start in range(N):
	judge = 0
	que = deque()
	que.append(start)
	parent = [-1]*N
	deep = [-1]*N
	deep[start] = 1
	while len(que) > 0:
		node = que.popleft()
		deep_next = -1
		last_list = []
		for node_next in graph[node]:
			#print((start, node, node_next))
			if deep[node_next] >= 1:
				last_list.append(node_next)
			if deep[node_next] == 1:
				deep_next = 1
			if deep[node_next] == -1:
				parent[node_next] = node
				deep[node_next] = deep[node] + 1
				que.append(node_next)
		if deep_next == 1:
			last = node
			judge = 1
			break
	if judge == 1:
		break


if judge == 0:
	print(-1)
	exit()

ans = [last]
#print(last_list, last, deep)
while True:
	x = parent[ans[-1]]
	if x == -1:
		break
	elif x in last_list:
		ans.append(x)
		break
	else:
		ans.append(x)
print(len(ans))
for i in range(len(ans)):
	print(ans[i] + 1)