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:
#input
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())

#output

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

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

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

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

#サイクルを短縮する
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
#結果の出力            
if short:
    del short[-1]
    print(len(short))
    for s in short:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

#サイクルを短縮する
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]
#結果の出力            
if short:
    del short[-1]
    print(len(short))
    for s in short:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

#サイクルを短縮する
if short:
    for i in range(1, len(short)-1):
        for j in C[i]:
            if j in short[(i+1):-2]:
                p = short.index(i)
                q = short.index(j)
                short = short[p:q]

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

Submission status: Wrong Answer

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

#output

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

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

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

shortest = None
for v in visited:
    if len(v) >= 2 and len(v) <= N and v[0] == v[-1]:
        if not shortest or len(v) < len(shortest):
            shortest = v
            
if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

#output

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

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

for i in range(N):
    search_stack[i] = [i]
    visited[i] = []
    while search_stack[i] != []:
        next_position[i] = search_stack[i].pop()
        visited[i].append(next_position[i])
        for node in C[next_position[i]]:
            if node in visited[i]:
                visited[i].append(node)
                search_stack[i] = []
                break
            elif node == i:
                visited[i].append(node)
                search_stack[i] = []
                break
            elif node in search_stack[i]:
                continue
            elif C[node] == []:
                continue
            else:
                search_stack[i].append(node)
 
shortest = None
for v in visited:
    if len(v) >= 2 and len(v) <= N and v[0] == v[-1]:
        if not shortest or len(v) < len(shortest):
            shortest = v

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

for i in range(N):
    search_stack[i] = [i]
    visited[i] = []
    while search_stack[i] != []:
        next_position[i] = search_stack[i].pop()
        visited[i].append(next_position[i])
        for node in C[next_position[i]]:
            if node == i:
                visited[i].append(node)
                search_stack[i] = []
                break
            elif node in visited[i]:
                continue
            elif node in search_stack[i]:
                continue
            elif C[node] == []:
                continue
            else:
                search_stack[i].append(node)
visited
shortest = None
for v in visited:
    if len(v) > 2 and len(v) <= N and v[0] == v[-1]:
        if not shortest or len(v) < len(shortest):
            shortest = v

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

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

if shortest:
    del shortest[-1]
    print(len(shortest))
    for s in shortest:
        print(s+1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
print(2)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
v = [[] for _ in range(N)]
for _ in range(M) :
    A, B = map(int, input().split())
    v[A-1].append(B-1)
    
def find_cycle() :
    visited = [False] * N
    for i in range(N) :
        if visited[i] :
            continue
        visited[i] = True
            
        path = []
        queue = [i]
        while queue :
            cur = queue.pop()
            path.append(cur)
            for nex in v[cur] :
                if nex == i :
                    return path
                if visited[nex] :
                    continue
                queue.append(nex)
                
    return False

def has_cycle(i) :
    queue = [i]
    visited = [False] * N
    visited[i] = True
    while queue :
        cur = queue.pop()
        for nex in v[cur] :
            if nex == i :
                return True
            if not exist[nex] or visited[nex] :
                continue
            queue.append(nex)
            visited[nex] = True
    
    return False

cycle = find_cycle()
if cycle :
    ret = []
    exist = [False] * N
    for i in cycle :
        exist[i] = True
    for i in cycle :
        if has_cycle(i) :
            ret.append(i)
        else :
            exist[i] = False
    
    print(len(ret))
    for i in ret :
        print(i + 1)
        
else :
    print(-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

vis = [0] * 1005


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


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

if len(t) == 0:
    print(-1)
    exit(0)

pre = t[0]
next = [0] * 1005
for i in range(1, len(t)):
    now = t[i]
    next[pre] = now
    pre = now
next[t[-1]] = t[0]
s = set()
for i in t:
    s.add(i)

cnt = 0
now = t[0]
while cnt < len(s):
    cnt += 1
    for i in g[now]:
        if i == next[now]:
            continue
        if i in s:
            cnt = 0
            k = now
            k = next[k]
            while k != i:
                s.remove(k)
                k = next[k]
            next[now] = i
    now = next[now]

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

Submission status: Wrong Answer

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

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

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

vis = [0] * 1005


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


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

Submission status: Wrong Answer

Solution code:
il = input().split(' ')
N = int(il[0])
M = int(il[1])
A = []
B = []
for i in range(M):
    l = input().split(' ')
    A.append(int(l[0]))
    B.append(int(l[1]))

from collections import defaultdict
from collections import deque

dic = defaultdict(list)
for i in range(M):
    dic[A[i]].append(B[i])

def myprint(li):
    print(len(li))
    for i in range(len(li)):
        print(li[i])
            
for key in dic:
    path = []
    deq = deque([])
    path.append(key)
    deq.append((key,path))
    while(len(deq) > 0):
        node, path = deq.popleft()
        if(node not in dic):
            continue
        for e in dic[node]:
            new_path = path + [e]
            if(new_path[0] == e):
                myprint(new_path[:-1])
                exit()
            if(e in path):
                continue
            deq.append((e, new_path))
print("-1")

Submission status: Wrong Answer

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

g1 = [[] for _ in range(1005)]
g2 = [[] for _ in range(1005)]

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

vis = [0] * 1005
s = []


def dfs1(x):
    if vis[x]:
        return
    vis[x] = 1
    for i in g1[x]:
        dfs1(i)
    s.append(x)


scc = [[] for _ in range(1005)]
cnt = 0

mnt = [0] * 1005
cc = [0] * 1005


def dfs2(x):
    vis[x] = 0
    scc[cnt].append(x)
    cc[x] = cnt
    for i in g2[x]:
        if not vis[i]:
            mnt[cnt] = 1
            mnt[cc[i]] = 1
            continue
        dfs2(i)


for i in range(1, 1 + n):
    dfs1(i)

for i in range(n - 1, -1, -1):
    if vis[s[i]]:
        cnt += 1
        dfs2(s[i])

for i in range(1, cnt + 1):
    if len(scc[i]) > 1:
        print(len(scc[i]))
        for j in scc[i]:
            print(j)
        exit(0)
print(-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
g = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
vis = {}
vs = []
def dfs(i):
    if i in vis:
        if vis[i]:
            del vs[:vs.index(i)]
        return vis[i]
    vis[i] = True
    vs.append(i)
    for j in g[i]:
        if dfs(j):
            return True
    vis[i] = False
    vs.pop()
    return False
for i in range(n):
    if dfs(i):
        break
else:
    print(-1)
    exit()
dist = {v: i for i, v in enumerate(vs)}
for i in vs:
    if i not in dist:
        continue
    k = -1
    for j in g[i]:
        if j not in dist:
            continue
        if k == -1:
            k = j
            continue
        dj = (dist[j]-dist[i])%len(vs) 
        dk = (dist[k]-dist[i])%len(vs) 
        if dj > dk:
            del dist[k]
            k = j
print(len(dist))
for i in dist:
    print(i)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [[] for _ in range(M)]
S = [[] for _ in range(M)]
q = [[] for _ in range(N)]
for m in range(M):
  a,b = map(int,input().split())
  A[m] = [a,b]
  S[m] = a
  q[a-1].append(b)

S = set(S)
A = [a for a in A if (a[0] in S) and (a[1] in S)]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N-2):
  for x in X:
    for v in q[x[-1]-1]:
      if v in x:  
          ans.append(x+[v])
          ans[0] = [len(ans[0])-1] + ans[0]
          print(*ans[0][:-1])
          import sys
          sys.exit()
      else:
          #XX.append(x + [v[1]])
          XX[i] = x + [v]
          i += 1
      X = [x for x in XX if x]

print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
A = []
S = [[] for _ in range(M)]
 
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  S[m] = a

S = set(S)
A = [a for a in A if (a[0] in S) and (a[1] in S)]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N-2):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        ans[0] = [len(ans[0])-1] + ans[0]
        print(*ans[0][:-1])
        import sys
        sys.exit()
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
      X = [x for x in XX if x]


print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque
N,M = map(int,input().split())
A = deque()

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  #X[m] = X[m] + [a] + [b]

ans = deque()
X = deque(list(A).copy())
XX = deque()
for _ in range(N-2):
  for n,v in itertools.product(range(len(X)),A):
      if X[n][-1] == v[0]:
        if v[1] in X[n]:
          ans.append(X[n] + [v[1]])
          break
        else:
          XX.append(X[n] + [v[1]])
  if XX == []:berak
  X = XX


if ans == deque([]):
  print(-1)
else:
  ans[0] =  [len(ans[0])-1] + ans[0][:-1]
  print(*ans[0])

Submission status: Wrong Answer

Solution code:
#import itertools
N,M = map(int,input().split())
A = []
X = [[0]]*M

for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  #X[m] = X[m] + [a] + [b]

ans = []
XX = []
X = A.copy()
for _ in range(N-2):
  for m in range(len(X)):
    for v in A:
      if X[m][-1] == v[0]:
        if v[1] in X[m]:
          ans.append(X[m]+[v[1]])
          break
        else:
          XX.append(X[m] + [v[1]])
  if len(XX) == 0:break
  X = XX

if ans == []:
  print(-1)
else:
  ans[0] = [len(ans[0])-1] + ans[0]
  print(*ans[0][:-1])