Convert an undirected simple graph from an edge list to adjacency lists.

Input

The first line contains n and m. Each of the next m lines contains an undirected edge u v.

• 1 <= n <= 1000
• 0 <= m <= n(n-1)/2

Output

For every vertex i from 1 to n, print i: followed by its neighbors in increasing order.

Example

Input

5 4
1 2
1 4
2 3
4 5

Output

1: 2 4
2: 1 3
3: 2
4: 1 5
5: 4