There are N clones of Misaka Mikoto (sisters) forming the Misaka network. Some pairs of sisters are connected so that one of them can pass message to the other one. The sister with serial number N is the source of all messages. All the other sisters get message directly or indirectly from her. There might be more than one path from sister #N to sister #I, but some sisters do appear in all of these paths. These sisters are called important sister of sister #K. What are the important sisters of each sister?


There are multiple test cases. Process to the End of File.
The first line of each test case contains two integers: the number of sisters 1 ≤ N ≤ 50,000 and the number of connections 0 ≤ M ≤ 100,000. The following M lines are M connections 1 ≤ Ai, Bi ≤ N, indicating that Ai can pass message to Bi.


For each test case, output the sum of the serial numbers of important sisters of each sister, separated with single space.

Sample Input:

Sample Output:


题目大意:给定一个有向图 \(G\) ,若从 \(n\) 号节点到 \(v\) 的所有路径都必须经过 \(u\) ,则称 \(u\)\(v\) 的Important Sister,现在问每一个点的Important Sister的编号和(包括该点本身)。

一道支配树(Dominator Tree)的模板题,大家可以看看这篇博客