0918 - 所属の判定(彼女は手動でやっている)
問題
「ああ、面倒ですわ・・・」
いつも通り、山積みの仕事に苦しめられていた・・・。今回の仕事は役人 a と役人 b の所属が同じかどうかを判断するというものである。
「もう・・・駄目、ですわ・・・」バタッ
とても大変そうなので、あなたは代わりにやってあげることにした。
「 "休み" を要求しますわ!」
入力
n q com0 a0 b0 comq-1 aq-1 bq-1
1 行目に役人の人数を表す整数 n とクエリの数を表す整数 q が与えられる。
続く q 行に整数 com , a , b が与えられる。
com の値が 0 の場合は役人 a と役人 b が同じ所属であることを意味し、com の値が 1 の場合は役人 a と役人 b が同じ所属であるかどうかを出力することを意味する。
出力
com に 1 が入力された段階で、役人 a と役人 b が同じ所属かどうかを出力する。所属が同じ場合は "Same" 、異なる場合は "Different" と出力せよ。出力の最後に改行を忘れずに。
制約
全ての入出力ケースについて以下を満たす。
- 2 ≦ n ≦ 10,000
- 1 ≦ q ≦ 100,000
- 必ず一回は com に 1 が入力される。
入出力例
入力例1
5 5 0 1 2 0 1 5 1 2 5 0 3 4 1 3 5
出力例1
Same Different
入力例2
3 5 1 1 2 1 2 3 0 2 3 1 1 3 1 2 3
出力例2
Different Different Different Same