I have my friends to visit. For some reason, I can only visit some of my friends. So I want see my friends as many as possible. Thus I must choose the longest way. Your goal is to help me developing a program that computes the length of the longest path that can be constructed in a given graph from a given starting point (My residence). You can assume that the graph has no cycles (there is no path from any node to itself), so I will reach my destination in a finite time. In the same line of reasoning, nodes are not considered directly connected to themselves.

Input

The input consists of a number of cases. The first line on each case contains a positive number n (1 < n <= 100) that specifies the number of points in the graph. A value of n = 0 indicates the end of the input. After this, a second number s is provided, indicating the starting point in my journey (1 <= s <= n). Then, you are given a list of pairs of places p and q, one pair per line. The pair "p q" indicates that I can visit q after p. A pair of zeros ("0 0") indicates the end of the case. As mentioned before, you can assume that the graphs provided will not be cyclic.

Output

For each test case you have to find the length of the longest path that begins at the starting place. You also have to print the number of the final place of such longest path. If there are several paths of maximum length, print the final place with smallest number.

Print a new line after each test case.

Sample Input

2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0

Sample Output

Case 1: The longest path from 1 has length 1, finishing at 2.
Case 2: The longest path from 3 has length 4, finishing at 5.
Case 3: The longest path from 5 has length 2, finishing at 1.

提交了10次，AC 3次，超時4次，wa 3次。

很無語。

應該是動態規劃最好，但是我不是很熟，用了搜索。以下是超時的代碼

#include<iostream>
#include<cstdlib>
using namespace std;
int path[101][101];
int mark[101];
int len[101];//
int end[101];
int dfs(int start,int num)//返回從當前點出發的最大長度
{
if(mark[start]==1)return len[start];
mark[start]=1;
end[start]=start;
for(int i=1;i<=num;i++)
{
if(path[start][i])
{
if(len[start]<dfs(i,num)+1)
{
len[start]=len[i]+1;
end[start]=end[i];
}
else
if(len[start]==len[i]+1&&end[start]>end[i])
end[start]=end[i];
}
}
mark[start]=0;//這句堅決不需要 
return len[start];
}
int main()
{
// freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
int j,k,turn=0;
int start,num;
while(cin>>num)
{
turn++;
if(num==0)break;
memset(path,0,sizeof(path));
memset(mark,0,sizeof(mark));
memset(len,0,sizeof(len));
memset(end,0,sizeof(end));
cin>>start;
while(cin>>j>>k)
{
if(j==0)break;
path[j][k]=1;
}
cout<<"Case "<<turn<<": The longest path from "<<start<<" has length "<<dfs(start,num)<<", finishing at "<<end[start]<<"."<<endl<<endl;
}
//system("PAUSE");
return   0;
}
以下是ac的代碼
#include<iostream>
#include<cstdlib>
using namespace std;
int path[102][102];
int mark[102], len[102],end[102];
int dfs(int start,int num)//返回從當前點出發的最大長度
{
if(mark[start]==1)return len[start];
mark[start]=1;
end[start]=start;
len[start]=0;
int i,t;
for( i=1;i<=num;i++)
{
if(path[start][i])
{
t=dfs(i,num)+1;
if(t>len[start])
{
len[start]=t;
end[start]=end[i];
}
else
if(len[start]==t)
{
if(end[start]>end[i])
end[start]=end[i];
}
}
}
return len[start];
}
int main()
{
//freopen("s.txt","r",stdin);
//freopen("key.txt","w",stdout);
int j,k,turn=0;
int start,num;
while(cin>>num,num)
{
turn++;
memset(path,0,sizeof(path));
memset(mark,0,sizeof(mark));
memset(len,0,sizeof(len));
memset(end,0,sizeof(end));
cin>>start;
while(cin>>j>>k,j||k)
{
path[j][k]=1;
}
dfs(start,num);
cout<<"Case "<<turn<<": The longest path from "<<start<<" has length "<<len[start]<<", finishing at "<<end[start]<<"."<<endl<<endl;
}
//system("PAUSE");
return   0;
}
不妨執行一下
5
3
1 2
3 5
3 1
2 4
4 5
0 0
先是len[3]=0;end[3]=3;flag[3]=1;
再執行t=dfs(1)+1,
轉入dfs（1）；len[1]=0;end[1]=1;flag[1]=1;
再執行t=dfs(2)+1;
轉入dfs(2),len[2]=0;end[2]=2;flag[2]=1;
再執行t=dfs(4)+1
轉入dfs(4),len[4]=0;end[4]=4;flag[4]=1;
再轉入t=dfs（5)+1;
轉入dfs(5),len[5]=0;end[5]=5;flag[5]=1;return(len[5]=0);
則t=1;t>len[4];len[4]=1;end[4]=end[5]=5;再看4沒了其他相鄰元素。dfs(4)=return(len[4])=1;
t=dfs(4)+1=2;len[2]=t=2;end[2]=end[4]=5;再看2沒了其他相鄰元素，dfs(2)=return(len(2)=2;
再看t=dfs(2)+1=3;len[1]=t=3;end[1]=en[2]=5;再看1有沒有其他相鄰元素，dfs(1)=return(len(1)=3
再執行t=dfs(1)+1,len[3]=4;end[3]=end[1]=5;再看3有沒有其他相鄰元素，有dfs(5),已經遍歷到了，所以dfs（5）return len【5】。
沒有影響。
假設改為
5
3
5 2
3 5
3 1
2 4
4 1
0 0
執行時會走3->1>這時的1結點len[1]已經求的   3>5>2>4>1len[1]已知了