Friend Recommendation

For each person, recommend a user who is neither that person nor a direct friend, preferring the most mutual friends and then the smallest ID. A user with 0 mutual friends is still a candidate; return −1 only when there are no non-friends at all. The formal conditions of the original do not require a positive mutual count.

输入格式

The first line contains n m, followed by m lines of undirected edges. Original range of the complete same problem: 1≤n≤100000, 0≤m≤250000, IDs 0..n−1; there are no self-loops or multi-edges, each person has at most 15 friends, and the graph may be disconnected. The 1-based typo in the body of problem 18 is restored to 0-based according to the original constraints and examples.

输出格式

Output n recommended IDs, in order of users 0..n−1.

样例 1

输入：

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

输出：

3 2 1 0 1

样例 2

输入：

3 3
0 1
1 2
2 0

输出：

-1 -1 -1

样例 3

输入：

3 1
0 1

输出：

2 2 0

样例说明

The outputs of the three public examples are, in order: 3 2 1 0 1; -1 -1 -1; 2 2 0. These answers were verified by independent enumeration or direct simulation.