{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e.content-description h4 {\n font-size: 1.4em;\n border-bottom: 1px solid #eee;\n line-height: 1.225;\n padding-bottom: 0.3em;\n padding-top: 0.5em;\n font-weight: 700;\n}.content-description img {\n max-width: 100%;\n height: auto;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content-description screen\"\u003e\n\u003cdiv\u003e\u003cp\u003eGardens by the Bay is a large nature park in Singapore. In the park there are \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e towers, known as supertrees. These towers are labelled \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e to \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7c2f2bec1ec557e3f5b8a8f76709a8dd?v\u003d1715326211\" style\u003d\"vertical-align: -0.505ex; width:5.397ex; height:2.343ex;\" alt\u003d\"n - 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n - 1~\u003c/span\u003e\u003c/span\u003e. We would like to construct a set of \u003cstrong\u003ezero or more\u003c/strong\u003e bridges. Each bridge connects a pair of distinct towers and may be traversed in \u003cstrong\u003eeither\u003c/strong\u003e direction. No two bridges should connect the same pair of towers.\u003c/p\u003e\n\u003cp\u003eA path from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c5a1000106524b99ffb20096d04970b1?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.33ex; height:1.676ex;\" alt\u003d\"x\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~x~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0e8f621bd8562db91042eb6f9f4e6dd4?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:1.155ex; height:2.009ex;\" alt\u003d\"y\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~y~\u003c/span\u003e\u003c/span\u003e is a sequence of one or more towers such that:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003ethe first element of the sequence is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c5a1000106524b99ffb20096d04970b1?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.33ex; height:1.676ex;\" alt\u003d\"x\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~x~\u003c/span\u003e\u003c/span\u003e,\u003c/li\u003e\n\u003cli\u003ethe last element of the sequence is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0e8f621bd8562db91042eb6f9f4e6dd4?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:1.155ex; height:2.009ex;\" alt\u003d\"y\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~y~\u003c/span\u003e\u003c/span\u003e,\u003c/li\u003e\n\u003cli\u003eall elements of the sequence are \u003cstrong\u003edistinct\u003c/strong\u003e, and\u003c/li\u003e\n\u003cli\u003eeach two consecutive elements (towers) in the sequence are connected by a bridge.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eNote that by definition there is exactly one path from a tower to itself and the number of different\npaths from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;\" alt\u003d\"j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j~\u003c/span\u003e\u003c/span\u003e is the same as the number of different paths from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;\" alt\u003d\"j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eThe lead architect in charge of the design wishes for the bridges to be built such that for all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/88adc902732aff8584295cbe48110f47?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:15.552ex; height:2.509ex;\" alt\u003d\"0 \\le i,j \\le n - 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1~\u003c/span\u003e\u003c/span\u003e there are exactly \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1c3d8f7a3231a0c0da03365e25e1402?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:5.607ex; height:2.843ex;\" alt\u003d\"p[i][j]\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][j]~\u003c/span\u003e\u003c/span\u003e different paths from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;\" alt\u003d\"j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j~\u003c/span\u003e\u003c/span\u003e, where \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/8b726f7bd3d657811091517263b3ee68?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:14.039ex; height:2.843ex;\" alt\u003d\"0 \\le p[i][j] \\le 3\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le p[i][j] \\le 3~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eConstruct a set of bridges that satisfy the architect\u0027s requirements, or determine that it is impossible.\u003c/p\u003e\n\u003ch4\u003eImplementation details\u003c/h4\u003e\n\u003cp\u003eYou should implement the following procedure:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e \u003cspan class\u003d\"n\"\u003econstruct\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e(\u003c/span\u003e\u003cspan class\u003d\"n\"\u003estd\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e::\u003c/span\u003e\u003cspan class\u003d\"n\"\u003evector\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class\u003d\"n\"\u003estd\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e::\u003c/span\u003e\u003cspan class\u003d\"n\"\u003evector\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026gt;\u0026gt;\u003c/span\u003e \u003cspan class\u003d\"n\"\u003ep\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e)\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/bdc68dd29cd0d56df3a7e8bcd1b23159?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;\" alt\u003d\"p\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p~\u003c/span\u003e\u003c/span\u003e : an \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/6c28bc302db49211e263c827d73007eb?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:5.63ex; height:1.676ex;\" alt\u003d\"n \\times n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n \\times n~\u003c/span\u003e\u003c/span\u003e array representing the architect\u0027s requirements.\u003c/li\u003e\n\u003cli\u003eIf a construction is possible, this procedure should make exactly one call to \u003ccode\u003ebuild\u003c/code\u003e (see below)\nto report the construction, following which it should return \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003cli\u003eOtherwise, the procedure should return \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e without making any calls to \u003ccode\u003ebuild\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003eThis procedure is called exactly once.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eThe procedure \u003ccode\u003ebuild\u003c/code\u003e is defined as follows:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"kt\"\u003evoid\u003c/span\u003e \u003cspan class\u003d\"n\"\u003ebuild\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e(\u003c/span\u003e\u003cspan class\u003d\"n\"\u003estd\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e::\u003c/span\u003e\u003cspan class\u003d\"n\"\u003evector\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class\u003d\"n\"\u003estd\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e::\u003c/span\u003e\u003cspan class\u003d\"n\"\u003evector\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026lt;\u003c/span\u003e\u003cspan class\u003d\"kt\"\u003eint\u003c/span\u003e\u003cspan class\u003d\"o\"\u003e\u0026gt;\u0026gt;\u003c/span\u003e \u003cspan class\u003d\"n\"\u003eb\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e)\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/6e4cb09ce4221fd4aacc1a80bd343ab5?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:0.998ex; height:2.176ex;\" alt\u003d\"b\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b~\u003c/span\u003e\u003c/span\u003e : an \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/6c28bc302db49211e263c827d73007eb?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:5.63ex; height:1.676ex;\" alt\u003d\"n \\times n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n \\times n~\u003c/span\u003e\u003c/span\u003e array, with \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2ff90b4acac247a2c18e9dd228960cb0?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:9.606ex; height:2.843ex;\" alt\u003d\"b[i][j] \u003d 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b[i][j] \u003d 1~\u003c/span\u003e\u003c/span\u003e if there is a bridge connecting tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:0.802ex; height:2.176ex;\" alt\u003d\"i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~i~\u003c/span\u003e\u003c/span\u003e and tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;\" alt\u003d\"j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j~\u003c/span\u003e\u003c/span\u003e, or \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/748957f36f7d02de521807e3a00198ab?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:9.606ex; height:2.843ex;\" alt\u003d\"b[i][j] \u003d 0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b[i][j] \u003d 0~\u003c/span\u003e\u003c/span\u003e otherwise.\u003c/li\u003e\n\u003cli\u003eNote that the array must satisfy \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/b7dc824b67d04c84787b97f15ef7158a?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:13.789ex; height:2.843ex;\" alt\u003d\"b[i][j] \u003d b[j][i]\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b[i][j] \u003d b[j][i]~\u003c/span\u003e\u003c/span\u003e for all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/88adc902732aff8584295cbe48110f47?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:15.552ex; height:2.509ex;\" alt\u003d\"0 \\le i,j \\le n - 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/8cc2e7b9a5d7f3b23997966b5de5cfdd?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:9.451ex; height:2.843ex;\" alt\u003d\"b[i][i] \u003d 0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b[i][i] \u003d 0~\u003c/span\u003e\u003c/span\u003e for all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a49750dff2c898b533a2d07297b07442?v\u003d1715326211\" style\u003d\"vertical-align: -0.505ex; width:13.56ex; height:2.343ex;\" alt\u003d\"0 \\le i \\le n - 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i \\le n - 1~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eExamples\u003c/h4\u003e\n\u003ch5\u003eExample 1\u003c/h5\u003e\n\u003cp\u003eConsider the following call:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"n\"\u003econstruct\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e({{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e2\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e}})\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp\u003eThis means that there should be exactly one path from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e. For all other pairs of towers \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/08292efa8b294976382a8fc9aa3f0668?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:5.328ex; height:2.843ex;\" alt\u003d\"(x, y)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(x, y)~\u003c/span\u003e\u003c/span\u003e, such that \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0d4e741056c8abbbe044e92982a8d429?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:14.106ex; height:2.509ex;\" alt\u003d\"0 \\le x \u003c y \\le 3\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le x \u0026lt; y \\le 3~\u003c/span\u003e\u003c/span\u003e, there should be exactly two paths from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c5a1000106524b99ffb20096d04970b1?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.33ex; height:1.676ex;\" alt\u003d\"x\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~x~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0e8f621bd8562db91042eb6f9f4e6dd4?v\u003d1715326211\" style\u003d\"vertical-align: -0.671ex; width:1.155ex; height:2.009ex;\" alt\u003d\"y\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~y~\u003c/span\u003e\u003c/span\u003e.\nThis can be achieved with \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/acf1b79c1849c49564c7ac0004e5c5e3?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"4\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~4~\u003c/span\u003e\u003c/span\u003e bridges, connecting pairs of towers \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/2fb59df533b7feb8a2e6cf8b0ab0840c?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:5.168ex; height:2.843ex;\" alt\u003d\"(0, 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(0, 1)~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/4d2a0c323b47d6b47db15d21e087adfa?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:5.168ex; height:2.843ex;\" alt\u003d\"(1, 2)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1, 2)~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/68a07c8164f37661ec3ec31d6610cb5c?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:5.168ex; height:2.843ex;\" alt\u003d\"(1, 3)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1, 3)~\u003c/span\u003e\u003c/span\u003e and \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d305e08296682af8dac0f6ded2d072fa?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:5.168ex; height:2.843ex;\" alt\u003d\"(2, 3)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(2, 3)~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eTo report this solution, the \u003ccode\u003econstruct\u003c/code\u003e procedure should make the following call:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"n\"\u003ebuild\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e({{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e}})\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cdiv style\u003d\"max-width: 100%;height: 143;max-height: 143;width: 143;text-align: center;\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/2e1bfe5e329a54761334ba9fe54945af?v\u003d1715326211\" class\u003d\"tex-full\" width\u003d\"143\" height\u003d\"143\"\u003e\u003c/div\u003e\u003cp\u003eIt should then return \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eIn this case, there are multiple constructions that fit the requirements, all of which would be considered correct.\u003c/p\u003e\n\u003ch5\u003eExample 2\u003c/h5\u003e\n\u003cp\u003eConsider the following call:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"n\"\u003econstruct\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e({{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e}})\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp\u003eThis means that there should be no way to travel between the two towers. This can only be satisfied\nby having no bridges.\u003c/p\u003e\n\u003cp\u003eTherefore, the \u003ccode\u003econstruct\u003c/code\u003e procedure should make the following call:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"n\"\u003ebuild\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e({{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e0\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e}})\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp\u003eAfter which, the \u003ccode\u003econstruct\u003c/code\u003e procedure should return \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003ch5\u003eExample 3\u003c/h5\u003e\n\u003cp\u003eConsider the following call:\u003c/p\u003e\n\u003cdiv class\u003d\"codehilite\"\u003e\u003cpre\u003e\u003cspan\u003e\u003c/span\u003e\u003ccode\u003e\u003cspan class\u003d\"n\"\u003econstruct\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e({{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e3\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e},\u003c/span\u003e \u003cspan class\u003d\"p\"\u003e{\u003c/span\u003e\u003cspan class\u003d\"mi\"\u003e3\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e,\u003c/span\u003e \u003cspan class\u003d\"mi\"\u003e1\u003c/span\u003e\u003cspan class\u003d\"p\"\u003e}})\u003c/span\u003e\n\u003c/code\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp\u003eThis means that there should be exactly \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/86748ce269b76185f219ba13eeede716?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"3\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~3~\u003c/span\u003e\u003c/span\u003e paths from tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e to tower \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e. This set of requirements cannot be satisfied. As such, the \u003ccode\u003econstruct\u003c/code\u003e procedure should return \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fc9653f00347ae032c0bb3370a2c7a76?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0~\u003c/span\u003e\u003c/span\u003e without making any call to \u003ccode\u003ebuild\u003c/code\u003e.\u003c/p\u003e\n\u003ch4\u003eConstraints\u003c/h4\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/f34539f4f086955b2e4ec504f653728a?v\u003d1715326211\" style\u003d\"vertical-align: -0.505ex; width:13.404ex; height:2.343ex;\" alt\u003d\"1 \\le n \\le 1000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le n \\le 1000~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d841be0bfec8b703ac917f36049242d5?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:9.712ex; height:2.843ex;\" alt\u003d\"p[i][i] \u003d 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][i] \u003d 1~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/b5356fe04df81817d8b04e5e095207ae?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:14.464ex; height:2.843ex;\" alt\u003d\"0 \\le i \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b672e339efe0ca0680e2163ebafde65?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:14.223ex; height:2.843ex;\" alt\u003d\"p[i][j] \u003d p[j][i]\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][j] \u003d p[j][i]~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/8b726f7bd3d657811091517263b3ee68?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:14.039ex; height:2.843ex;\" alt\u003d\"0 \\le p[i][j] \\le 3\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le p[i][j] \\le 3~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eSubtasks\u003c/h4\u003e\n\u003col\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d6c8ed0de560f88fa572eb1ec2aca1c6?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"11\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~11~\u003c/span\u003e\u003c/span\u003e points) \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/319b02c2044cd0fd385868b30f836634?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:9.868ex; height:2.843ex;\" alt\u003d\"p[i][j] \u003d 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][j] \u003d 1~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e604467303f21c656febff5848d33242?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"10\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~10~\u003c/span\u003e\u003c/span\u003e points) \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/ec37c2ac8499f8752d46fd07f229094b?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:9.868ex; height:2.843ex;\" alt\u003d\"p[i][j] \u003d 0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][j] \u003d 0~\u003c/span\u003e\u003c/span\u003e or \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d9f5035dae02b1fc71150971d60eea9e?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"19\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~19~\u003c/span\u003e\u003c/span\u003e points) \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/ec37c2ac8499f8752d46fd07f229094b?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:9.868ex; height:2.843ex;\" alt\u003d\"p[i][j] \u003d 0\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][j] \u003d 0~\u003c/span\u003e\u003c/span\u003e or \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/edff4a53ceab26bbeb9fa3434bd9765d?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/acc9517e85edbf84a55226363bf47ae5?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"35\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~35~\u003c/span\u003e\u003c/span\u003e points) \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5d658512a57deac8e50453cf525cdc1d?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:14.039ex; height:2.843ex;\" alt\u003d\"0 \\le p[i][j] \\le 2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le p[i][j] \\le 2~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e and there is at least one construction satisfying the requirements.\u003c/li\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e7e23e2a77ce09fa69c1b5a18aa20861?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:2.325ex; height:2.176ex;\" alt\u003d\"21\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~21~\u003c/span\u003e\u003c/span\u003e points) \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5d658512a57deac8e50453cf525cdc1d?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:14.039ex; height:2.843ex;\" alt\u003d\"0 \\le p[i][j] \\le 2\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le p[i][j] \\le 2~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30771f8224df93c58eb0e7c026a1c1fe?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:0.905ex; height:2.843ex;\" alt\u003d\"(\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(~\u003c/span\u003e\u003c/span\u003efor all \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/34c623aeea98a815385d5b30e95e10a7?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:16.456ex; height:2.843ex;\" alt\u003d\"0 \\le i,j \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~0 \\le i,j \\le n - 1)~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003e(\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/acf1b79c1849c49564c7ac0004e5c5e3?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"4\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~4~\u003c/span\u003e\u003c/span\u003e points) No additional constraints.\u003c/li\u003e\n\u003c/ol\u003e\n\u003ch4\u003eSample grader\u003c/h4\u003e\n\u003cp\u003eThe sample grader reads the input in the following format:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eline \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e: \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c1a0bc43a3139849dd28538746a21e7e?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.395ex; height:1.676ex;\" alt\u003d\"n\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~n~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003cli\u003eline \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dd6a26d205d1ff5b8c800dba21ce18af?v\u003d1715326211\" style\u003d\"vertical-align: -0.505ex; width:4.805ex; height:2.343ex;\" alt\u003d\"2 + i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 + i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/69db2a1004b4a30d4e34c524ec7b8034?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:15.369ex; height:2.843ex;\" alt\u003d\"(0 \\le i \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(0 \\le i \\le n - 1)~\u003c/span\u003e\u003c/span\u003e: \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/02f6a0287d8277f86a39e1d9fd37dbdc?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; margin-left: -0.089ex; width:26.729ex; height:2.843ex;\" alt\u003d\"p[i][0] \\ p[i][1] \\ \\dots \\ p[i][n - 1]\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~p[i][0] \\ p[i][1] \\ \\dots \\ p[i][n - 1]~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eThe output of the sample grader is in the following format:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eline \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e: the return value of \u003ccode\u003econstruct\u003c/code\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eIf the return value of \u003ccode\u003econstruct\u003c/code\u003e is \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dc15aebf4fa2f4039e7e91a157d4b279?v\u003d1715326211\" style\u003d\"vertical-align: -0.338ex; width:1.162ex; height:2.176ex;\" alt\u003d\"1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1~\u003c/span\u003e\u003c/span\u003e, the sample grader additionally prints:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eline \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/dd6a26d205d1ff5b8c800dba21ce18af?v\u003d1715326211\" style\u003d\"vertical-align: -0.505ex; width:4.805ex; height:2.343ex;\" alt\u003d\"2 + i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 + i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/69db2a1004b4a30d4e34c524ec7b8034?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:15.369ex; height:2.843ex;\" alt\u003d\"(0 \\le i \\le n - 1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(0 \\le i \\le n - 1)~\u003c/span\u003e\u003c/span\u003e: \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/cf0cc731f90adac7bfee4a1e56e45a61?v\u003d1715326211\" style\u003d\"vertical-align: -0.838ex; width:26.124ex; height:2.843ex;\" alt\u003d\"b[i][0] \\ b[i][1] \\ \\dots \\ b[i][n - 1]\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~b[i][0] \\ b[i][1] \\ \\dots \\ b[i][n - 1]~\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}