410051: GYM103931 M My University Is Better Than Yours

People rank for things. Yes, ranking is nothing for most of the time, except when you are doing year-end report to your boss.

Under the promotion of the construction of world-class universities, a lot of universities are struggling to improve ranking in every way. Publishing papers, applying for funds, improving diversity... They are too hard and your result may not be fairly judged by institutions like US News and Times! However, some universities are more clever – they publish their own rankings, which makes the ranking indirectly better. For example, using Shanghai Ranking's Academic Ranking of World Universities (ARWU) produced by Shanghai Jiao Tong University, Desprado2 can prove that his school is better than MIT.

https://www.zizhengfang.com/applets/transitivity

Anyway, that is a joke unless you are finding jobs and need to brag about your school. But at the same time, Desprado2 comes out a problem: assume there are $$$n$$$ universities in total, and he has collected $$$m$$$ university rankings. For simplicity, all the universities are denoted by a number from $$$1$$$ to $$$n$$$. Here, Desprado2 defines that university $$$x$$$ is directly better than university $$$y$$$, if and only if there exists a university ranking such that university $$$x$$$ ranks higher than university $$$y$$$. Furthermore, Desprado2 defines that university $$$x$$$ is better than university $$$y$$$, if and only if there exists a sequence $$$\{s_1,\ s_2,\ ...,\ s_k\}$$$ ($$$k\ge 2$$$), such that:

• $$$s_1=x,\ s_k=y$$$
• $$$\forall i\in \{1, 2, \dots, k - 1\}$$$, university $$$s_i$$$ is directly better than university $$$s_{i+1}$$$

For each university, Desprado2 want you to tell him it is better than how many of other universities.

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 5\times 10^5$$$, $$$1\le m\le 5\times 10^5$$$, $$$1\le n\times m\le 10^6$$$), denoting the number of universities considered, and the number of university rankings.

Then follows $$$m$$$ lines. The $$$i$$$-th line contains $$$n$$$ distinct integers $$$s_{i,1},\ s_{i,2},\ ...,\ s_{i,n}$$$ ($$$1\le s_{i,j}\le n$$$), denoting the order of the $$$i$$$-th university ranking (from high to low).

Output one line with $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, separated by spaces. The $$$i$$$-th number $$$a_i$$$ denotes the number of universities that university $$$i$$$ is better than.

4 2
1 2 3 4
1 3 2 4

3 2 2 0 

4 2
1 2 3 4
4 3 2 1

3 3 3 3 

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

0 1 2 3 4