# Python での想定解 by Shobonvip
# https://github.com/not522/ac-library-python/blob/master/atcoder/maxflow.py
from typing import NamedTuple, Optional, List, cast
class MFGraph:
class Edge(NamedTuple):
src: int
dst: int
cap: int
flow: int
class _Edge:
def __init__(self, dst: int, cap: int) -> None:
self.dst = dst
self.cap = cap
self.rev: Optional[MFGraph._Edge] = None
def __init__(self, n: int) -> None:
self._n = n
self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
self._edges: List[MFGraph._Edge] = []
def add_edge(self, src: int, dst: int, cap: int) -> int:
assert 0 <= src < self._n
assert 0 <= dst < self._n
assert 0 <= cap
m = len(self._edges)
e = MFGraph._Edge(dst, cap)
re = MFGraph._Edge(src, 0)
e.rev = re
re.rev = e
self._g[src].append(e)
self._g[dst].append(re)
self._edges.append(e)
return m
def get_edge(self, i: int) -> Edge:
assert 0 <= i < len(self._edges)
e = self._edges[i]
re = cast(MFGraph._Edge, e.rev)
return MFGraph.Edge(
re.dst,
e.dst,
e.cap + re.cap,
re.cap
)
def edges(self) -> List[Edge]:
return [self.get_edge(i) for i in range(len(self._edges))]
def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
assert 0 <= i < len(self._edges)
assert 0 <= new_flow <= new_cap
e = self._edges[i]
e.cap = new_cap - new_flow
assert e.rev is not None
e.rev.cap = new_flow
def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
assert 0 <= s < self._n
assert 0 <= t < self._n
assert s != t
if flow_limit is None:
flow_limit = cast(int, sum(e.cap for e in self._g[s]))
current_edge = [0] * self._n
level = [0] * self._n
def fill(arr: List[int], value: int) -> None:
for i in range(len(arr)):
arr[i] = value
def bfs() -> bool:
fill(level, self._n)
queue = []
q_front = 0
queue.append(s)
level[s] = 0
while q_front < len(queue):
v = queue[q_front]
q_front += 1
next_level = level[v] + 1
for e in self._g[v]:
if e.cap == 0 or level[e.dst] <= next_level:
continue
level[e.dst] = next_level
if e.dst == t:
return True
queue.append(e.dst)
return False
def dfs(lim: int) -> int:
stack = []
edge_stack: List[MFGraph._Edge] = []
stack.append(t)
while stack:
v = stack[-1]
if v == s:
flow = min(lim, min(e.cap for e in edge_stack))
for e in edge_stack:
e.cap -= flow
assert e.rev is not None
e.rev.cap += flow
return flow
next_level = level[v] - 1
while current_edge[v] < len(self._g[v]):
e = self._g[v][current_edge[v]]
re = cast(MFGraph._Edge, e.rev)
if level[e.dst] != next_level or re.cap == 0:
current_edge[v] += 1
continue
stack.append(e.dst)
edge_stack.append(re)
break
else:
stack.pop()
if edge_stack:
edge_stack.pop()
level[v] = self._n
return 0
flow = 0
while flow < flow_limit:
if not bfs():
break
fill(current_edge, 0)
while flow < flow_limit:
f = dfs(flow_limit - flow)
flow += f
if f == 0:
break
return flow
def min_cut(self, s: int) -> List[bool]:
visited = [False] * self._n
stack = [s]
visited[s] = True
while stack:
v = stack.pop()
for e in self._g[v]:
if e.cap > 0 and not visited[e.dst]:
visited[e.dst] = True
stack.append(e.dst)
return visited
# ここまでac-library-python
class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
class SCCgraph:
#Required ... UnionFind
def __init__(self, n):
self.n = n
self.ikeru = [[] for i in range(n)]
self.ikeruinv = [[] for i in range(n)]
self.union = UnionFind(n)
self.edges = []
self.u = []
self.newmap = dict()
def add_edge(self, a, b):
self.ikeru[a].append(b)
self.ikeruinv[b].append(a)
self.edges.append((a,b))
def scc(self):
tansaku = [0] * self.n
dat = [-1] * self.n
dfs_index = 0
for start in range(self.n):
if tansaku[start] == 0:
mada = [~start, start]
while mada:
i = mada.pop()
if i >= 0:
if tansaku[i] == 1:
continue
tansaku[i] = 1
for j in self.ikeru[i]:
if tansaku[j] == 0:
mada.append(~j)
mada.append(j)
else:
if dat[~i] == -1:
dat[~i] = dfs_index
dfs_index += 1
self.u = [(i, dat[i]) for i in range(self.n)]
self.u.sort(key=lambda x:-x[1])
tansakuinv = [0] * self.n
for start, d in self.u:
if tansakuinv[start] == 0:
mada = [start]
tansakuinv[start] = 1
while mada:
i = mada.pop()
for j in self.ikeruinv[i]:
if tansakuinv[j] == 0:
tansakuinv[j] = 1
mada.append(j)
self.union.union(i, j)
def new_graph(self):
if len(self.u) == 0:
self.scc()
new_n = 0
new_repre = []
for start, d in self.u:
if self.union.parents[start] < 0:
new_repre.append(start)
self.newmap[start] = new_n
new_n += 1
new_ikeru = [[] for i in range(new_n)]
added_set = set()
for a, b in self.edges:
x = self.newmap[self.union.find(a)]
y = self.newmap[self.union.find(b)]
if x != y and (x,y) not in added_set:
added_set.add((x,y))
new_ikeru[x].append(y)
return new_n, new_ikeru
N, M = map(int,input().split())
scc = SCCgraph(N)
EdgeFrom = [0] * M
EdgeTo = [0] * M
for i in range(M):
x, y = map(int,input().split())
scc.add_edge(x-1, y-1)
EdgeFrom[i] = x-1
EdgeTo[i] = y-1
SN, NewEdge = scc.new_graph()
mf = MFGraph(2*SN + 2)
for i in range(SN):
mf.add_edge(2*SN, i+SN, 1)
mf.add_edge(i, 2*SN+1, 1)
mf.add_edge(i, i+SN, 10**9)
for j in NewEdge[i]:
mf.add_edge(i+SN, j, 10**9)
mf.flow(2*SN, 2*SN+1)
ins = [0] * SN
outs = [0] * SN
edge_flows = [[] for i in range(SN)]
for i in mf.edges():
if i.src == 2*SN:
if i.flow > 0:
ins[i.dst - SN] = 1
elif i.dst == 2*SN + 1:
if i.flow > 0:
outs[i.src] = 1
elif i.src >= SN:
edge_flows[i.src - SN].append((i.dst, i.flow))
ansc = [0] * SN
tmp = [[] for i in range(SN)]
cnt = 1
for i in range(SN):
if not outs[i]:
tmp[i].append(cnt)
cnt += 1
ansc[i] = tmp[i][0]
if not ins[i]:
tmp[i].pop()
for j, times in edge_flows[i]:
for k in range(times):
tmp[j].append(tmp[i].pop())
ans = [0] * N
for i in range(N):
ans[i] = ansc[scc.newmap[scc.union.find(i)]]
print(*ans)