山登り
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
山登りに来た paiza 君は、途中仲間と逸れてしまい遭難してしまいました。
paiza 君のバッグには幸いにも山のマップが入っており、山には N 個のチェックポイントとそれらをつなぐ N-1 本の道があり、チェックポイント 1 つ分移動すると、山の中での高さが 1 つ変化することを確認しました。マップの一番上に山の頂点が書かれているので、マップの上側に移動することは山を登ることを、下側に移動することは山を下ることを意味します。
paiza 君はやっとの思いでチェックポイントらしき場所に到着しましたが、肝心のチェックポイント番号が書かれていません。
自分がスタートした位置と山を登る方面・降りる方面に何本の道を歩いたかを記録していた paiza 君は、これらの情報とマップの情報を合わせることで、自分が今いる可能性のあるチェックポイントがわかることに気がつきました。
山についての情報と paiza 君が記録していた情報についての入力が与えられるので、 paiza 君がいる可能性のあるチェックポイントの場所を求めてください。
ただし、paiza 君が山から脱出することはないものとします。
例として、入力例 1 を考えると、山には以下の通りチェックポイントがあります。
スタート地点は チェックポイント 4 で、2 回登り、 1 回降ります。
2 回登ったのち 1 回降りた場合は (4, 2, 1, 3) または (4, 2, 1, 2) という順にチェックポイントを通ります。
同様に 1 回登り、1 回降り、1 回登った場合は (4, 2, 4, 2) または (4, 2, 5, 2)、
1 回降り 2 回登った場合は、(4, 7, 4, 2) という順になります。
よって、paiza 君がいる可能性のあるチェックポイントは 2, 3 となります。
- 入力される値
-
N T S C D
a_1 b_1
...
a_{N-1} b_{N-1}
・1 行目には、山のチェックポイントの数 N, 山の頂点に割り当てられたチェックポイントの番号 T, paiza 君が出発したチェックポイントの番号 S, paiza 君が山を登った回数 C, 降りた回数 D が与えられます。
・続く N-1 行では、山の N-1 本の道の両端のチェックポイントの番号が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・paiza 君がいる可能性のあるチェックポイントの番号を昇順で改行区切りで全て出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100
・ 1 ≦ T ≦ N
・ 1 ≦ S ≦ N
・ 0 ≦ C ≦ 5
・ 0 ≦ D ≦ 5
・ 登った回数の合計が C 回、下った回数の合計が D 回である移動方法が必ずあることが保証されている。
- 入力例1
-
8 1 4 2 1
1 2
1 3
2 4
2 5
3 6
4 7
6 8
- 出力例1
-
2
3
- 入力例2
-
10 6 9 1 1
9 10
3 9
4 3
6 10
5 3
7 6
2 3
8 10
1 2
- 出力例2
-
8
9
