Problem:


最悪の記者  

問題

あなたは JOI 新聞社の記者であり，スポーツ記事を担当している．

昨日までに，クロアチアでは，n 個のサッカーチームによる総当りのリーグ戦が行われた．大会実行委員会は，試合結果と規定に基づき各チームに 1 位から n 位までの順位をつけたようである．あなたには，一部の試合の勝敗とともに，次の情報が伝えられた．

情報 1 引き分けの試合はなかった．

情報 2 全てのチームに異なる順位がついた．

情報 3 全ての 1 ≤ a 
例1 (情報に適合する順位表が 1 つしかない場合)

チーム数が4で，各チームに1から4までの番号が付けられており，勝敗が次の表で与えられていたとする．

i 行 j 列が○のときは，番号 i のチームと番号 j のチームの試合において，番号 i のチームが勝利したことを意味する．また，×のときは，番号 j のチームが勝利したことを意味する．? は勝敗が与えられていないことを意味する．このとき，伝えられた情報に適合する順位表は次の 1 つしかない

 1 位 番号 3 のチーム 

 2 位 番号 4 のチーム 

 3 位 番号 1 のチーム 

 4 位 番号 2 のチーム 

例2 (情報に適合する順位表が複数存在する場合)

チーム数が3で，各チームに1から3までの番号が付けられており，勝敗が次の表で与えられていたとする．

このとき，伝えられた情報に適合する順位表は，次の 2 つである．

1 位 番号 2 のチーム

2 位 番号 1 のチーム

3 位 番号 3 のチーム

1 位 番号 2 のチーム

2 位 番号 3 のチーム

3 位 番号 1 のチーム

入力

入力は以下の形式で与えられる．

 1 行目には，サッカーチームの個数 n が書かれている．各チームには，1 から n までの番号が付けられている．

2 行目には，与えられた試合の勝敗の個数 m が書かれている．

3 行目から m + 2 行目は試合の勝敗を表す．各行は空白で区切られた 2 つの整数 i, j を含み，番号 i のチームが番号 j のチームに勝利したことを表す．

n, m は 1 ≤ n ≤ 5000,  1 ≤  m ≤ 100000 をみたす．

採点の際に用いるテストデータのうち，30% は 1 ≤ n ≤ 7,  1 ≤ m ≤ 15 をみたす．また，60% は 1 ≤ n ≤ 100, 1 ≤ m ≤ 2000 をみたす．

出力

出力は n + 1 行からなる．

1 行目から n 行目までの n 行には，伝えられた情報に適合する順位表を出力せよ．

i 行目 (1 ≤ i ≤ n) に i 位のチームの番号を出力せよ．

n + 1 行目には，出力した順位表以外に，伝えられた情報に適合する順位表が存在するかどうかを表す整数を出力せよ．もし存在しなければ 0 を，存在する場合は 1 を出力せよ．

入出力例

例 1 に対応する入出力は以下の通りである．

入力例 1

4
5
1 2
3 1
3 2
3 4
4 1

出力例 1

3
4
1
2
0

例 2 に対応する入出力は以下の通りである．

入力例 2

3
2
2 1
2 3

この入力データに対して，次の 2 通りの出力データが考えられる．どちらを出力してもよい．

出力例 2

2
1
3
1

2
3
1
1

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4
5
1 2
3 1
3 2
3 4
4 1


Sample output:
3
4
1
2
0

Submission status: Wrong Answer

Solution code:
from collections import deque

def Topologicalsort(v):
    start=deque()
    for i in xrange(v):
        if indeg[i]==0 :
            start.append(i)
    if len(start)>1:
        flag=True
    else:
        flag=False

    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        tmp=[]
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                tmp.append(j)
                start.append(j)
                if len(tmp)>=1:
                    flag=True
                else:
                    flag=False
    return ans,flag

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,flag=Topologicalsort(n)
    return ans,flag

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

ans,flag=solve(n,m)

if flag:
    for  i in xrange(len(ans)):
        print(ans[i]+1)
    print(1)
else:
    for i in xrange(n):
        print(ans[i]+1)
    print(0)

Submission status: Wrong Answer

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

used = [False for i in range(n)]
rank = [0 for i in range(n)]

ind = 1

def search(x):
  global ind
  global flag
  pl = pare_lst[x]
  cl = child_lst[x]
  for p in pl:
    search(p)
  if not used[x]:
    rank[x] = ind
    ind += 1
    used[x] = True

def height(x, h):
  if not pare_lst[x]:
    return h
  return max([height(p, h + 1) for p in pare_lst[x]])

flag = 1
for i in range(n):
  search(i)
  if height(i, 1) == n:
    flag = 0

for r in rank:
  print(r)
print(flag)

Submission status: Accepted

Solution code:
n=int(raw_input())
m=int(raw_input())
countlose=[0 for i in range(n+1)]
llist=[[] for i in range(n+1)]
wlist=[[] for i in range(n+1)]
for i in range(m):
    [w,l]=[int(x) for x in raw_input().split()]
    countlose[l]+=1
    wlist[w].append(l)
#for i in range(1,n+1):
#    llist[countlose[i]].append(i)
rank=[]
notyet=range(1,n+1)
only=0
while len(notyet)>0:
    #print countlose
    newtop=[x for x in notyet if countlose[x]==0]
    for x in newtop:
        notyet.remove(x)
    if len(newtop)>1:
    #    print newtop
        only=1
    rank+=newtop
    for j in newtop:
        for k in wlist[j]:
            countlose[k]-=1
for r in rank:
    print r
print only

Submission status: Accepted

Solution code:
from collections import deque

def Topologicalsort(v):
    start=deque()
    for i in xrange(v):
        if indeg[i]==0 :
            start.append(i)
    if len(start)>1:
        flag=True
    else:
        flag=False

    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        tmp=[]
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                tmp.append(j)
                start.append(j)
                if len(tmp)>1:
                    flag=True
    return ans,flag

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,flag=Topologicalsort(n)
    return ans,flag

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

ans,flag=solve(n,m)

if flag:
    for  i in xrange(len(ans)):
        print(ans[i]+1)
    print(1)
else:
    for i in xrange(n):
        print(ans[i]+1)
    print(0)

Submission status: Accepted

Solution code:
from collections import deque

def Topologicalsort(v):
    start=deque()
    for i in xrange(v):
        if indeg[i]==0 :
            start.append(i)
    if len(start)>1:
        flag=True
    else:
        flag=False
    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        tmp=[]
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                tmp.append(j)
                start.append(j)
                if len(tmp)>1:
                    flag=True
    return ans,flag

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,flag=Topologicalsort(n)
    return ans,flag

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

ans,flag=solve(n,m)

if flag:
    for i in xrange(n):
        print(ans[i]+1)
    print(1)
else:
    for i in xrange(n):
        print(ans[i]+1)
    print(0)

Submission status: Accepted

Solution code:
from collections import deque

def Topologicalsort(v):
    start=deque()
    for i in xrange(v):
        if indeg[i]==0 :
            start.append(i)
    if len(start)>1:
        flag=True
    else:
        flag=False
    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        cnt=0
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                cnt+=1
                start.append(j)
                if cnt>1:
                    flag=True
    return ans,flag

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,flag=Topologicalsort(n)
    return ans,flag

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

ans,flag=solve(n,m)

if flag:
    for i in xrange(n):
        print(ans[i]+1)
    print(1)
else:
    for i in xrange(n):
        print(ans[i]+1)
    print(0)

Submission status: Accepted

Solution code:
from collections import deque

def Topologicalsort(v):
    start=deque()
    for i in xrange(v):
        if indeg[i]==0 :
            start.append(i)
    if len(start)>1:
        flag=True
    else:
        flag=False
    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        cnt=0
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                cnt+=1
                start.append(j)
                if cnt>1:
                    flag=True
    return ans,flag

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,flag=Topologicalsort(n)
    if flag:
        for i in xrange(n):
            print(ans[i]+1)
        print(1)
    else:
        for i in xrange(n):
            print(ans[i]+1)
        print(0)

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

solve(n,m)

Submission status: Accepted

Solution code:
from collections import deque

def TopoSort_cnt(n,cnt):
    start=deque()
    for i in xrange(n):
        if indeg[i]==0 :
            start.append(i)
    cnt+=len(start)
    while len(start)>0:
        i=start.popleft()
        ans.append(i)
        tmp=0
        for j in g[i]:
            indeg[j]-=1
            if indeg[j]==0:
                start.append(j)
                tmp+=1
        cnt=max(cnt,cnt*tmp)
    return ans,cnt

def solve(n,m):
    for i in xrange(m):
        wt,lt=map(int,raw_input().split())
        wt-=1;lt-=1
        g[wt].append(lt)
        indeg[lt]+=1
    ans,cnt=TopoSort_cnt(n,0)
    if cnt>1:
        for i in xrange(n):
            print(ans[i]+1)
        print(1)
    else:
        for i in xrange(n):
            print(ans[i]+1)
        print(0)

n=int(raw_input())
m=int(raw_input())
indeg=[0]*n
g=[[] for _ in xrange(n)]
ans=[]

solve(n,m)

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
in_linkset = [set() for _ in range(n)]
out_linkset = [set() for _ in range(n)]
for _ in range(m):
    s, t = (x - 1 for x in map(int, input().split()))
    in_linkset[t].add(s)
    out_linkset[s].add(t)

result = []
roots = {s for s, links in enumerate(in_linkset) if not links}
unique = True

while roots:
    if unique and len(roots) > 1:
        unique = False
    root = roots.pop()
    result.append(root)
    for neighbor in out_linkset[root]:
        in_links = in_linkset[neighbor]
        in_links.remove(root)
        if not in_links:
            roots.add(neighbor)

if len(result) < n:
    result.extend(s for s in range(n) if s not in result)

print('\n'.join(str(s + 1) for s in result))
print(int(not unique))

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())
in_counts = [0] * n
out_set = [set() for _ in range(n)]
for _ in range(m):
    s, t = (x - 1 for x in map(int, input().split()))
    in_counts[t] += 1
    out_set[s].add(t)

roots = {s for s, link_count in enumerate(in_counts) if not link_count}
unique = True

while roots:
    if unique and len(roots) > 1:
        unique = False
    r = roots.pop()
    print(r + 1)
    for nxt in out_set[r]:
        in_counts[nxt] -= 1
        if not in_counts[nxt]:
            roots.add(nxt)

print(int(not unique))

Submission status: Accepted

Solution code:
def output(i):
    global outputlist
    global winnerlist
    global reported
    if outputlist[i]:
        return
    else:
        outputlist[i] = 1

    for each in winnerlist[i]:
        output(each)
    print(i+1)
    reported.append(i)


n = int(input())
m = int(input())

winnerlist = [[] for i in range(n+1)]
outputlist = [0]*n
reported = []

for i in range(m):
    winner, loser = map(int, input().split())
    winner -= 1
    loser -= 1
    winnerlist[loser].append(winner)

for i in range(n):
    output(i)

isnotunique = 0

for i in range(n-1):
    if not reported[i] in winnerlist[reported[i+1]]:
        isnotunique = 1
        break

print(isnotunique)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519

"""
import sys
from sys import stdin
from collections import deque
input = stdin.readline


def bfs(s):
    global Colors
    global Output
    global In_degrees
    global Is_unique

    q = deque()
    q.append(s)
    Colors[s] = GRAY

    while q:
        u = q.popleft()
        Output.append(u)

        pending = []
        for e in Out_edges[u]:
            In_degrees[e] -= 1
            if In_degrees[e] == 0 and Colors[e] == WHITE:
                Colors[e] = GRAY
                pending.append(e)
        if len(pending) > 1:
            Is_unique = False
        for e in pending:
            q.append(e)


def topologial_sort(n):
    global Colors
    global In_degrees
    global Is_unique

    for u in range(1, n+1):
        if In_degrees[u] == 0 and Colors[u] == WHITE:
            if In_degrees.count(0) > 1:
                Is_unique = False
            bfs(u)


BLACK, GRAY, WHITE = 0, 1, 2
Colors = []
Output = []
In_degrees = []
Out_edges = []
Is_unique = True

def main(args):
    global Out_edges
    global Colors
    global In_degrees
    global Is_unique

    n = int(input())            #  ???????????°
    m = int(input())            #  ???????????±?????°
    Out_edges = [[] for _ in range(n+1)]
    In_degrees = [0] * (n + 1)
    In_degrees[0] = -1
    Colors = [WHITE] * (n + 1)

    scores = [[int(x) for x in input().split()] for _ in range(m)]

    for w, l in scores:
        In_degrees[l] += 1
        Out_edges[w].append(l)

    topologial_sort(n)

    for d in Output:
        print(d)
    if Is_unique:
        print(0)
    else:
        print(1)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

n = int(file_input.readline())
m = int(file_input.readline())

adj_list = [[] for i in range(n + 1)]

indeg = [0] * (n + 1)

for line in file_input:
    i, j = map(int, line.split())
    adj_list[i].append(j)
    indeg[j] += 1

unvisited = [True] * (n + 1)

from collections import deque
q = deque()

ans = []

def bfs(s):
    q.append(s)
    unvisited[s] = False
    while q:
        u = q.popleft()
        ans.append(u)
        for v in adj_list[u]:
            indeg[v] -= 1
            if indeg[v] == 0 and unvisited[v]:
                unvisited[v] = False
                q.append(v)

# Topological Sort
for s in range(1, n + 1):
    if indeg[s] == 0 and unvisited[s]:
        bfs(s)

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

# Check whether there is a Hamilton path
for s, t in zip(ans, ans[1:]):
    if t not in adj_list[s]:
        print(1)
        break
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.insert(0,x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.append(x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)
L.reverse()

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def main():
  V, E = int(input()), int(input())
  L = []
  app = L.append
  visited = [0 for i in range(V)]
  edges = [[] for i in range(V)]
  
  def visit(x):
    if not visited[x]:
      visited[x] = 1
      for e in edges[x]:
        visit(e)
      app(x)
  
  for i in range(E):
    s, t = map(int,input().split())
    edges[s - 1].append(t - 1)
  
  for i in range(V):
    if not visited[i]:
      visit(i)
  L.reverse()
  
  flag = 0
  for i in range(V):
    print(L[i] + 1)
    if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
      flag = 1
  print(flag)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def main():
  V, E = int(input()), int(input())
  L = []
  app = L.append
  visited = [0 for i in range(V)]
  edges = [[] for i in range(V)]
  
  def visit(x):
    if not visited[x]:
      visited[x] = 1
      for e in edges[x]:
        visit(e)
      app(x)
  
  for i in range(E):
    s, t = map(int,input().split())
    edges[s - 1].append(t - 1)
  
  for i in range(V):
    if not visited[i]:
      visit(i)
  L.reverse()
  
  flag = 0
  temp = L[0]
  print(temp + 1)
  for i in range(V - 1):
    v = L[i + 1]
    print(v + 1)
    if not flag and i < V - 1 and (v not in edges[temp]):
      flag = 1
    temp = v
  print(flag)
main()

Submission status: Accepted

Solution code:
# AOJ 0519: Worst Reporter
# Python3 2018.6.20 bal4u

# トポロジーソート V:総ノード数, to[][]:隣接リスト
def topological_sort(V, to):
	cnt = [0]*V
	for i in range(V):
		for j in to[i]: cnt[j] += 1
	Q = []
	for i in range(V):
	   if cnt[i] == 0: Q.append(i)
	f = 0
	while len(Q) > 0:
		f |= len(Q) > 1
		i = Q[0]
		del Q[0]
		print(i+1)  # ノードの表示
		for k in to[i]:
			cnt[k] -= 1
			if cnt[k] == 0:	Q.append(k)
	return f	

n = int(input())
to = [[] for i in range(n)]
m = int(input())
for i in range(m):
	a, b = list(map(int, input().split()))
	to[a-1].append(b-1)
print(1 if topological_sort(n, to) else 0)

Submission status: Accepted

Solution code:
def main():
    #import sys
    #input=sys.stdin.readline
    n=int(input())
    m=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*m]
    g=[[] for _ in [0]*n]
    dp=[0]*n
    [g[a-1].append(b-1) for a,b in ab]
    for i,l in enumerate(g):
        for j in l:
            dp[j]+=1
    l=[i for i,j in enumerate(dp) if j==0]
    ans=[i for i,j in enumerate(dp) if j==0]
    while l:
        i=l.pop()
        for j in g[i]:
            dp[j]-=1
            if dp[j]==0:
                l.append(j)
                ans.append(j)
    for i in ans:
        print(i+1)
    for i in range(n-1):
        if ans[i+1] not in g[ans[i]]:
            print(1)
            break
    else:
        print(0)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
m = int(input())

edge = [[] for i in range(n)] #a→b bはaに勝利
visited = [0 for i in range(n)]
maxpath = [-2 for i in range(n)]
toposo = []

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

def dfs(v):
    global visited , maxpath , toposo
    if visited[v] : return maxpath[v]
    visited[v] = 1
    if not (len(edge[v])):
        maxpath[v] = 0
        toposo.append(v)
        return 0
    else : 
        aa = 0
        for next in edge[v]:
             aa = max(aa, dfs(next))
        maxpath[v] = aa+1
        toposo.append(v)
        return aa+1

ansans = 0

for vv in range(n):
    if not visited[vv] : ansans = max(ansans,dfs(vv))
    
for ans in toposo:
    print(ans+1)


if ansans == n-1 : print("0")
else : print("1")

Submission status: Runtime Error

Solution code:
import sys

file_input = sys.stdin

n = int(file_input.readline())
m = int(file_input.readline())

adj_list = [[] for i in range(n + 1)]

for line in file_input:
    i, j = map(int, line.split())
    adj_list[i].append(j)

unvisited = [True] * (n + 1)

ans = []

def dfs(u):
    unvisited[u] = False
    for v in adj_list[u]:
        if unvisited[v]:
            dfs(v)
    ans.append(u)

for s in range(1, n + 1):
    if unvisited[s]:
        dfs(s)

ans.reverse()

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

# Check whether there is a Hamilton path
for s, t in zip(ans, ans[1:]):
    if t not in adj_list[s]:
        print(1)
        break
else:
    print(0)

Submission status: Runtime Error

Solution code:
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.insert(0,x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(100000)
V, E = int(input()), int(input())
L = []
visited = [0 for i in range(V)]
edges = [[] for i in range(V)]
#flag = 0

def visit(x):
#  if visited[x] == 1:
#    flag = 1
  if not visited[x]:
    visited[x] = 1
    for e in edges[x]:
      visit(e)
    L.insert(0,x)

for i in range(E):
  s, t = map(int,input().split())
  edges[s - 1].append(t - 1)

for i in range(V):
  if not visited[i]:
    visit(i)

flag = 0
for i in range(V):
  print(L[i] + 1)
  if not flag and i < V - 1 and (L[i + 1] not in edges[L[i]]):
    flag = 1
print(flag)

Submission status: Runtime Error

Solution code:
# AOJ 0519: Worst Reporter
# Python3 2018.6.20 bal4u

# トポロジーソート V:総ノード数, to[][]:隣接リスト
def topological_sort(V, to):
	cnt = [0]*V
	for i in range(V):
		for j in to[i]: cnt[j] += 1
	Q = []
	for i in range(V):
	   if cnt[i] == 0: Q.append(i)
	f = 0
	while len(Q) > 0:
		f |= len(Q) > 1
		i = Q[0]
		del Q[0]
		print(i+1)  # ノードの表示
		for k in to[i]:
			cnt[k] -= 1
			if cnt[k] == 0:	Q.append(k)
	return f	

import fileinput
n = int(fileinput.input())
to = [[] for i in range(n)]
m = int(fileinput.input())
for i in range(m):
	a, b = list(map(int, fileinput.input().split()))
	to[a-1].append(b-1)
print(1 if topological_sort(n, to) else 0)