Challenge: Who Is Connected to Whom?

Lab C++ Beginner 10 points

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

Input

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

Output

n lines, from place 0 to n − 1.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

vector<vector<int>> g(n);

A two-way road adds each place to the other's list.

Solution explanation

The adjacency list uses O(V + E) memory.

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int v = 0; v < n; v++) {
        sort(g[v].begin(), g[v].end());
        cout << v << ":";
        for (int w : g[v]) cout << ' ' << w;
        cout << endl;
    }
    return 0;
}

Output

Answer