A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes *u* and *v* (*u* ≠ *v*) exists either an edge going from *u* to *v*, or an edge from *v* to *u*.

You are given a tournament consisting of *n* vertexes. Your task is to find there a cycle of length three.
The first line contains an integer *n* (1 ≤ *n* ≤ 5000). Next *n* lines contain the adjacency matrix *A* of the graph (without spaces). *A*<sub class="lower-index">*i*, *j*</sub> = 1 if the graph has an edge going from vertex *i* to vertex *j*, otherwise *A*<sub class="lower-index">*i*, *j*</sub> = 0. *A*<sub class="lower-index">*i*, *j*</sub> stands for the *j*-th character in the *i*-th line.

It is guaranteed that the given graph is a tournament, that is, *A*<sub class="lower-index">*i*, *i*</sub> = 0, *A*<sub class="lower-index">*i*, *j*</sub> ≠ *A*<sub class="lower-index">*j*, *i*</sub> (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*).
5
00100
10000
01001
11101
11000
1 3 2 
5
01111
00000
01000
01100
01110
-1
5
01000
00101
10010
11001
10100
1 2 3 
5
00110
10110
00011
00000
11010
1 3 5 
10
0011000010
1011001101
0000101100
0010101010
1100000100
1111101100
1000100000
1001001011
0110111001
1011111000
1 3 5 
10
0111001000
0011111000
0000110110
0010101110
1000011001
1001000010
0010010101
1100110000
1100101100
1111010110
1 3 5 
10
0101111011
0001111111
1100011110
0010011000
0011000110
0000101011
0000100000
1001011011
0001001000
0011101010
1 4 3 
10
0000010011
1001001111
1100001110
1010010011
1111011000
0110000001
1001010100
1001110000
0000111101
0010101100
1 6 2 
10
0000000000
1001100111
1101101111
1000000011
1001000111
1111101111
1101100111
1001000011
1000000001
1000000000
-1
1
0
-1
2
00
10
-1
3
001
100
010
1 3 2 
3
010
001
100
1 2 3 
2
01
00
-1
3
011
000
010
-1
4
0000
1010
1001
1100
2 3 4 
5
01111
00111
00010
00001
00100
3 4 5 
from sys import stdin,stdout,setrecursionlimit
import threading
setrecursionlimit(10**9)
threading.stack_size(10**8)

class DFS_General:
    def __init__(self,edges,n):
        self.n= n
        self.pi = [-1 for _ in range(0,n)]
        self.visit = [False  for _ in range(0,n)]
        self.Ady= edges
        self.d = [-1 for _ in range(0,n)]
        self.low = [-1 for _ in range(0,n)]
        self.compo = [-1 for _ in range(0,n )]
        self.count = 0
        self.time = 0
        self.bridges = []
    def DFS_visit_AP(self, u):
        self.visit[u] = True 
        self.time += 1
        self.d[u] = self.time
        self.low[u] = self.d[u]
        for v in self.Ady[u]:
            if not self.visit[v]:  
                self.pi[v]= u
                self.DFS_visit_AP(v)
                self.low[u]= min(self.low[v], self.low[u])
            elif  self.visit[v] and self.pi[u] != v:
                self.low[u]= min(self.low[u], self.d[v])      
        self.compo[u]= self.count        
        if self.pi[u] != -1 and self.low[u]== self.d[u]:
            self.bridges.append((self.pi[u], u))

    def DFS_AP(self):
        for i in range(0,self.n):
            if  not self.visit[i]: 
                self.count += 1 
                self.DFS_visit_AP(i)

def BFS(s,Ady,n):
    d = [0 for _ in range(0,n)]
    color = [-1 for _ in range(0,n)]
    queue = []
    queue.append(s)
    d[s]= 0
    color[s] = 0
    while queue:
        u = queue.pop(0) 
        for v in Ady[u]:
            if  color[v] == -1:
                color[v]= 0
                d[v] = d[u] + 1
                queue.append(v)       
    return d
def Solution():
    n_m =  stdin.readline().split()
    n = int(n_m[0])
    m = int(n_m[1])
    Ady = [[] for i in range (0,n)]
    for i in range(m):
        stri= stdin.readline().split() 
        item = (int(stri[0])-1,int(stri[1])-1)
        Ady[item[0]].append(item[1])
        Ady[item[1]].append(item[0])
    DFS_ = DFS_General(Ady,n)
    DFS_.DFS_AP()
    
    if len(DFS_.bridges) > 0:
        for i in DFS_.bridges:
            Ady[i[0]].remove(i[1])
            Ady[i[1]].remove(i[0])
        DFS_final = DFS_General(Ady,n)
        DFS_final.DFS_AP()
        Ady = [[] for _ in range(0,DFS_final.count)]
        for i in DFS_.bridges:
            Ady[DFS_final.compo[i[0]]-1].append(DFS_final.compo[i[1]] -1)
            Ady[DFS_final.compo[i[1]] -1].append(DFS_final.compo[i[0]] -1)
        d = BFS(0,Ady,len(Ady))
        i = d.index(max(d))                
        d = BFS(i,Ady,len(Ady))
        ma = max(d)
        stdout.write(str(ma)) 
    else:
       stdout.write(str( 0))
threading.Thread(target=Solution).start()        

