#11547. 路线【蓝桥杯】

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

有一个旅游景区,景区中有N个景点,景点以数字1到N编号,其中编号为N的景点为游客服务中心所在地。景区中有M条连接路线,每条路线连接两个景点。

已知:

1)一个景点可以被多条路线连接;

2)景点之间的连接路线都可以双向行走;

当给出N个景点和M条连接路线,及M条路线的连接关系,请你计算出从编号1到编号N-1的每一个景点,到达游客服务中心至少需要经过几条

路线,如果某个景点不能到达游客服务中心则输出“-1”。

例如:N=5,M=4,4条路线的连接关系为:1<->2、1<->3、2<->4、2<->5,

景点1到达景点5(游客服务中心)至少经过2条路线(路线2、路线4);

景点2到达景点5(游客服务中心)至少经过1条路线(路线4);

景点3到达景点5(游客服务中心)至少经过3条路线(路线1、路线2、路线4);

景点4到达景点5(游客服务中心)至少经过2条路线(路线3、路线4);

输入格式

第一行输入两个正整数N和M(4<=N<=100,1<=M<=100),N表示景点个数,M表示路线条数,两个正整数之间一个空格隔开

接下来输入M行,每行包括两个正整数S,E(1≤S≤N,1≤E≤N,S!=E),两个正整数之间一个空格隔开,表示编号S和编号E的两个景点有一条路线连接

输出格式

一行输出多个整数。按照1到N-1的编号顺序,分别输出每个景点到达编号N(游客服务中心),经过几条路线可以到达,如果某个景点不能到达则输出“-1”,整数之间一个空格隔开

样例

样例输入:

5 4
1 2
1 3
2 4
2 5

样例输出:

2 1 3 2

数据范围与提示

13届蓝桥杯c++省赛2E