Phuc loves to make friends via facebook and he is very proud of the number of friends on his facebook. One day he wondered if there were many people with similar hobbies like him. He knew that it was impossible to scout people on the wall (due to the huge number) so he learned and obtained the relationship graph of facebook's friends. He wanted to base his relationship graph on a list of IDs, number of friends and ID of each friend by account. Please help him.Note: The account ID is unique and cannot be made. P loves to make friends via facebook and he is very proud of the number of friends on his facebook. One day he wondered if there were many people with similar hobbies like him. He obtained the relationship graph of facebook's friends. Each account, he want to find out the id, the number of friends and the list of friends. Please help him.

Note: The account's idenity is unique.

Input

• The friendship relationship graph that P obtained, the first line is a positive integer ~n, m~ ~(n, m ≤ 10 ^ 5)~ is the number of accounts and the number of relationships.
• In the next ~m~ lines, each line contains the IDs of the two accounts that have befriended each other, separated by a space.
• Account's ID is an integer from ~0~ to ~n-1~.

Output

• List of friends in each account, with each line format including: account ID, the number of friends and friend's IDs
• The list of account should be sorted by Id (ascending)
• The list of friends of each account should be in ascending order

Example Input

5 4
1 2
2 0
1 0
1 3

Example Output

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