그래프는 정점과 정점을 잇는 간선으로 정의된 자료 구조이다. 그림으로 그래프를 표현할 때, 정점은 보통 원으로 표현하고 간선은 원을 잇는 선으로 표현한다. 위 그래프에서 정점은 1, 2, 3, 4, 5, 6이고 간선은 ~(1, 2), (1, 5), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6)~이다.

수학적으로는 그래프를 위와 같이 정의할 수 있으나, 실제 프로그램으로 그래프를 저장하는 방법은 여러 가지가 있다. 인접 리스트(Adjacency list)란 그러한 방법 중 하나로, N개의 리스트(자료 구조)를 통해서 그래프를 표현하는 방법이다.

예를 들어 위 그래프의 간선을 모두 저장하고 난 후의 인접 리스트(Adjacency list)는 위와 같다. 위 그래프에서 간선에는 방향이 없기 때문에 adj[u].append(v)를 해줬다면 반대로 adj[v].append(u)도 해줘야 한다.

그래프가 주어질 때, 이를 인접 리스트(Adjacency list)로 표현해보자.

입력

첫째 줄에 그래프의 정점의 개수와 간선의 개수 ~N, M(1 \le N, M \le 50)~이 주어진다. 그래프의 각 정점에는 1부터 N까지 번호가 매겨져 있다.

둘째 줄부터 M개의 줄에 그래프의 간선이 주어진다. 간선은 서로 다른 두 정점 ~u, v(1 \le u, v \le N)~를 잇는다. 주어지는 그래프는 단순 그래프(Simple graph)이다. 따라서 두 정점을 잇는 간선은 최대 한 개 존재할 수 있으며, 자기 자신을 잇는 간선은 없다.

출력

주어진 그래프를 표현한 인접 리스트(Adjacency list)를 출력한다. 즉, N개의 줄에 i번째 정점의 이웃한 정점 adj[i]를 출력한다. adj[i]는 오름차순으로 정렬해서 출력해야 하며 adj[i]가 비었다면 -1만을 출력한다.

예제 입력 1

6 7
1 5
1 2
2 3
2 5
3 4
4 6
4 5

예제 출력 1

2 5
1 3 5
2 4
3 5 6
1 2 4
4

예제 입력 2

4 2
1 2
2 3

예제 출력 2

2
1 3
2
-1

예제 입력 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

예제 출력 3

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

노트

빈 리스트로 초기화되어 있는 길이가 N인 배열을 선언한 후에 M개의 간선을 입력받으면서 리스트에 원소를 추가합니다.

간선으로 ~(u, v)~가 주어지면 adj[u].append(v)를 해줍니다. 반대도 마찬가지로 추가해 줘야 함에 유의합니다.