題目

某通信網(wǎng)絡(luò)中有N個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)，用1到N進(jìn)行標(biāo)識(shí)。

網(wǎng)絡(luò)中的結(jié)點(diǎn)互聯(lián)互通，且結(jié)點(diǎn)之間的消息傳遞有時(shí)延，相連結(jié)點(diǎn)的時(shí)延均為一個(gè)時(shí)間單位。

現(xiàn)給定網(wǎng)絡(luò)結(jié)點(diǎn)的連接關(guān)系link[i]={u，v}，其中u和v表示網(wǎng)絡(luò)結(jié)點(diǎn)。

當(dāng)指定一個(gè)結(jié)點(diǎn)向其他結(jié)點(diǎn)進(jìn)行廣播，所有被廣播結(jié)點(diǎn)收到消息后都會(huì)在原路徑上回復(fù)一條響應(yīng)消息，請計(jì)算發(fā)送結(jié)點(diǎn)至少需要等待幾個(gè)時(shí)間單位才能收到所有被廣播結(jié)點(diǎn)的響應(yīng)消息。

注：

N的取值范圍為[1，100];

連接關(guān)系link的長度不超過3000，且1 <= u,v <= N;

網(wǎng)絡(luò)中任意結(jié)點(diǎn)間均是可達(dá)的;

輸入描述

輸入的第一行為兩個(gè)正整數(shù)，分別表示網(wǎng)絡(luò)結(jié)點(diǎn)的個(gè)數(shù)N，以及時(shí)延列表的長度T；

接下來的T行輸入，表示結(jié)點(diǎn)間的連接關(guān)系列表；

最后一行的輸入為一個(gè)正整數(shù)，表示指定的廣播結(jié)點(diǎn)序號(hào)；

輸出描述

輸出一個(gè)整數(shù)，表示發(fā)送結(jié)點(diǎn)接收到所有響應(yīng)消息至少需要等待的時(shí)長。

示例

輸入

5 7

1 4

2 1

2 3

2 4

3 4

3 5

4 5

2

輸出

4

說明

結(jié)點(diǎn)2到5的最小時(shí)延為2，到剩余結(jié)點(diǎn)的最小時(shí)延均為1，所以至少要等待2*2=4s。

Java 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128174233

Python實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/128385295

C++ 實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/127174743

JavaScript實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/130729142

C實(shí)現(xiàn)：https://renjie.blog.csdn.net/article/details/129190260