방향 그래프(Directed Graph)는 정점(Vertex)들과 한 정점에서 다른 정점으로 방향이 있는 간선(Edge)들로 이루어진 자료구조입니다.

그래프를 컴퓨터에서 표현하는 또 다른 대표적인 방법은 인접 리스트(Adjacency List)입니다.

인접 리스트는 각 정점마다 해당 정점에서 나가는 간선으로 연결된 정점들을 리스트로 관리하는 방식입니다.

V개의 정점과 E개의 간선 정보가 주어졌을 때, 이 그래프를 인접 리스트 형식으로 출력하는 프로그램을 작성하시오.

각 정점 i에 대해 출력 형식은 다음과 같아야 합니다.

• i :를 출력한 뒤, i번 정점에서 갈 수 있는 정점 번호들을 오름차순으로 정렬하여 공백으로 구분해 출력합니다.
• 만약 특정 정점에서 나가는 간선이 하나도 없다면, 정점 번호와 콜론(:)까지만 출력하고 줄바꿈합니다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 공백을 사이에 두고 주어진다.

둘째 줄부터 E개의 줄에 걸쳐 각 간선의 시작 정점 u와 도착 정점 v가 공백을 사이에 두고 주어진다.

이는 u에서 v로 가는 방향성 간선이 존재함을 의미한다. (동일한 간선이 중복되어 주어지지 않는다.)

출력

첫째 줄부터 V개의 줄에 걸쳐 1번 정점부터 V번 정점까지의 인접 리스트 상태를 형식에 맞춰 출력한다.

제한 사항

• 1 ≤ V ≤ 100,000
• 0 ≤ E ≤ 500,000
• 1 ≤ u, v ≤ V (단, u ≠ v 이며, 자기 자신으로 향하는 간선은 없다.)

예제 입력 1

4 4
1 2
1 3
3 4
4 1

예제 출력 1

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