Given n users numbered 0 to n - 1 and an array friendships where [u, v] represents an undirected friendship, recommend exactly one new friend for every user.

Rules

For each user:

• The recommended user must not already be a direct friend.
• The recommended user must not be the user themselves.
• Choose the user with the maximum number of mutual friends.
• If multiple users tie, choose the user with the lowest ID.
• If no valid candidate has at least 1 mutual friend, return -1.

Return an array recommendations where recommendations[i] is the recommended friend for user i.

Constraints

1 <= n <= 10^5
0 <= friendships.length <= 2 * 10^5
friendships[i].length == 2
0 <= u, v < n
u != v
No duplicate friendships

Example

Input:

n = 5
friendships = [[0,1], [0,2], [1,3], [2,3], [3,4]]

Output:

[3, 2, 1, 0, 1]

Explanation

User 0 → User 3
Mutual friends = {1, 2} → 2 mutual friends

User 1 → User 2
Mutual friends = {0, 3} → 2 mutual friends

User 2 → User 1
Mutual friends = {0, 3} → 2 mutual friends

User 3 → User 0
Mutual friends = {1, 2} → 2 mutual friends

User 4 → User 1
User 1 and User 2 both have 1 mutual friend.
Choose the lower ID → User 1.

Expected result:

[3, 2, 1, 0, 1]