Challenge: Who Are My Friends?

Lab Java Beginner 10 points

Read a friendship network and print every person's friends, sorted, as p: a b c (or p: none).

Input

Line 1: n m – people/places are numbered 1 to n, and there are m links. Then m lines u v: a two-way link between u and v.

Output

n lines, one per person from 1 to n.

Example

Input

Output

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

Sample input available Sample output available

Editor

Java

Hints

Make n + 1 empty lists so person p uses index p.

A friendship goes both ways: add v to u's list and u to v's.

Solution explanation

Building the lists is O(n + m); sorting each list adds a little on top.

Show solution

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<Integer>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            g.get(u).add(v);
            g.get(v).add(u);
        }
        StringBuilder sb = new StringBuilder();
        for (int p = 1; p <= n; p++) {
            ArrayList<Integer> list = g.get(p);
            Collections.sort(list);
            sb.append(p).append(':');
            if (list.isEmpty()) sb.append(" none");
            for (int f : list) sb.append(' ').append(f);
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer