// 01:北海道
// 02:青森県 03:岩手県 04:宮城県 05:秋田県 06:山形県 07:福島県
// 08:茨城県 09:栃木県 10:群馬県 11:埼玉県 12:千葉県 13:東京都 14:神奈川県
// 15:新潟県 16:富山県 17:石川県 18:福井県 19:山梨県 20:長野県
// 21:岐阜県 22:静岡県 23:愛知県 24:三重県
// 25:滋賀県 26:京都府 27:大阪府 28:兵庫県 29:奈良県 30:和歌山県
// 31:鳥取県 32:島根県 33:岡山県 34:広島県 35:山口県
// 36:徳島県 37:香川県 38:愛媛県 39:高知県
// 40:福岡県 41:佐賀県 42:長崎県 43:熊本県 44:大分県 45:宮崎県 46:鹿児島県 47:沖縄県
#include <stdio.h>
int main()
{
int connect[][10] =
{
{1, 2},
{2, 3, 5},
{3, 4, 5, 6},
{4, 5, 6, 7},
{5, 6},
{6, 7, 15},
{7, 8, 9, 10, 15},
{8, 9, 11, 12},
{9, 10, 11, 12, 13},
{10, 11, 19, 20},
{11, 12131920},
{12, 13},
{13, 1419},
{14, 19},
{15, 16, 20},
{16, 17, 20, 21},
{17, 18, 21},
{18, 21,25,26},
{19, 20,22},
{20, 22,23},
{21, 23,24,25},
{22, 23},
{23, 24},
{24, 25,26,29},
{25, 26,27,29},
{26, 27,28,29},
{27, 28,29,30},
{28, 31,33},
{29, 30},
{31, 32,33,34},
{32, 33,34,35},
{33, 34,37},
{34, 35,38},
{35, 40},
{36, 37,38,39},
{37, 38,39},
{38, 39},
{40, 41,43,44},
{41, 42,43},
{43, 44,45,46},
{44, 43,45},
{45, 46},
{46, 47}
};
return 0;
}
Ly8gMDE65YyX5rW36YGTCi8vIDAyOumdkuajruecjCAwMzrlsqnmiYvnnIwgMDQ65a6u5Z+O55yMIDA1Oueni+eUsOecjCAwNjrlsbHlvaLnnIwgMDc656aP5bO255yMCi8vIDA4OuiMqOWfjuecjCAwOTrmoIPmnKjnnIwgMTA6576k6aas55yMIDExOuWfvOeOieecjCAxMjrljYPokYnnnIwgMTM65p2x5Lqs6YO9IDE0OuelnuWliOW3neecjAovLyAxNTrmlrDmvZ/nnIwgMTY65a+M5bGx55yMIDE3Ouefs+W3neecjCAxODrnpo/kupXnnIwgMTk65bGx5qKo55yMIDIwOumVt+mHjuecjAovLyAyMTrlspDpmJznnIwgMjI66Z2Z5bKh55yMIDIzOuaEm+efpeecjCAyNDrkuInph43nnIwKLy8gMjU65ruL6LOA55yMIDI2OuS6rOmDveW6nCAyNzrlpKfpmKrlupwgMjg65YW15bqr55yMIDI5OuWliOiJr+ecjCAzMDrlkozmrYzlsbHnnIwKLy8gMzE66bOl5Y+W55yMIDMyOuWztuagueecjCAzMzrlsqHlsbHnnIwgMzQ65bqD5bO255yMIDM1OuWxseWPo+ecjAovLyAzNjrlvrPls7bnnIwgMzc66aaZ5bed55yMIDM4OuaEm+Wqm+ecjCAzOTrpq5jnn6XnnIwKLy8gNDA656aP5bKh55yMIDQxOuS9kOizgOecjCA0MjrplbfltI7nnIwgNDM654aK5pys55yMIDQ0OuWkp+WIhuecjCA0NTrlrq7ltI7nnIwgNDY66bm/5YWQ5bO255yMIDQ3Ouaylue4hOecjAoKI2luY2x1ZGUgPHN0ZGlvLmg+CmludCBtYWluKCkKewogICAgaW50IGNvbm5lY3RbXVsxMF0gPQogICAgewogICAgICAgIHsxLCAyfSwKICAgICAgICB7MiwgMywgNX0sCiAgICAgICAgezMsIDQsIDUsIDZ9LAogICAgICAgIHs0LCA1LCA2LCA3fSwKICAgICAgICB7NSwgNn0sCiAgICAgICAgezYsIDcsIDE1fSwKICAgICAgICB7NywgOCwgOSwgMTAsIDE1fSwKICAgICAgICB7OCwgOSwgMTEsIDEyfSwKICAgICAgICB7OSwgMTAsIDExLCAxMiwgMTN9LAogICAgICAgIHsxMCwgMTEsIDE5LCAyMH0sCiAgICAgICAgezExLCAxMjEzMTkyMH0sCiAgICAgICAgezEyLCAxM30sCiAgICAgICAgezEzLCAxNDE5fSwKICAgICAgICB7MTQsIDE5fSwKICAgICAgICB7MTUsIDE2LCAyMH0sCiAgICAgICAgezE2LCAxNywgMjAsIDIxfSwKICAgICAgICB7MTcsIDE4LCAyMX0sCiAgICAgICAgezE4LCAyMSwyNSwyNn0sCiAgICAgICAgezE5LCAyMCwyMn0sCiAgICAgICAgezIwLCAyMiwyM30sCiAgICAgICAgezIxLCAyMywyNCwyNX0sCiAgICAgICAgezIyLCAyM30sCiAgICAgICAgezIzLCAyNH0sCiAgICAgICAgezI0LCAyNSwyNiwyOX0sCiAgICAgICAgezI1LCAyNiwyNywyOX0sCiAgICAgICAgezI2LCAyNywyOCwyOX0sCiAgICAgICAgezI3LCAyOCwyOSwzMH0sCiAgICAgICAgezI4LCAzMSwzM30sCiAgICAgICAgezI5LCAzMH0sCiAgICAgICAgezMxLCAzMiwzMywzNH0sCiAgICAgICAgezMyLCAzMywzNCwzNX0sCiAgICAgICAgezMzLCAzNCwzN30sCiAgICAgICAgezM0LCAzNSwzOH0sCiAgICAgICAgezM1LCA0MH0sCiAgICAgICAgezM2LCAzNywzOCwzOX0sCiAgICAgICAgezM3LCAzOCwzOX0sCiAgICAgICAgezM4LCAzOX0sCiAgICAgICAgezQwLCA0MSw0Myw0NH0sCiAgICAgICAgezQxLCA0Miw0M30sCiAgICAgICAgezQzLCA0NCw0NSw0Nn0sCiAgICAgICAgezQ0LCA0Myw0NX0sCiAgICAgICAgezQ1LCA0Nn0sCiAgICAgICAgezQ2LCA0N30KICAgIH07CiAgICByZXR1cm4gMDsKfQo=