Balanced Path

問題文

頂点数 $N$ 、辺数 $M$ の単純連結無向グラフが与えられる。頂点には $1$ から $N$ までの番号が振られており、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいる。

このグラフから頂点 $S$ から始まるパスを削除することで、すべての連結成分の頂点数を $\left\lfloor{\dfrac{N}{2}}\right\rfloor$ 以下にすることができるか判定し、できるならばパスを求めよ。

厳密には、次の条件をすべて満たす頂点列 $P=(P_1,P_2,\dots,P_K)$ が存在するか判定し、存在するなら一つ求めよ。

• $1\le K\le N$
• $P_1=S$
• $P_1,P_2,\dots,P_K$ は相異なる。
• すべての $1\le i<K$ に対して、頂点 $P_i$ と頂点 $P_{i+1}$ の間に辺が存在する。
• グラフから頂点 $P_1,P_2,\dots,P_K$ とそれらに接続する辺をすべて削除したとき、残ったグラフの各連結成分の頂点数は $\lfloor N/2\rfloor$ 以下である。

制約

• 入力はすべて整数である。
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le S \le N$
• $1 \le u_i, v_i \le N$
• 与えられるグラフは単純かつ連結である。

入力

入力は以下の形式で標準入力から与えられる。

出力

条件を満たす頂点列が存在しない場合、No を出力せよ。

存在する場合、以下の形式で出力せよ。

条件を満たすパスが複数存在する場合、どれを出力してもよい。

サンプル

サンプル 1

入力

8 8 1
1 2
2 3
2 4
3 5
5 6
4 7
7 8
5 8

出力

Yes
4
1 2 3 5

頂点 $1,2,3,5$ を削除すると、残ったグラフの連結成分は $\{4,7,8\}$ と $\{6\}$ になる。いずれも頂点数は $4$ 以下である。