题目描述

有 $n$ 个人参加一个游戏，他们的等级用一个数组 $a_1,a_2,\dots,a_n$ 表示，第 $i$ 个人的等级为整数 $a_i$。等级 $1$、$0$、$-1$ 分别表示国王、平民、囚徒。游戏开始时所有人的等级均为 $0$。 游戏有 $m$ 条规则。第 $j$ 条规则由两个整数 $u_j,v_j\left(1\leq u_j<v_j\leq n\right)$ 表示，并按照以下方式使用： $\hspace{23pt}\bullet\,$当第 $u_j$ 个人行动时，若此时 $a_{u_j}=0$ 且 $a_{v_j}=1$，则这条规则可用； $\hspace{23pt}\bullet\,$使用这条规则后，$a_{u_j}$ 变为 $1$，$a_{v_j}$ 变为 $-1$，其他人的等级不变。 每个人仅行动一次，行动顺序依次为第 $n,n-1,\dots,1$ 个人。一个人行动时，可以自由选择是否使用规则。 我们认为每个人都以自己的最终等级最大为目标，且所有人都绝对聪明。你需要分别考虑 $n$ 次相互独立的游戏。在第 $i$ 次游戏开始前，只有第 $i$ 个人可以从 $\{-1,0,1\}$ 中选择自己的初始等级 $a_i$，其余人的初始等级均为 $0$。请你计算游戏结束时第 $i$ 个人的等级最大是多少。官方中文

输入格式

第一行输入两个整数 $n,m\left(2\leq n\leq 10^5;\, 1 \leq m \leq 10^5\right)$，表示参加游戏的人数、规则数。 此后 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i\left(1\leq u_i<v_i\leq n\right)$，表示第 $i$ 条规则。官方中文

输出格式

输出 $n$ 行，第 $i$ 行输出一个属于 $\{-1,0,1\}$ 的整数，表示第 $i$ 次游戏中，游戏结束时第 $i$ 个人等级的最大值。官方中文