Cycle Detection

Time limit1sMemory limit128 MB

Summary

Given a graph on at most 20 vertices, for each edge that lies on a cycle, count how many distinct simple cycles contain it.

Level: Medium7 of 10
Topics: Graph, Brute force, Bit manipulation, DFS
Solved: No attempts yet

Problem

Consider a network of computers in which each computer is connected to others by cables. Every cable connects exactly two computers, and any two computers are joined by at most one cable.

Given such a network, find every cable that belongs to at least one cycle, and for each such cable determine how many cycles it belongs to.

A cycle is a sequence of cables that starts at some computer $A$ and returns to $A$ . Every computer other than $A$ may appear at most once in the cycle. Two cycles made of the same set of cables are counted as one, regardless of direction or starting computer.

Input

The first line contains a positive integer $N$ ( $N \le 20$ ), the number of computers in the network.

Each of the next $N$ lines describes the connections as an adjacency matrix: every line contains $N$ values separated by single spaces. If the entry in line $L$ and column $C$ is $0$ , there is no direct connection between computers $L$ and $C$ ; otherwise the two computers are directly connected.

Output

On the first line, print a positive integer $M$ , the number of cables that belong to at least one cycle.

On the next line, print $M$ positive integers separated by single spaces: the number of cycles that each such cable belongs to, sorted in increasing order.

If no cable belongs to any cycle, print a single line containing NO CYCLE.

Examples4

Example 1

Input

6
0 1 1 0 0 0
1 0 1 1 0 0
1 1 0 0 0 1
0 1 0 0 1 0
0 0 0 1 0 1
0 0 1 0 1 0

Expected output

7
2 2 2 2 2 2 2

Example 2
Input
```
3
0 1 1
1 0 1
1 1 0
```
Expected output
```
3
1 1 1
```

Example 3

Input

Expected output

4
1 1 1 1

Example 4

Input

Expected output

NO CYCLE