Rule


ルール

ワクチンを用いてウイルスを撲滅せよ

TSG国では、これまで確認されていなかった新型のウイルスが9種類も同時に発見され、未曾有の災禍をもたらしていました。

幸い、KMC研究所がそれぞれのウイルスに合わせた9種類のワクチンの開発に成功し、治療に用いられることになりました。

ところで、このウイルスは特殊な性質を持っており、一方向に3つ以上同じ種類のウイルスもしくは対応するワクチンが並ぶと消滅します。

さて、この新型ウイルスに感染した患者が32人やってきました。

検査により、体内に存在するウイルスの配列、およびワクチンを投与する場所はすでにわかっています。

消滅させられるウイルスを最大化するために投与するべきワクチンの種類を答えてください。

入力

出力

制約

パターン

入出力例

入力1

994 499
811 211
879 596
366 668
685 879
122 998
578 927
644 779
628 823
811 857
688 891
812 224
755 554
634 236
972 772
895 951
413 556
953 396
547 787
488 583
446 448
338 528
411 155
366 926
862 927
126 273
528 665
258 588
626 664
614 416
929 129
843 716

出力1

41566914818256765378451697666495

入力2

866 298
921 442
412 264
833 938
644 758
598 981
988 185
911 114
367 566
789 983
519 815
994 994
475 577
233 776
797 575
771 773
465 525
678 182
726 945
628 589
939 412
977 332
227 288
843 497
166 639
417 146
322 223
227 771
849 499
476 889
944 481
328 883

出力2

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