Challenge: Who Is Connected to Whom?

Lab Python Beginner 10 points

Build an adjacency list for an undirected graph and print each place's neighbours in increasing order, as <place>: <neighbours> (nothing after the colon if it has none).

Input

Line 1: n m – the number of places (numbered 0 to n − 1) and the number of roads. Then m lines a b: a two-way road between a and b.

Output

n lines, one per place, from 0 to n − 1.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

g = [[] for _ in range(n)]

A two-way road adds b to a's list and a to b's list.

Solution explanation

An adjacency list uses O(V + E) memory – only the roads that exist.

Show solution

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for v in range(n):
    print(f"{v}: " + " ".join(map(str, sorted(g[v]))))

Output

Answer