OpenKattis
Same Day Assignment 7: 21 October 8:00am - 11:59pm

#### Start

2019-10-20 16:00 AKDT

## Same Day Assignment 7: 21 October 8:00am - 11:59pm

#### End

2019-10-21 07:59 AKDT
The end is near!
Session is over.
Not yet started.
Session is starting in -292 days 5:32:10

15:59:59

0:00:00

# Problem AWeak Vertices

Engineers like to use triangles. It probably has something to do with how a triangle can provide a lot of structural strength. We can describe the physical structure of some designs using an undirected graph. We’ll say vertex $i$ is part of a triangle if $i$ has two different neighbors $j$ and $k$ such that $j$ and $k$ are neighbors of each other. For this problem, find weak vertices in graphs – those vertices that is not part of any triangle.

## Input

Input consists of up to $100$ graphs. Each starts with an integer, $1 \le n \le 20$, giving the number of vertices in the graph. Next come $n$ lines with $n$ integers on each line, which describe an $n \times n$ adjacency matrix for the graph. Vertices are numbered from $0$ to $n - 1$. If the adjacency matrix contains a one at row $r$, column $c$ (where $0 \le r, c \le n-1$), it means that there is an edge from vertex $r$ to vertex $c$. Since the graph is undirected, the adjacency matrix is symmetric. The end of input is marked by a value of $-1$ for $n$.

## Output

For each graph, produce a line listing the weak vertices ordered from least to greatest.

Sample Input 1 Sample Output 1
9
0 1 1 1 0 0 0 0 0
1 0 0 0 0 0 1 0 0
1 0 0 1 0 1 0 0 0
1 0 1 0 0 1 1 0 0
0 0 0 0 0 0 1 1 0
0 0 1 1 0 0 0 0 0
0 1 0 1 1 0 0 1 0
0 0 0 0 1 0 1 0 1
0 0 0 0 0 0 0 1 0
1
0
-1

1 8
0