Convert a directed graph from an edge list to outgoing adjacency lists.

Input

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

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

Output

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

Example

Input

4 4
1 2
1 3
3 2
4 1

Output

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