EIU Programming Practices and Exams

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

Output

0 2 1 2

1 3 0 2 3

2 2 0 1

3 1 1

4 0