全国高等学校パソコンコンクール
プログラミング部門 本選問題
２０２２年１１月５日(土)１３時１５分～１７時１５分

全国高等学校パソコンコンクール実行委員会

問題１

卓球

（２点）

卓球では、試合中に選手がタオルを使って汗を拭いてよいタイミングが決められています。一部例外がありますが、基本的にタオルを使ってよいのは、点数が「３対３」や「５対７」のように、両者の点数の和が６の倍数になっているときだけです。

課題
卓球の試合の現時点の点数が与えられたとき、タオルを使ってよいタイミングかどうかを判定するプロ
グラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑝𝑞
１行に卓球の試合の点数「𝑝対𝑞」を表す整数𝑝と𝑞(0 ≤ 𝑝, 𝑞 ≤ 10)が与えられる。ただし、𝑝 + 𝑞 ≥ 1である。

出力
現在の点数がタオルを使ってよいタイミングなら「1」、そうでないなら「0」を１行に出力する。

入出力例
入力例１5 7

出力例１1

入力例２3 5

出力例２0

問題２

ベコレンジャーカード（３点）

ヤエちゃんが通う学校では、ベコレンジャーカードが人気です。同じキャラクターのカードを２枚集めると、そのキャラクターのグッズがもらえます。
ヤエちゃんの兄のカクマ君は、ベコレンジャーカードを４枚手に入れたので、それをヤエちゃんにあげることにしました。ところがヤエちゃんにあげる前にカードを１枚紛失してしまいました。残った３枚のカードで、ヤエちゃんはグッズをもらえるでしょうか。

課題
カクマ君が持っていた４枚のカードの情報が与えられるが、どのカードが紛失したかわからない。このとき、グッズを必ずもらえる場合、もらえる可能性が全くない場合、もらえる可能性はあるが必ずではない場合のうち、どの場合になるかを判定するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑐 𝑐 𝑐 𝑐
１行に４枚のカードに書かれたキャラクターを表す整数𝑐 (1 ≤ 𝑐 ≤ 4)が与えられる。

出力
どのカードを紛失しても、ヤエちゃんがグッズを必ずもらえる場合は「1」、もらえる可能性が全くない場合は「2」、もらえる可能性はあるが必ずではない場合は「3」を１行に出力する。

入出力例入力例１1 1 1 1

出力例１1入力例２1 2 3 4出力例２2

入力例３4 3 4 2出力例３3問題３直方体ボート（４点）

PCK 君は直方体の形をしたボートを作っています。PCK 君は、このボートのサイズを幅が長さの３分の１、高さが幅の２分の１で、長さ、幅、高さをｃｍ単位で整数にしようと考えています。
このボートに積み荷を載せて水に浮かべます。積み荷を載せたボートが水に浮くのは、ボートと積み荷の重さの合計と、ボートによって押しのけられた水の重さがちょうど釣り合うときです。PCK 君はボートの上面と水面が平行になるように、ボートをそっと浮かべます。このとき、ボートの上面から水面までの距離（乾舷、図の実線矢印のところの長さ）を３０ｃｍ以上にしたいと考えているので、そうなるようにボートのサイズを決めなければなりません。

幅
ボート
高さ

乾舷
水課題
ボートに載せる積み荷の重さが与えられたとき、ボートの長さ、幅、高さがそれぞれ最小何ｃｍになるかを求めるプログラムを作成せよ。ただし、１リットル（＝１０００立方ｃｍ）の水の重さは１キログ
ラム、ボートの重さは大きさにかかわらず５０キログラムとする。

入力
入力は以下の形式で与えられる。
𝑊
１行にボートに載せる積み荷の重さ𝑊(1 ≤ 𝑊 ≤ 1,000)がキログラム単位の整数で与えられる。

出力
ボートの長さ、幅、高さを、空白区切りで１行にｃｍ単位で出力する。

入出力例
入力例１300

出力例１270 90 45

入力例２500

出力例２300 100 50

問題４演算装置の接続（６点）

あなたは、複数の演算装置を互いに接続して、特殊な処理を行おうとしている。演算装置にはいくつかの接続ポートがあり、一つのポートは他の演算装置の一つのポートにだけ接続できる。異なる演算装置の接続ポート同士をつなげることで、それらの演算装置を接続できる。行おうとしている処理は、以下の性質を持っている。


演算装置に接続されていない接続ポートがあると、処理が失敗する。
一つの演算装置の複数のポートが同じ演算装置に直接接続していると、処理が失敗する。

あなたは、使用する演算装置の数とそれぞれの演算装置の接続ポートの数がわかった時点で、処理が成功する接続方法があるかどうか判別できることに気がついた。

課題
演算装置の数とそれぞれの演算装置の接続ポート数が与えられたとき、処理が成功する接続方法があるかどうかを出力するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑎 𝑎 ⋯𝑎
１行目に演算装置の数𝑁(1 ≤ 𝑁 ≤ 200,000)が与えられる。続く１行に、𝑖番目の演算装置の接続ポートの数𝑎 (1 ≤ 𝑎 ≤ 200,000)が与えられる。ただし、𝑎 の総和は200,000以下である。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力
処理が成功する接続方法がある場合は「Yes」、そうでない場合は「No」を出力する。

入出力例
入力例１43 3 2 2

出力例１Yes

入力例２32 3 3

出力例２No問題５どろだんご（７点）

ウジサト君はどろだんごを販売する会社を経営している。仕入れたどろだんごに土と水を塗り、美しいどろだんごに仕上げて販売している。
ウジサト君は、様々な粘度の土と、様々な純度の水に、土には 1 から𝑁、水には 1 から𝑀の番号を振って管理している。それらの中から、それぞれ数種類使ってどろだんごを作る。一つのどろだんごを完成させるまで、様々な土と水を選びそれらを順番に塗っていく。ただし、一度使った土や水を２回以上塗ることはできない。
どろだんごの品質は、大きさ、柔らかさ、美しさの３つの尺度により決まる。大きさ𝑠、柔らかさℎ、美しさ𝑏のどろだんごに土か水を塗ると、その大きさ、柔らかさ、美しさは以下のようになる。


粘度𝑣の土を塗ると、大きさと美しさがそれぞれ𝑣、ℎ × 𝑣増える。柔らかさは変わらない。
純度𝑝の水を塗ると、柔らかさと美しさがそれぞれ𝑝、𝑠 × 𝑝増える。大きさは変わらない。

ウジサト君は、常連客からどろだんごの美しさのバリエーションはどれくらいあるのかという質問を受けた。そこで、ウジサト君はどろだんごの美しさが何種類あるかを求めるプログラムを書くことにした。

課題
土の種類と水の種類の数、それぞれの土の粘度と水の純度が与えられたとき、それらを使って作れるどろだんごの美しさが何種類あるかを求めるプログラムを作成せよ。ただし、仕入れたときのどろだんごの大きさ、柔らかさ、美しさはどれも 1 とし、仕入れたときのどろだんごの美しさも一つの種類とする。

入力
入力は以下の形式で与えられる。
𝑁𝑀𝑣 𝑣 …𝑣
𝑝 𝑝 …𝑝
１行目に、土の種類の数𝑁 (1 ≤ 𝑁 ≤ 10)と水の種類の数𝑀 (1 ≤ 𝑀 ≤ 10)が与えられる。２行目に、𝑖番目の種類の土の粘度𝑣 (1 ≤ 𝑣 ≤ 100,000,000)が整数で与えられる。３行目に、𝑖番目の種類の水の純度𝑝 (1 ≤ 𝑝 ≤ 100,000,000)が整数で与えられる。

出力
どろだんごの美しさが何種類あるかを１行に出力する。

入出力例
入力例１1 273 5

出力例１8入力例２3 31 2 31 1 1

出力例２19問題６

一筆書き

（９点）

PCK 君が画用紙に絵を描いている。PCK 君は以下のように絵を描く。


一回の動作で、１つの線分を描く。
既に描かれている線分に触れる場合は、お互いの端点だけで重なる。

この動作を繰り返すと、画用紙にはいくつかの図形が現れる。ここでは、連結した線分のグループを１つの図形とする。たとえば、図(a)には、それぞれ５本と１本の線分からなる２つの図形が描かれている。図(a)に 1 本の線分を追加して図(b)のように描くと、７本の線分からなる１つの図形になる。

画用紙に描かれている図形の中で、一筆書きが可能なものはいくつあるだろうか？一筆書きとは、筆記具を画用紙から一度も離さず、同じ線を二度なぞらずに線図形を描くことである。ただし、同じ端点を何回通っても構わない。たとえば、図の(a)、(b)、(c)の順に描いていったとき、それぞれで一筆書きが可能な図形は、２個、０個、１個ある。

課題
PCK 君が線分を描く動作の情報が順番に与えられる。動作が終わるごとに、画用紙に含まれる一筆書きが可能な図形の数を報告するプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
𝑠𝑒𝑔𝑚𝑒𝑛𝑡
𝑠𝑒𝑔𝑚𝑒𝑛𝑡:
𝑠𝑒𝑔𝑚𝑒𝑛𝑡
１行目に、線分の数𝑁 (1 ≤ 𝑁 ≤ 200,000)が与えられる。続く𝑁行に、𝑖番目の動作で描く線分の情報が与えられる。ただし、同じ線分が与えられることはない。各線分は以下の形式で与えられる。
𝑥 𝑦 𝑥 𝑦線分の始点の座標𝑥 , 𝑦 (0 ≤ 𝑥 , 𝑦 ≤ 1,000,000,000)と終点の座標𝑥 , 𝑦 (0 ≤ 𝑥 , 𝑦 ≤ 1,000,000,000)が整数で与えられる。ただし、始点と終点の座標が同じものが与えられることはない（𝑥 ≠ 𝑥 または𝑦 ≠𝑦 ）。

時間制限
入力に対して、実行時間が２秒を超えてはならない。

出力各動作の後に、一筆書きが可能な図形の個数を１行に出力する。

入出力例
入力例
85 0 8 35 6 2 310 5 10 12 3 5 05 0 5 68 3 5 68 3 10 110 5 8 3出力例
12322201

問題７素数の日の並び（１０点）

１週間にはある月に属する日だけではなく、その前の月の日や、その次の月の日も含まれることがある。たとえば 2022 年 11 月 1 日が含まれる週から、12 月 31 日が含まれる週までの週の並びを見ると、 日右の図のようになっている。
このような週の並びで、日曜日から土曜日までの 1 週間分の日の並びに、最大でいくつの素数の日が入っているかを考える。右の図の場合、各週の素数の日は以下のようになる。


1 週目の素数の日は 31、2、3、5 の 4 つ。
2 週目の素数の日は 7, 11 の 2 つ。
3 週目の素数の日は 13, 17, 19 の 3 つ。
4 週目の素数の日は 23 だけで 1 つ。
5 週目の素数の日は 29, 2, 3 の 3 つ。
6 週目の素数の日は 5, 7 の 2 つ。
7 週目の素数の日は 11, 13, 17 の 3 つ。
8 週目の素数の日は 19, 23 の 2 つ。
9 週目の素数の日は 29, 31 の 2 つ。

2022 年 11 月,12 月
月 火 水 木 金 土

30 31

12368910 11 1274513 14 15 16 17 18 1920 21 22 23 24 25 26
27 28 29 30

1234891056711 12 13 14 15 16 1718 19 20 21 22 23 2425 26 27 28 29 30 31

つまり、2022 年 11 月 1 日が含まれる週から 12 月 31 日が含まれる週までのうち、素数の日の数の最大値は 4 で、そのような週の数は 1 である。このように、週を常に日曜日から始める 7 日間としたとき、素数の日の数が最大になる週が、ある期間において何度現れるだろうか？
ただし、西暦 2000 年 1 月 1 日は土曜日とする。また、4 で割り切れてかつ 100 で割り切れないか、400で割り切れる年は閏年とする。1 月、3 月、5 月、7 月、8 月、10 月、12 月は 31 日まで、2 月は 28 日まで（ただし閏年では 29 日まで）、他の月は 30 日まである。

課題
開始年月と終了年月が与えられたとき、その開始年月の 1 日が含まれる週から、終了年月の最後の日が含まれる週までの期間において、一つの週に現れる素数の日の数の最大値と、素数の日の数が最大になる週の数を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑦 𝑚𝑦 𝑚
１行目に開始年𝑦 (2000 ≤ 𝑦 ≤ 100,000,000)と開始月𝑚 (1 ≤ 𝑚 ≤ 12)、２行目に終了年𝑦 (𝑦 ≤ 𝑦 ≤100,000,000)と終了月𝑚 (1 ≤ 𝑚 ≤ 12)が与えられる。ただし、𝑦 = 𝑦 のときは𝑚 ≤ 𝑚 とする。

出力一つの週に現れる素数の日の数の最大値と、素数の日の数が最大になる週の数を、空白区切りで１行に出力する。

入出力例
入力例１2022 12022 12

出力例１4 8

入力例２2003 92022 11

出力例２4 156

問題８

ゲームブック（１１点）

ゲームブックとは、読者の選択によって指定されたページへ移動することで、物語を楽しめる本である。
たとえば、本の 5 ページ目に、ページ番号 8、17、32 が書かれていれば、読者はこれらの中から１つ選択して、5 ページ目から 8、17、32 ページ目のいずれかへ飛ぶことができる。
あなたは𝑁ページのゲームブックを作成しようとしている。各ページにはいくつかのページ番号を書き込む。以下の条件をすべて満たすページ番号の書き方は何通りあるだろうか？


各ページには、そのページ番号よりも大きいページ番号を書き込む。
1 ページ目から、直接またはいくつかのページを経由して、任意のページにたどり着ける。
任意のページから、直接またはいくつかのページを経由して、𝑁ページ目にたどり着ける。

課題
ゲームブックのページ数が与えられる。上の条件を満たすページ番号の書き込み方が何通りあるかを求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
１行にページの数𝑁 (2 ≤ 𝑁 ≤ 500)が与えられる。

出力
ページ番号の書き込み方が何通りあるかを表す数を 998,244,353 で割った余りを１行に出力する。

入出力例
入力例１3

出力例１2

入力例２5

出力例２122

問題９縄張りの大きさ（１１点）

イズア地方には、東西に𝑊本、南北に𝐻本の木が格子状に並ぶ森がある。ただし，並んでいる木の種類は同じとは限らない。この森には奇妙な習性を持つ鳥が住んでいる。
a b b c d
この鳥は、東西と南北にそれぞれ同じ数だけ並んだ正方形の木の領域を縄張りとする。少なくとも𝑘箇所の縄張りを確保し、それらを次々と移動する。ただし、この鳥 a a b b aはとてもデリケートなので、それらの縄張りはどれも同じ大きさで、その中の木の並 a a a b b
びが同じになっていなければならない。そのような縄張りを𝑘箇所以上確保できると a a a a a
きは、一つの縄張りが最も広くなるものを選ぶ。
たとえば、右の図のような東西に５本、南北に４本の木が格子状に並んだ森がある（英小文字は木の種類を表す）とき、縄張りを２箇所以上確保したい鳥(𝑘 = 2)は、線で囲んだ２つの縄張りの間を移動する。
鳥類学者であるあなたは、この鳥の一つの縄張りの大きさを明らかにしたいと考えている。

課題
森の情報と鳥が確保したい縄張りの最低の個数が与えられたとき、その鳥が確保する一つの縄張りの大きさを求めるプログラムを作成せよ。ただし、縄張りの大きさは、その中に東西または南北に並んだ木の本数で表すものとする。

入力
入力は以下の形式で与えられる。
𝐻𝑊𝑘𝑡, 𝑡, …𝑡,𝑡 , 𝑡 , …𝑡 ,:𝑡 , 𝑡 , …𝑡 ,１行目に、森の木が南北に並んだ本数𝐻 (1 ≤ 𝐻 ≤ 600)、東西に並んだ本数𝑊 (1 ≤ 𝑊 ≤ 600)と、鳥が少なくとも確保したい縄張りの数𝑘 (2 ≤ 𝑘 ≤ 𝐻 × 𝑊)が与えられる。続く𝐻行に、格子状に並んだ木の情報が英小文字で与えられる。ただし、𝑡 , , 𝑡 , , 𝑡 , , 𝑡 , はそれぞれ森の北西、北東、南西、南東の隅にある木を表す。文字の種類が木の種類に対応する。

時間制限
入力に対して、実行時間が３秒を超えてはならない。

出力鳥が確保する一つの縄張りの中に、東西または南北に並んだ木の本数を 1 行に出力する。ただし、縄張りを𝑘箇所以上確保できないときは、「-1」を出力する。

入出力例
入力例１4 5 2
abbcd
aabba
aaabb
aaaaa

出力例１3

入力例２3 3 5cbbdabaaa

出力例２-1

問題１０

数列の復元

（１１点）

長さ𝑁の数列𝑇 = (𝑇 , 𝑇 , ⋯ , 𝑇 )と、正整数𝑋,𝑌が与えられる。あなたは全ての要素の値が 0 である長さ𝑁の数列𝐴 = (𝐴 , 𝐴 , ⋯ , 𝐴 )に対して操作を行い、数列𝑇と等しくなるようにしたい。
数列𝐴に対して以下の操作𝑓 を複数回行うことができる。ただし𝑘 = 1, 2, ⋯ , 𝑁である。
𝑓 ：数列𝐴の𝑘番目の要素に𝑋を加算し、それ以外の要素から𝑌を減算する。
数列𝐴を数列𝑇と等しくするために行った各操作の回数の列を求めたい。ただし、数列𝐴と𝑇を等しくすることが不可能な場合もある。

課題
数列𝑇と 2 つの正整数が与えられたとき、数列𝐴を数列𝑇と等しくするための各操作の回数の列を出力するプログラムを作成せよ。ただし、そのような各操作の回数の列が複数存在する場合は、操作の回数の総和が最も少ないものの列を出力せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑋𝑌𝑇 𝑇 ⋯𝑇
１行目に、数列の要素数𝑁(2 ≤ 𝑁 ≤ 200,000)と２つの正整数𝑋, 𝑌(1 ≤ 𝑋, 𝑌 ≤ 100,000,000)が与えられる。続く１行に、𝑖番目の数列の要素𝑇 (−1,000,000,000 ≤ 𝑇 ≤ 1,000,000,000)が整数で与えられる。

出力
数列を等しくすることができる場合は、各操作の回数を 1 行に空白区切りで出力する。数列を等しくすることができない場合は、「-1」を出力する。

入出力例
入力例１5 4 1-5 10 0 0 -5

出力例１0 3 1 1 0

入力例２5 4 2-5 10 0 0 -5出力例２-1

問題１１ 𝑵数列

（１２点）

𝑁個の要素からなる𝑁本の数列𝐴 , 𝐴 , ⋯ , 𝐴 があり、数列𝐴 の𝑗番目の要素を𝐴 , と表す。最初はすべての数列𝐴 について 𝐴 , , 𝐴 , , ⋯ , 𝐴 , = (𝑎 , 𝑎 , ⋯ , 𝑎 )であるとする。
数列𝐴 , 𝐴 , ⋯ , 𝐴 に対して、以下の３種類の操作が行える。


数列𝐴 を数列𝐴 で置き換える。
数列𝐴 の𝑠番目の要素𝐴 , の値と、数列𝐴 の𝑡番目の要素𝐴 , の値を入れ替える。



数列𝐴 に対して、𝑠番目から𝑡番目の要素の総和を出力する。

課題
数列の初期値と操作のリストが与えられたとき、リスト中のすべての操作を順番に行うプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁𝑄𝑎 𝑎 ⋯𝑎𝑞𝑢𝑒𝑟𝑦
𝑞𝑢𝑒𝑟𝑦:
𝑞𝑢𝑒𝑟𝑦
１行目に数列の本数と要素の数𝑁 (2 ≤ 𝑁 ≤ 200,000)と操作の数𝑄 (1 ≤ 𝑄 ≤ 200,000)が与えられる。続く１行に、すべての数列の要素の初期値𝑎 (1 ≤ 𝑎 ≤ 1,000,000,000)が整数で与えられる。続く𝑄行に、操作のリスト中の𝑖番目の操作𝑞𝑢𝑒𝑟𝑦 が与えられる。各操作は以下のいずれかの形式で与えられる。
1𝑥𝑦または
2𝑥𝑠𝑦𝑡または
3𝑥𝑠𝑡
1 𝑥 𝑦 は、数列𝐴 (1 ≤ 𝑦 ≤ 𝑁)を数列𝐴 (1 ≤ 𝑥 ≤ 𝑁)で置き換える操作を表す。
2 𝑥 𝑠 𝑦 𝑡 は、数列𝐴 (1 ≤ 𝑥 ≤ 𝑁)の𝑠 (1 ≤ 𝑠 ≤ 𝑁)番目の要素の値と、数列𝐴 (1 ≤ 𝑦 ≤ 𝑁)の𝑡 (1 ≤ 𝑡 ≤𝑁)番目の要素の値を入れ替える操作を表す。
3 𝑥 𝑠 𝑡 は、数列𝐴 (1 ≤ 𝑥 ≤ 𝑁)に対して、𝑠 (1 ≤ 𝑠 ≤ 𝑁)番目から𝑡 (𝑠 ≤ 𝑡 ≤ 𝑁)番目の要素の総和を出力する操作を表す。この操作は１回以上与えられる。

時間制限
入力に対して、実行時間が１秒を超えてはならない。

出力
総和を出力する操作それぞれについて、結果を１行に出力する。

入出力例
入力例１3 41 2 33 1 2 32 1 2 3 3
1 1 33 1 2 3

出力例１56入力例２3 61 2 33 3 1 32 1 1 3 3
1 3 23 1 1 33 2 1 33 3 1 3

出力例２6844

問題１２三角形パズル（１４点）

平面上に２つ以上の三角形の集合が与えられる。与えられる三角形は、以下の条件を満たすものとする。
 これらの三角形が互いに重なることはない。
 各三角形は、少なくとも他の一つの三角形と、辺の一部を共有して連結している。ただし、２つの三角形が１点だけを共有する場合は、連結とはみなさない。つまり、図(b)、図(c)、図(d)のような三角形の集合は与えられない。
 三角形の集合が形成する多角形の内部は、三角形によりすべて埋め尽くされている。つまり、図(e)のような三角形の集合は与えられない。
これらの三角形で形成される多角形のすべての頂点の座標を求めよ。たとえば、図(a)の三角形の集合からは、図(f) の多角形が得られる。
𝑦𝑥

課題
上の条件を満たすように２つ以上の三角形が与えられたとき、それらが形成する多角形のすべての頂点の座標を求めるプログラムを作成せよ。

入力
入力は以下の形式で与えられる。
𝑁
𝑇𝑟𝑖𝑎𝑛𝑔𝑙𝑒
𝑇𝑟𝑖𝑎𝑛𝑔𝑙𝑒:
𝑇𝑟𝑖𝑎𝑛𝑔𝑙𝑒
１行目に、三角形の個数𝑁 (2 ≤ 𝑁 ≤ 100,000)が与えられる。
続く𝑁行に、𝑖番目の三角形の情報𝑇𝑟𝑖𝑎𝑛𝑔𝑙𝑒 が与えられる。各𝑇𝑟𝑖𝑎𝑛𝑔𝑙𝑒 は以下の形式で与えられる。
𝑥 𝑦 𝑥 𝑦 𝑥 𝑦𝑖 番 目 の 三 角 形 の 𝑗 番 目 の 頂 点 の 𝑥 座 標 𝑥 (−1,000,000,000 ≤ 𝑥 ≤ 1,000,000,000) と 𝑦 座 標𝑦 (−1,000,000,000 ≤ 𝑦 ≤ 1,000,000,000)が、それぞれ整数で反時計回りの順に与えられる。

時間制限
入力に対して、実行時間が１秒を超えてはならない。

出力
三角形の集合が形成する多角形の輪郭線に沿って、多角形の各頂点の𝑥座標と𝑦座標を表す整数の組を、空白区切りで１行に出力する。頂点は以下の順番で出力する。


起点となる頂点 P1 を出力する。起点とは𝑦座標が最も小さい頂点である。そのような頂点が複数ある場合は、それらの中で𝑥座標が最も小さい頂点を起点とする。
２番目の点を出力する。２番目の点は、P1 を中心として𝑥軸の正の方向を基準として反時計回りに見たとき最初に見つかる P1 と直接つながる頂点とする。
３番目以降は、直前に出力した点と直接つながる頂点のうち、未訪問の点を出力する。

入出力例
入力例１20 0 4 4 0 4
1 1 3 1 3 3

出力例１0 01 13 13 34 40 4

入力例２30 0 2 0 1 22 0 3 2 1 2
2 0 4 0 3 2

出力例２0 04 03 21 2

下図の(a)(b)はそれぞれ入力例２と出力例２を表す。
𝑦𝑥