{"trustable":true,"prependHtml":"\u003cstyle\u003e.statText pre { font-size: 12px; }\ntable {display:block !important; width:100%; }\ntable tbody {display:block !important; width:100%; }\ntable tbody tr { width:100% !important;display: block;}\ntable tbody tr td.statText { margin-left: 5px; display: inline-block; width: fit-content; }\ntable tbody tr td.statText br { display: block; content: \" \";line-height: 12px;margin: 12px 0;}\ntable tbody tr td.statText table table pre {\n white-space: pre-wrap;\n text-overflow: ellipsis;\n word-break: break-all;\n}\ntd { padding: 0 !important; border: none !important; }\npre { line-height: normal; margin: 0; }\n\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\n \n \t\t\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eProblem Statement\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cp\u003e\nYou are given an undirected graph with \u003cb\u003en\u003c/b\u003e nodes and m edges.\nThe nodes are numbered 0 through \u003cb\u003en\u003c/b\u003e-1.\nThe edges are given in the int[]s \u003cb\u003ea\u003c/b\u003e and \u003cb\u003eb\u003c/b\u003e: for each valid index i, there is an edge between \u003cb\u003ea\u003c/b\u003e[i] and \u003cb\u003eb\u003c/b\u003e[i].\nThis graph may have self-loops or multiple edges.\n\u003c/p\u003e\n\u003cp\u003e\nLet f(k) denote the number of ways to choose a subset of exactly k edges so the graph consisting of all \u003cb\u003en\u003c/b\u003e nodes and the edges you selected is connected.\nLet g(k) \u003d f(k) modulo (10^9 + 7).\n\u003c/p\u003e\n\u003cp\u003e\nReturn a int[] with exactly m-\u003cb\u003en\u003c/b\u003e+2 elements.\nFor each i starting from 0, element i of the return value should be g(i+\u003cb\u003en\u003c/b\u003e-1).\n\u003c/p\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eDefinition\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eClass:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eSpanningSubgraphs\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eMethod:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003ecount\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eParameters:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eint, int[], int[]\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eReturns:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eint[]\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003eMethod signature:\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eint[] count(int n, int[] a, int[] b)\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e(be sure your method is public)\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eConstraints\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cb\u003en\u003c/b\u003e will be between 1 and 15, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003em will be between \u003cb\u003en\u003c/b\u003e-1 and 200, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003cb\u003ea\u003c/b\u003e and \u003cb\u003eb\u003c/b\u003e will contain exactly m elements each.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" valign\u003d\"top\" class\u003d\"statText\"\u003e-\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003eEach element of \u003cb\u003ea\u003c/b\u003e and \u003cb\u003eb\u003c/b\u003e will be between 0 and \u003cb\u003en\u003c/b\u003e-1, inclusive.\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u0026nbsp;\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003ch3\u003eExamples\u003c/h3\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e0)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e3\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{0,1,2}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{1,2,0}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: {3, 1 }\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eThis case is a triangle graph. For k\u003d2, we can choose any subset of 2 edges, for a total of 3 choices. For k\u003d3, we only have one way (choosing all edges).\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e1)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{0,1,4,3}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{0,1,4,3}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: {0 }\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003eEven though m is at least \u003cb\u003en\u003c/b\u003e-1, the graph you are given is not necessarily connected.\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e2)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{0,1,1,2,2,2,3,3,4}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{1,2,3,3,4,5,4,5,5}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: {40, 48, 27, 8, 1 }\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd align\u003d\"center\" nowrap\u003d\"true\" class\u003d\"statText\"\u003e3)\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003c/td\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e15\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{7,3,8,2,5,8,5,11,8,3,10,8,6,6,8,8,3,9,4,6,4,6,1,1,5,4,\n0,9,4,7,6,0,6,2,2,6,11,4,6,10,9,2,6,0,4,7,6,8,1,3,11,3,\n4,8,1,0,12,9,5,14,0,13,7,14,7,9,6,7,8,8,8,4,14,1,13,5,\n1,6,13,14,0,4,8,5,13,7,2,10,10,11,8,2,4,13,12,10,5,13,\n5,9,6,4,1,11,4,13,6,4,8,8,11,1,14,10,3,1,2,0,10,5,9,5,\n10,8,4,2,5,12,7,2,3,2,4,6,9,3,7,9,2,14,14,0,14,3,12,12,\n0,11,7,8,6,6,0,10,7,2,0,7,8,10,3,11,11,7,0,0,11,8,6,11,\n13,4,11,11,8,5,13,11,9,14,10,1,12,12,3,3,0,13,13,6,2,9,\n1,4,2,7,14,5}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003e{12,8,1,11,1,6,12,3,7,5,1,1,11,11,9,0,7,9,12,8,13,13,11,\n0,2,14,12,12,13,10,13,12,2,14,11,13,14,3,12,14,11,5,3,0,\n9,0,1,10,5,11,6,6,1,4,0,12,13,1,4,10,9,8,3,4,13,3,10,7,\n3,2,13,0,1,13,7,3,3,9,9,10,9,9,0,13,12,3,14,4,1,7,5,0,0,\n11,13,0,0,14,13,5,5,0,10,0,3,8,13,4,6,7,4,0,6,7,8,10,7,\n4,6,13,0,6,3,2,11,8,7,12,0,14,12,6,10,8,6,9,2,4,14,9,4,\n6,3,11,12,8,7,12,14,0,10,11,9,7,4,6,12,13,7,4,13,9,7,13,\n2,4,7,6,2,0,10,7,8,13,1,14,13,3,12,14,2,4,6,7,10,11,8,4,\n10,13,14,9,0,5,3,0,7,11}\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003cpre\u003eReturns: \n{165676111, 472152904, 401323420, 92841577, 361806106, 251066093, 860026758, 204774808, 800204699, 78217142, 290847617, 377659363, 799299488, 639266686, 463155556, 542289798, 505455263, 931966095, 332452321, 157494446, 701362585, 4372546, 189983818, 137009880, 456907012, 699388046, 492757156, 402334178, 262521060, 683669243, 218329042, 912344074, 469164876, 951780423, 845657616, 358560958, 877409160, 936645440, 506542339, 711561307, 182417811, 411559656, 609363889, 410499565, 523968597, 808436626, 796861282, 799905851, 332114660, 28142829, 832046308, 515892527, 461122988, 459763203, 639481498, 760842951, 53778152, 531539556, 499281391, 756160187, 408189379, 536177501, 236162240, 932086574, 249801471, 691291871, 305954956, 944526707, 689056121, 509929491, 860012851, 270237338, 530915439, 636690481, 284974622, 213167754, 791793494, 581854637, 515718421, 142304792, 170068497, 175763828, 669814256, 87330307, 657451539, 902803718, 994244944, 710593682, 158314930, 728217704, 428356628, 680806591, 426349961, 578797504, 448716917, 937968991, 727251530, 565010419, 762565871, 373908747, 569188731, 954967822, 83820159, 869337563, 549355611, 927598978, 992408503, 670497964, 348959921, 892858049, 328944072, 946559373, 830835081, 805632932, 389521576, 995252131, 717245242, 882920285, 127735960, 774020953, 299323686, 248711270, 707972648, 824068405, 929290955, 262377161, 603969848, 20319782, 655428762, 772441022, 315946694, 773490199, 63054183, 280718941, 320481045, 714052434, 119312921, 334810041, 844617606, 239955633, 647743078, 159621066, 358764917, 571545322, 29056136, 300270686, 822798951, 841318305, 809733973, 849084831, 542304340, 360014205, 268267900, 461637720, 441483501, 500466014, 722102413, 274028790, 889071123, 456597703, 989359978, 781914152, 339994675, 176509460, 71482668, 940949411, 727100238, 343026545, 279293690, 51741525, 759652847, 198027784, 293410546, 430593193, 339024072, 605239373, 602353448, 433606430, 526225238, 410141720, 62117055, 1274196, 19503, 198, 1 }\u003c/pre\u003e\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"statText\"\u003e\u003ctable\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd colspan\u003d\"2\" class\u003d\"statText\"\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003chr\u003e\u003cp\u003eThis problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved. \u003c/p\u003e\n \n "}}]}