There is k switches linked somehow among themselves. Each switch can be only in two states: "on" and "off". The system works as follows: when someone switches the switch (only one for time), the state change both this switch, and all switches linked to it directly. Lighting will switch only when all switches are able "on".
Task. What least number of steps necessary for turning on lighting?
Notes. Initially all switches are in position "off".
Stream. The input stream sets number of switches k and a symmetric matrix of links in the size k where on an intersection i th string and j th column there is 1 if i th switch is linked with j th, or 0 if it is not linked. The output stream should specify the minimum number of steps necessary for inclusion of all switches, or - 1 if such state is impossible.
1 0 1
0 1 0
1 0 1