#include <stdio.h>

int main() {
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);

    int n, m, x, y;

    scanf("%d %d", &n, &m);

    int a[n+1][n+1], adiac[n+1][n+1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = adiac[i][j] = 0;
        }
        adiac[i][0] = 1;
    }

    for (int i = 0; i < m; i++) {
        scanf("%d %d", &x, &y);

        if (a[x][y] == 0) {
            a[x][y] = a[y][x] = 1;

            adiac[x][adiac[x][0]] = y;
            adiac[x][0]++;

            adiac[y][adiac[y][0]] = x;
            adiac[y][0]++;
        }
    }

    int grad[n+1], gradMax = 0;

    for (int i = 1; i <= n; i++) {
        grad[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        adiac[i][0]--;

        grad[i] = adiac[i][0];

        if (grad[i] > gradMax) {
            gradMax = grad[i];
        }
    }

    //a
    for (int i = 1; i <= n; i++) {
        printf("(%d: %d) ", i, grad[i]);
    }

    printf("\n");

    //b
    for (int i = 1; i <= n; i++) {
        if (grad[i] == gradMax) {
            printf ("%d ", i);
        }
    }

    //c
    for (int i = 1; i <= n; i++) {
        if (grad[i] == 0) {
            printf("%d ", i);
        }
    }

    printf("\n");

}