3701: 【BFS】2023B-最长广播响应

金币值:1 时间限制:2.000 s 内存限制:128 M
正确:39 提交:63 正确率:61.90% 命题人:

题目描述

某通信网络中有N个网络节点,用1到N进行标识。 

网络中的节点互联互通,且节点之间的消息传递有时延,相连节点的时延均为一个时间单位。 

现给定网络节点的连接关系link[i] = {u,v},其中u和v表示网络节点。 

当指定一个节点向其他节点进行广播,所有被广播节点收到消息后都会在原路径上回复一条响应消息,请计算发送节点至少需要等待几个时间单位才能收到所有被广播节点的响应消息。 

注: 

1. N的取值范围为[1,100]; 

2. 连接关系link的长度不超过3000,且1 <= u, v <= N; 

3. 网络中任意节点间均是可达的;

输入格式

第一行输入两个数字,N和M,用空格隔开。N表示连通图一共有N个节点,M表示连通图一共有M条边。 

接下来输入M行,包含两个数字v1和v2,表示v1和v2相连。

 最后一行输入一个数字,表示指定节点。

输出格式

一个数字,表示从指定节点出发,广播所有节点所需要的时间。

输入样例    复制

5 7
1 4
2 1
2 3
2 4
3 4
3 5
4 5
2

输出样例    复制

4