Problem: Consider a string with rings on both ends. Rings have positive integers to distinguish them. Rings on both ends of the string have different numbers a and b. Describe this as [a, b]. If there are multiple strings and the number attached to the ring of one string and the other string is the same, these strings can be connected at that ring, and the one made by connecting is called a chain. For example, the strings [1, 3] and [3, 4] form the chain [1, 3, 4]. The string and the chain or the chains are also connected at the ring with the same integer. Suppose you can.

For example, a chain [1, 3, 4] and a string [5, 1] ​​can form [5, 1, 3, 4], and a chain [1, 3, 4] and a chain [2, 3, 5] can form [5, 1, 3, 4]. The chain [1, 3, 4] and the chain [4, 6, 1] form a ring.

There are various shapes like this, but in some of them, rings with the same number follow only once. Multiple connected strings are called chains. For example, chains [1, 3, 4] The centrally crossed shape of the chains [2, 3, 5] also includes the chains [1, 3, 5], [2, 3, 4], and the chains [1, 3, 4]. And chains [4, 6, 1] loops include chains such as [1, 3, 4, 6], [3, 4, 6, 1], [4, 6, 1, 3]. ..

For these chains, the number contained is defined as the length. For a given number of strings, anything that can be connected can form a shape that contains one or more chains. Create a program to find the length of the chain.

The first line of the input data contains the number of strings, the positive integer 1 ≤ n ≤ 100, and each of the following n lines contains two integers a, b separated by blanks 1 ≤ a <b ≤ 100. The two integers in each line represent the integers at both ends of one string.

Input example 1 | Input example 2 | Input example 3
--- | --- | ---
|
7 | 6 | 7
1 3 | 1 2 | 1 3
3 4 | 2 3 | 2 4
1 4 | 3 4 | 3 5
2 7 | 4 5 | 4 6
5 7 | 1 5 | 6 7
6 7 | 2 6 | 2 6
1 7 | | 4 7
Output example 1 | Output example 2 | Output example 3
5 | 6 | 4

input

The input consists of multiple datasets. Input ends when n is 0. The number of datasets does not exceed 10.

output

For each dataset, the maximum chain length is output on one line.





Example

Input

7
1 3
3 4
1 4
2 7
5 7
6 7
1 7
6
1 2
2 3
3 4
4 5
1 5
2 6
7
1 3
2 4
3 5
4 6
6 7
2 6
4 7
0


Output

5
6
4

Solution (in CPP):

Solution:
   #include <bits/stdc++.h>
 
//    #include <boost/multiprecision/cpp_int.hpp>
 #define int long long
 #define inf  1000000007
 #define pa pair<int,int>
 #define ll long long
 #define pal pair<double,double>
 #define ppap pair<pa,int>
  #define PI 3.14159265358979323846
  #define paa pair<int,char>
  #define  mp make_pair
  #define  pb push_back
  #define EPS (1e-8)
                                          
    int dx[8]={0,1,0,-1,1,1,-1,-1};
    int dy[8]={1,0,-1,0,-1,1,1,-1};
                                            using namespace std;
                                   			class pa3{
                                            	public:
                                            	int x;
                                   				int y,z;
                                            	pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
                                            	bool operator < (const pa3 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		 return z<p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                   				bool operator > (const pa3 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		 return z>p.z;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa3 &p) const{
                                            		return x==p.x && y==p.y && z==p.z;
                                            	}
                                            		bool operator != (const pa3 &p) const{
                                            			return !( x==p.x && y==p.y && z==p.z);
                                            	}
                                            
                                            };
                                            
                                            class pa4{
                                            	public:
                                            	int x;
                                            	int y,z,w;
                                            	pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
                                            	bool operator < (const pa4 &p) const{
                                            		if(x!=p.x) return x<p.x;
                                            		if(y!=p.y) return y<p.y;
                                            		if(z!=p.z)return z<p.z;
                                            		return w<p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator > (const pa4 &p) const{
                                            		if(x!=p.x) return x>p.x;
                                            		if(y!=p.y) return y>p.y;
                                            		if(z!=p.z)return z>p.z;
                                            		return w>p.w;
                                            		//return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa4 &p) const{
                                            		return x==p.x && y==p.y && z==p.z &&w==p.w;
                                            	}
                                            		
                                            
                                            };
                                            class pa2{
                                            	public:
                                            	int x,y;
                                            	pa2(int x=0,int y=0):x(x),y(y) {}
                                            	pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
                                            	pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
                                            	bool operator < (const pa2 &p) const{
                                            		return y != p.y ? y<p.y: x<p.x;
                                            	}
                                            	bool operator > (const pa2 &p) const{
                                            		return x != p.x ? x<p.x: y<p.y;
                                            	}
                                            	bool operator == (const pa2 &p) const{
                                            		return abs(x-p.x)==0 && abs(y-p.y)==0;
                                            	}
                                            	bool operator != (const pa2 &p) const{
                                            		return !(abs(x-p.x)==0 && abs(y-p.y)==0);
                                            	}
                                            		
                                            
                                            };
                                            
 
                      
                                string itos( int i ) {
                                ostringstream s ;
                                s << i ;
                                return s.str() ;
                                }
                                 
                                int gcd(int v,int b){
                                	if(v==0) return b;
                                	if(b==0) return v;
                                	if(v>b) return gcd(b,v);
                                	if(v==b) return b;
                                	if(b%v==0) return v;
                                	return gcd(v,b%v);
                                }
                 
                            
                                int mod;
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}
pa operator+(const pa & l,const pa & r) {   
    return {l.first+r.first,l.second+r.second};                                    
}    
pa operator-(const pa & l,const pa & r) {   
    return {l.first-r.first,l.second-r.second};                                    
}  
                                
                int pr[10000100];
                int inv[10000010];
                
                int beki(int wa,int rr,int warukazu){
                	if(rr==0) return 1%warukazu;
                	if(rr==1) return wa%warukazu;
                	wa%=warukazu;
                	if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
                	ll zx=beki(wa,rr/2,warukazu);
                	return (zx*zx)%warukazu;
                }
 
                
    			int comb(int nn,int rr){
    				if(rr<0 || rr>nn || nn<0) return 0;
    				int r=pr[nn]*inv[rr];
    				r%=mod;
    				r*=inv[nn-rr];
    				r%=mod;
    				return r;
    			}
               
                void gya(int ert){
                	pr[0]=1;
                	for(int i=1;i<=ert;i++){
                		pr[i]=(pr[i-1]*i)%mod;
                	}
                		inv[ert]=beki(pr[ert],mod-2,mod);
                	for(int i=ert-1;i>=0;i--){
                		inv[i]=inv[i+1]*(i+1)%mod;
                	}
                }
                
              //   cin.tie(0);
    		//	ios::sync_with_stdio(false);
    			//priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                 //sort(ve.begin(),ve.end(),greater<int>());
 //   mt19937(clock_per_sec);
  //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
      
int ans=0;
bool vis[110]={};
vector<int> G[110];
int cnt=0;

void dfs(int r){
	if(vis[r]) return;
	vis[r]=1;
	cnt++;
	ans=max(ans,cnt);
	
	for(auto v:G[r])if(!vis[v])dfs(v);
	vis[r]=0;
	cnt--;
}

signed main(){
	
	
   cin.tie(0);
	ios::sync_with_stdio(false);

while(1){

	int n;
	cin>>n;
if(n==0)exit(0);
ans=0;
for(int i=0;i<=100;i++)G[i].clear(),vis[i]=0;
	for(int i=0;i<n;i++){
		int y,yy;
		cin>>y>>yy;
		G[y].pb(yy);
		G[yy].pb(y);
	}
	for(int i=1;i<=100;i++)dfs(i);
	cout<<ans<<endl;
	}
return 0;
	

 
 }