//Articulation Points
import java.util.*;

public class ArticulationPoints {
    private int numVertices;
    private int[][] adjacencyMatrix;
    private int[] discoveryTime;
    private int[] lowLinkValue;
    private int timeCounter;
    private Set<Integer> articulationPoints;

    public ArticulationPoints(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
        discoveryTime = new int[numVertices];
        lowLinkValue = new int[numVertices];
        timeCounter = 1;
        articulationPoints = new HashSet<>();
    }

    public void readGraph(Scanner scanner) {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                adjacencyMatrix[i][j] = scanner.nextInt();
            }
            discoveryTime[i] = 0;
        }
    }

    public void findArticulationPoints(int currentVertex, int parentVertex) {
        discoveryTime[currentVertex] = timeCounter;
        lowLinkValue[currentVertex] = timeCounter;
        timeCounter++;
        int childrenCount = 0;

        for (int adjacentVertex = 0; adjacentVertex < numVertices; adjacentVertex++) {
            if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && discoveryTime[adjacentVertex] == 0) {
                if (parentVertex == -1) childrenCount++;
                findArticulationPoints(adjacentVertex, currentVertex);

                if (parentVertex != -1 && lowLinkValue[adjacentVertex] >= discoveryTime[currentVertex]) {
                    articulationPoints.add(currentVertex);
                }

                lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], lowLinkValue[adjacentVertex]);
            } else if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && adjacentVertex != parentVertex) {
                lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], discoveryTime[adjacentVertex]);
            }
        }

        if (parentVertex == -1 && childrenCount > 1) {
            articulationPoints.add(currentVertex);
        }
    }

    public void printResults() {
        System.out.println("Articulation points: " + articulationPoints);
        System.out.print("Discovery times: ");
        for (int i = 0; i < numVertices; i++) {
            System.out.print(discoveryTime[i] - 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter number of vertices:");
        int numVertices = scanner.nextInt();
        ArticulationPoints articulation = new ArticulationPoints(numVertices);

        System.out.println("Enter the adjacency matrix:");
        articulation.readGraph(scanner);

        articulation.findArticulationPoints(0, -1);
        articulation.printResults();
    }
}

// Input for Test Case with 4 vertices
/*
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
*/

// Expected Output
/*
Articulation points: [1, 2]
Discovery times: 0 1 2 3
*/