問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
paiza 国には 1 から n までの番号がついた n 個の地点と、それらを結ぶ m 本の道路があります。
i 番目の道路は、地点 a_i と地点 b_i を結んでいて、その距離は 5 km です。
今回、paiza 国では 2 つの避難場所をつくることにしました。
避難場所はそれぞれ地点 x, y にあります。
各地点について、地点 x までの最短距離と、地点 y までの最短距離のどちらが短いかを求めてください。
n m x y
a_1 b_1
...
a_m b_m
合計 n 行出力してください。
i 行目には、地点 i から地点 x までの最短距離のほうが短い場合には X is closer
, 地点 i から地点 y までの最短距離のほうが短い場合には Y is closer
, どちらも同じ場合には Same
を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ n ≦ 100,000 = 10^5
・ n - 1 ≦ m ≦ min(n × (n - 1) / 2, 100,000 = 10^5)
・ 1 ≦ x, y ≦ n
・ x ≠ y
・ 1 ≦ a_i, b_i ≦ n
・ a_i ≠ b_i
・ (a_i, b_i) ≠ (a_j, b_j), (a_i, b_i) ≠ (b_j, a_j) (i ≠ j)
・ 与えられるグラフは連結である
3 2 1 3
1 2
2 3
X is closer
Same
Y is closer