Friend Recommendation System (Max Common Friends)

Users are numbered 0..n−1, and the input gives undirected friendships. For each user y, among users who are neither y nor a friend of y, choose the one with the most mutual friends; break ties by the smallest number. If there is no candidate, the result is -1.

The original problem's ordering rule and the limit of at most 15 friends per person are explicit; this site adds no duplicate edges and the input/output protocol.

输入格式

The first line contains n m (1≤n≤100000); each of the next m lines is a pair of distinct user numbers. Friendships have no duplicates, are undirected, and each person has at most 15 friends.

输出格式

Output n recommended numbers in order of user number.

样例 1

输入：

3 0

输出：

1 0 0

样例 2

输入：

4 2
0 1
1 2

输出：

2 3 0 0

样例 3

输入：

5 4
0 1
0 2
1 3
2 3

输出：

3 2 1 0 0