Doctor Who的TARDIS
描述
Doctor Who
刚刚重生为12th
,TARDIS
重新装修过之后是一棵“树”,TARDIS
有个房间,并且有根走廊连接,每个房间都可以相互到达,且俩个房间之间的路线都是唯一的。
Doctor Who
想邀请Clara
前来参观,为了防止Clara
走错,并且还指定一份参观指南,他希望Clara
能够按照他的指南顺序,先去,再去,,最后到 ,去参观TARDIS
。可是这样会导致重复走很多房间,Clara
不停地推辞。可是Doctor Who
告诉他,每走到一个房间,他就可以从房间拿一块糖果吃。
Clara
立马就答应了。现在Doctor Who
希望知道为了保证Clara
有糖果吃,他需要在每一个房间各放至少多少个糖果。
因为Doctor Who
参观指南上的最后一个房间 是餐厅,餐厅里他准备了丰盛的大餐,所以当Clara
在参观的最后到达餐厅时就不需要再拿糖果吃了。
格式
输入格式
第一行一个正整数,表示房间个数第二行个正整数,依次描述 。
接下来 行,每行两个正整数,表示标号和的两个房间之间有走廊相连。
输出格式
一共行,第行输出标号为的房间至少需要放多少个糖果,才能让Clara
有糖果吃。
样例1
样例输入1
样例输出1
限制
对于全部的数据,。