'''
先进行拓扑排序,然后按照拓扑序的逆序进行DP递推,DP
状态定义为某节点能够到达的节点的集合,用bitset方式
进行表示
'''
import sys
from collections import deque
import array
class BitSet(object):
# from low to high "00000001 00000010 00000011", the array is [1, 2, 3]
def __init__(self, capacity):
# "B"类型相当于 C 语言的 unsigned char, 即占用1byte(8位),所以size大小设置为8
self.unit_size = 8
self.unit_count = int((capacity + self.unit_size - 1) / self.unit_size)
self.capacity = capacity
self.arr = array.array("B", [0] * self.unit_count)
def or_oper(self, other):
ans = BitSet(self.capacity)
for i in range(len(self.arr)):
ans.arr[i] = self.arr[i] | other.arr[i]
return ans
def and_oper(self, other):
ans = BitSet(self.capacity)
for i in range(len(self.arr)):
ans.arr[i] = self.arr[i] & other.arr[i]
return ans
def xor_oper(self, other):
ans = BitSet(self.capacity)
for i in range(len(self.arr)):
ans.arr[i] = self.arr[i] ^ other.arr[i]
return ans
def any(self):
# 是否存在置为 1 的位
for a in self.arr:
if a != 0:
return True
return False
def all(self):
# 是否所有位都为 1, 即是否存在置为 0 的位
t = (1 << self.unit_size) - 1
for a in self.arr:
if (a & t) != t:
return False
return True
def none(self):
# 是否所有位都为 0,即是否不存在置为 1 的位
for a in self.arr:
if a != 0:
return False
return True
def count(self):
# 置为 1 的位的个数
cnt = 0
for val in self.arr:
while val:
cnt += 1
val &= (val-1)
return cnt
def size(self):
# 所有位的个数
return self.unit_count * self.unit_size
def get(self, pos):
# 获取第 pos 位的值
index = int(pos / self.unit_size)
offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
return (self.arr[index] >> offset) & 1
def test(self, pos):
# 判断第 pos 位的值是否为 1
if self.get(pos):
return True
return False
def set(self, pos=-1):
# 设置第 pos 位的值为 1,若 pos 为 -1, 则所有位都置为 1
if pos >= 0:
index = int(pos / self.unit_size)
offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
self.arr[index] = (self.arr[index]) | (1 << offset)
else:
t = (1 << self.unit_size) - 1
for i in range(self.unit_count):
self.arr[i] = self.arr[i] | t
def reset(self, pos=-1):
# 设置第 pos 位的值为 0,若 pos 为 -1, 则所有位都置为 0
if pos >= 0:
index = int(pos / self.unit_size)
offset = (self.unit_size - (pos - index * self.unit_size) - 1) % self.unit_size
x = (1 << offset)
self.arr[index] = (self.arr[index]) & (~x)
else:
for i in range(self.unit_count):
self.arr[i] = 0
def flip(self, pos=-1):
# 把第 pos 位的值取反,若 pos 为 -1, 则所有位都取反
if pos >= 0:
if self.get(pos):
self.reset(pos)
else:
self.set(pos)
else:
for i in range(self.unit_count):
self.arr[i] = ~self.arr[i] + (1 << self.unit_size)
def binstr(self):
b = ""
for a in self.arr:
t = bin(a)
b += "0" * (self.unit_size - len(t) + 2) + t + ","
return "[" + b.replace("0b", "").strip(",") + "]"
def show(self):
return self.arr
class TopoSort:
# edges是边列表, (a, b)代表一条边,表示a依赖于b, 返回拓扑排序之后的节点列表, 无法完成拓扑排序返回None
# 节点编号是1, 2, 3, .... node_num
@staticmethod
def sort(edges, node_num):
dep_cnt = [0] * (node_num + 1) # 每一个节点的依赖计数
link = {}
for a, b in edges:
if b not in link:
link[b] = []
link[b].append(a) # link[b]记录哪些点依赖b
dep_cnt[a] += 1
ans = []
valid_node = deque() # 当前入度为0的所有节点
for idx, degree in enumerate(dep_cnt[1:]):
if degree == 0:
valid_node.append(idx+1)
while len(ans) < node_num:
if len(valid_node) == 0:
return None
cur_node = valid_node.popleft()
if cur_node in link:
for next in link[cur_node]:
dep_cnt[next] -= 1
if dep_cnt[next] == 0:
valid_node.append(next)
ans.append(cur_node)
return ans
edges = set()
n, m = map(int, input().split())
link = [[] for _ in range(n+1)]
visit_nodes = [BitSet(n+1) for _ in range(n+1)]
for i in range(m):
s = sys.stdin.readline()
a, b = map(int, s.split())
edges.add((b, a))
link[a].append(b)
# 按照拓扑序的逆序来进行DP递推
sort_list = TopoSort.sort(edges, n)
for node in reversed(sort_list):
visit_nodes[node].set(node)
for next in link[node]:
visit_nodes[node] = visit_nodes[node].or_oper(visit_nodes[next])
for i in range(1, n+1):
print(visit_nodes[i].count())