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

그래프를 컴퓨터에서 표현하는 대표적인 방법 중 하나는 인접 리스트(Adjacency List)이다. 인접 리스트는 각 정점마다 해당 정점에서 나가는 간선으로 연결된 정점들을 리스트로 관리하는 방식이다.

\(V\)개의 정점과 \(E\)개의 간선 정보가 주어졌을 때, 이 그래프를 인접 리스트 형식으로 출력하여라.

각 정점 \(i\)는 다음 형식으로 출력한다.

• i :를 출력한 뒤, \(i\)번 정점에서 갈 수 있는 정점 번호들을 간선이 입력된 순서대로 공백으로 구분하여 출력한다.
• 특정 정점에서 나가는 간선이 하나도 없다면 정점 번호와 콜론(:)까지만 출력하고 줄을 바꾼다.

입력

첫째 줄에 정점의 개수 \(V\)와 간선의 개수 \(E\)가 공백으로 구분되어 주어진다.

다음 \(E\)개의 줄에 각 간선의 시작 정점 \(u\)와 도착 정점 \(v\)가 공백으로 구분되어 주어진다. 이는 \(u\)에서 \(v\)로 가는 방향 간선이 존재함을 의미한다.

출력

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

제한 사항

• \(1 \le V \le 100,000\)
• \(0 \le E \le 500,000\)
• \(1 \le u,v \le V\)
• \(u \ne v\)
• 자기 자신으로 향하는 간선은 주어지지 않는다.
• 동일한 방향 간선이 중복해서 주어지지 않는다.
• 입력으로 주어지는 값은 모두 정수이다.

예제 입력 1

4 4
1 2
1 3
3 4
4 1

예제 출력 1

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

예제 입력 2

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

예제 출력 2

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

1번 정점에서 나가는 간선은 1 4, 1 2, 1 3의 순서로 입력되었으므로 인접 정점도 4 2 3의 순서로 출력한다.