Problem p02902 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
    if len(path)!=2:
        for v in path:
            nvs=[nv for nv in g[v] if nv in path]
            if len(nvs)==1:continue
            end=set(nvs)
            end.add(v)
            for nv in nvs:
                ary={v}
                ary.add(nv)
                nv=g[nv][0]
                while nv not in end:
                    ary.add(nv)
                    nv=[x for x in g[v] if nv in path][0]
                if nv==v:
                    func(ary)
    print(len(path))
    for v in path:
        print(v+1)
    exit()

def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            path={v}
            while seen[v] not in path:
                v=seen[v]
                path.add(v)
            func(path)
        else:
            seen[nv]=v
            dfs(nv,seen)
            seen[nv]=-1
while mi:
    v=mi.pop()
    seen=[-1]*n
    dfs(v,seen)
print(-1)
exit()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
    if len(path)!=2:
        for v in path:
            nvs=[nv for nv in g[v] if nv in path]
            if len(nvs)==1:continue
            end=set(nvs)
            end.add(v)
            for nv in nvs:
                ary={v}
                ary.add(nv)
                nv=g[nv][0]
                while nv not in end:
                    ary.add(nv)
                    nv=g[nv][0]
                if nv==v:
                    func(ary)
    print(len(path))
    for v in path:
        print(v+1)
    exit()


def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            path={v}
            while seen[v] not in path:
                v=seen[v]
                path.add(v)
            func(path)
        else:
            seen[nv]=v
            dfs(nv,seen)
            seen[nv]=-1
while mi:
    v=mi.pop()
    seen=[-1]*n
    dfs(v,seen)
print(-1)
exit()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                    seen[nv][0]=v
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                        seen[nv][0]=v
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:print(hoge)
    cnt+=1

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

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    mi.discard(v)
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
nv=s
#print(seen,nv)
cnt=0
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
    if cnt>n:print(hoge)
    cnt+=1

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