Santa Claus draws up a road map that will allow you to visit
N cities in the shortest possible time. For simplicity, he numbered all cities with numbers
1,
...,
N. Cities are connected by
M number of roads.
Ith road (1<=i<=M) connects city
Ai and city
Bi. Before building the optimal route, Santa Claus wants to know which cities each city is associated with. Help Santa Claus.
Output
N lines as follows.
- Let
di be the number of cities directly related to city i (1<=i<=N) and these cities will be cities ai,1, ..., ai,di listed in ascending order.
Ith line (1<=i<=N) should contain di+1 integer: di, ai,1,..., ai,di in that order, separated by spaces.
Input
The first line of the input contains two integers separated by one space
N and
M (2 <= N <= 10
5, 1 <= M <= 10
5). M lines follow, each containing 2 numbers
Ai and
Bi (1 <= A
i <B
i <= N, 1 <= i <= M).
If i
≠j then (
Ai,
Bi )
≠(
Aj,
Bj). All numbers are integers.
Imprint
Output
N lines according to the format described in the problem statement.
Examples
| # |
Input |
Output |
| 1 |
6 6
36
1 3
5 6
25
1 2
16 |
3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5
|
| 2 |
5 10
1 2
1 3
14
15
23
24
25
34
3 5
4 5 |
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
|