#p4925. 例题8.3.2 单位图最短路径

例题8.3.2 单位图最短路径

D 山洞

题目描述

有一个山洞,山洞里有NN个洞室,被分别从11到NN标号,洞室之间有MM条通道连接,被从11到MM标号,第ii条通道双向连接洞室AiA_i和BiB_i。只有洞室11和外界联通。

为了防止迷路,现在需要在除了洞室11之外的每个洞室都插一个路标,指向与其相连的某个洞室,要求你合理地安排路标,使得从任意一个洞室出发,并沿着路标走,都能经过最少的洞室走出洞穴。

保证从任意一个洞室出发都能走到11号洞室。如果有多种方案,只需输出任意一种。

输入格式

第一行两个用空格隔开的整数NN和MM。

接下来MM行,第ii行有两个用空格隔开的整数AiA_i和BiB_i。

输出格式

如果不存在满足题目要求的方案,输出“No"。

如果存在,第一行输出"Yes",接着输出N−1N-1行,每行一个整数,表示第22到第NN个洞室放置的路标指向的洞室标号。

样例数据

input


4 4

1 2

2 3

3 4

4 2

output


Yes

1

2

2

input


6 9

3 4

6 1

2 4

5 3

4 6

1 5

6 2

4 5

5 6

output


Yes

6

5

5

1

1

数据规模与约定

2≤N≤1052\leq N\leq 10^5

1≤M≤2×1051\leq M\leq 2\times 10^5

1≤Ai,Bi≤N (1≤i≤M)1\leq A_i,B_i\leq N\ (1\leq i\leq M)

Ai≠Bi (1≤i≤M)A_i\neq B_i\ (1\leq i\leq M)

时间限制:2s2 \text {s}

空间限制:1024MB1024 \text {MB}