#include <stdio.h>

#define MAX 100

int graph[MAX][MAX];
int visited[MAX], disc[MAX], low[MAX], parent[MAX];
int isAP[MAX];
int timeCounter;

/* ---------- DFS FOR ARTICULATION POINT ---------- */
void dfs(int u, int V) {
    int v, children = 0;

    visited[u] = 1;
    disc[u] = low[u] = ++timeCounter;

    for (v = 0; v < V; v++) {
        if (graph[u][v]) {

            if (!visited[v]) {
                children++;
                parent[v] = u;

                dfs(v, V);

                /* update low value */
                if (low[v] < low[u])
                    low[u] = low[v];

                /* Case 1: root with multiple children */
                if (parent[u] == -1 && children > 1)
                    isAP[u] = 1;

                /* Case 2: non-root */
                if (parent[u] != -1 && low[v] >= disc[u])
                    isAP[u] = 1;
            }
            /* Back edge */
            else if (v != parent[u]) {
                if (disc[v] < low[u])
                    low[u] = disc[v];
            }
        }
    }
}

/* ---------- FIND ARTICULATION POINTS ---------- */
void findArticulationPoints(int V) {
    int i;

    for (i = 0; i < V; i++) {
        visited[i] = 0;
        parent[i] = -1;
        isAP[i] = 0;
    }

    timeCounter = 0;

    for (i = 0; i < V; i++) {
        if (!visited[i])
            dfs(i, V);
    }

    printf("\nRouters whose removal disconnects the network:\n");
    for (i = 0; i < V; i++) {
        if (isAP[i])
            printf("Router %d\n", i);
    }
}

/* ---------- MAIN ---------- */
int main() {
    int V, E, i, u, v;

    printf("Enter number of routers: ");
    scanf("%d", &V);

    printf("Enter number of connections: ");
    scanf("%d", &E);

    /* Initialize graph */
    for (i = 0; i < V; i++)
        for (int j = 0; j < V; j++)
            graph[i][j] = 0;

    printf("Enter router connections (u v):\n");
    for (i = 0; i < E; i++) {
        scanf("%d %d", &u, &v);
        graph[u][v] = 1;
        graph[v][u] = 1;
    }

    findArticulationPoints(V);

    return 0;
}