Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить
N городов. Для простоты он пронумеровал все города номерами
1,
...,
N. Города соединены
M количеством дорог.
I-я дорога (1<=i<=M) соединяет город
Ai и город
Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите
N строк следующим образом.
- Пусть
di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города ai,1, ..., ai,di,перечисленных в порядке возрастания.
I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.
Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом
N и
M (2 <= N <= 10
5, 1 <= M <= 10
5). Далее следует M строк, каждая из которых содержит 2 числа
Ai и
Bi (1 <= A
i < B
i <= N, 1 <= i <= M).
Если i
≠j, то (
Ai,
Bi)
≠(
Aj,
Bj). Все числа целые.
Выходные данные
Выведите
N строк по формату, описанному в условии задачи.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6
3 6
1 3
5 6
2 5
1 2
1 6 |
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
1 4
1 5
2 3
2 4
2 5
3 4
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 |