{"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\u003ch5\u003eJOI Open Contest\u003c/h5\u003e\n\u003cp\u003eThe JOI Co., Ltd. has \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e servers in total around the world. Each server contains an important piece of information.\nDifferent servers contain different pieces of information. The JOI Co., Ltd. is now building digital lines\nbetween the servers so that the pieces of information will be shared with the servers. When a line is built between\ntwo servers, pieces of information can be exchanged between them. It is possible to exchange pieces of\ninformation from one server to another server which is reachable through the lines which are already built.\u003c/p\u003e\n\u003cp\u003eEach server has a high-performance synchronization system. When two servers can exchange pieces of information\neach other and they contain different pieces of information, they automatically synchronize the pieces\nof information. After a synchronization between the server A and the server B, both of the servers A and B\nwill contain all the pieces of information which are contained in at least one of the servers A and B before the\nsynchronization.\u003c/p\u003e\n\u003cp\u003eIn order to reduce the cost, only \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fd8b3536ed085708a0178c8e31f8cf22?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:6.066ex; 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 lines can be built. After the \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fd8b3536ed085708a0178c8e31f8cf22?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:6.066ex; 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 lines are built, there will be a unique\nroute to exchange pieces of information from one server to another server without passing through the same server\nmore than once.\u003c/p\u003e\n\u003cp\u003eIn the beginning (at time 0), no lines are built. Sometimes, lines are built in a harsh condition (e.g. in a desert,\nin the bottom of sea). Some of the lines become unavailable at some point. Once a line becomes unavailable, it is\nnot possible to use it until it is rebuilt.\u003c/p\u003e\n\u003cp\u003eIt is known that, at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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 \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/ddb53056bcf2d2f88b5ea75fad8f1589?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.569ex; height:2.843ex;\" alt\u003d\"(1 \\le j \\le M)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le j \\le M)~\u003c/span\u003e\u003c/span\u003e, the state of exactly one line is changed.\u003c/p\u003e\n\u003cp\u003eWe need to know the number of different pieces of information contained in some of the servers at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/da94590309ccdc0266c50b9d42ccd65a?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:6.445ex; height:2.343ex;\" alt\u003d\"M+1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M+1~\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003ch4\u003eTask\u003c/h4\u003e\n\u003cp\u003eWrite a program which, given information of the lines to be built and the state of the lines, determine the number\nof different pieces of information contained in some of the servers.\u003c/p\u003e\n\u003ch4\u003eInput Specification\u003c/h4\u003e\n\u003cp\u003eRead the following data from the standard input.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eThe first line of input contains three space separated integers \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/09364895aecdedfd8cb6f510534a1e89?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.442ex; height:2.176ex;\" alt\u003d\"M\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d8d5cff7eb1238d9dec4f7a0a8e840be?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:1.838ex; height:2.509ex;\" alt\u003d\"Q\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Q~\u003c/span\u003e\u003c/span\u003e. This means the number of the servers\nis \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/7b60d7c68d7ec066966b2e5a535229a8?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.064ex; height:2.176ex;\" alt\u003d\"N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~N~\u003c/span\u003e\u003c/span\u003e, a list of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/09364895aecdedfd8cb6f510534a1e89?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.442ex; height:2.176ex;\" alt\u003d\"M\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M~\u003c/span\u003e\u003c/span\u003e changes of the state of the lines is given, and we need to know the number of different pieces of information contained in \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d8d5cff7eb1238d9dec4f7a0a8e840be?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:1.838ex; height:2.509ex;\" alt\u003d\"Q\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Q~\u003c/span\u003e\u003c/span\u003e servers.\u003c/li\u003e\n\u003cli\u003eThe \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1714994085\" 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-th line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a97245ad4b692abd23ee89bb3aa91fb5?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:16.038ex; height:2.843ex;\" alt\u003d\"(1 \\le i \\le N-1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le i \\le N-1)~\u003c/span\u003e\u003c/span\u003e of the following \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/fd8b3536ed085708a0178c8e31f8cf22?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:6.066ex; 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 lines contains space separated integers \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/475abba72d03900b30bb3dd5d0edf189?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.724ex; height:2.509ex;\" alt\u003d\"X_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~X_i~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9fe5b345f0f5a8dfae221ee9283d88aa?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.15ex; height:2.509ex;\" alt\u003d\"Y_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Y_i~\u003c/span\u003e\u003c/span\u003e. This means the line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1714994085\" 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, when it is built, connects the server \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/475abba72d03900b30bb3dd5d0edf189?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.724ex; height:2.509ex;\" alt\u003d\"X_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~X_i~\u003c/span\u003e\u003c/span\u003e and the server \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/9fe5b345f0f5a8dfae221ee9283d88aa?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.15ex; height:2.509ex;\" alt\u003d\"Y_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Y_i~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003cli\u003eThe \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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-th line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/ddb53056bcf2d2f88b5ea75fad8f1589?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.569ex; height:2.843ex;\" alt\u003d\"(1 \\le j \\le M)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le j \\le M)~\u003c/span\u003e\u003c/span\u003e of the following \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/09364895aecdedfd8cb6f510534a1e89?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:2.442ex; height:2.176ex;\" alt\u003d\"M\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~M~\u003c/span\u003e\u003c/span\u003e lines contains an integer \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e40469023679c142dae9a33554fd770c?v\u003d1714994085\" style\u003d\"vertical-align: -1.005ex; width:2.834ex; height:2.843ex;\" alt\u003d\"D_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~D_j~\u003c/span\u003e\u003c/span\u003e. This means the state of the line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e40469023679c142dae9a33554fd770c?v\u003d1714994085\" style\u003d\"vertical-align: -1.005ex; width:2.834ex; height:2.843ex;\" alt\u003d\"D_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~D_j~\u003c/span\u003e\u003c/span\u003e is changed at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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. Namely, if the line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e40469023679c142dae9a33554fd770c?v\u003d1714994085\" style\u003d\"vertical-align: -1.005ex; width:2.834ex; height:2.843ex;\" alt\u003d\"D_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~D_j~\u003c/span\u003e\u003c/span\u003e is unavailable just before time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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, this line is built at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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. If the line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/e40469023679c142dae9a33554fd770c?v\u003d1714994085\" style\u003d\"vertical-align: -1.005ex; width:2.834ex; height:2.843ex;\" alt\u003d\"D_j\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~D_j~\u003c/span\u003e\u003c/span\u003e is available just before time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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, this line becomes unavailable at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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. When the state is changed at time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d1ce794193cf0a31252546069ac934df?v\u003d1714994085\" 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, all the synchronization processes will be finished before time \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/31fabccf5e445633c9474172390be65f?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;\" alt\u003d\"j+1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~j+1~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003cli\u003eThe \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:1.211ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~k~\u003c/span\u003e\u003c/span\u003e-th line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/23f6cd27ae7cfcb6cbcc22121fb37463?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.218ex; height:2.843ex;\" alt\u003d\"(1 \\le k \\le Q)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le k \\le Q)~\u003c/span\u003e\u003c/span\u003e of the following \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d8d5cff7eb1238d9dec4f7a0a8e840be?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:1.838ex; height:2.509ex;\" alt\u003d\"Q\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Q~\u003c/span\u003e\u003c/span\u003e lines contains an integer \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c94abedd250c208eaffa5f8a3e3374f8?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.751ex; height:2.509ex;\" alt\u003d\"C_k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~C_k~\u003c/span\u003e\u003c/span\u003e. This means we need to know the number of different pieces of information contained in the server \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c94abedd250c208eaffa5f8a3e3374f8?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.751ex; height:2.509ex;\" alt\u003d\"C_k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~C_k~\u003c/span\u003e\u003c/span\u003e in the end.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eOutput Specification\u003c/h4\u003e\n\u003cp\u003eWrite \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/d8d5cff7eb1238d9dec4f7a0a8e840be?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:1.838ex; height:2.509ex;\" alt\u003d\"Q\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Q~\u003c/span\u003e\u003c/span\u003e lines to the standard output. The \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/58614bc17dddddc4e51be1b63b3ce5ef?v\u003d1714994085\" style\u003d\"vertical-align: -0.338ex; width:1.211ex; height:2.176ex;\" alt\u003d\"k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~k~\u003c/span\u003e\u003c/span\u003e-th line \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/23f6cd27ae7cfcb6cbcc22121fb37463?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.218ex; height:2.843ex;\" alt\u003d\"(1 \\le k \\le Q)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le k \\le Q)~\u003c/span\u003e\u003c/span\u003e should contain an integer, the number of different pieces of information contained in the server \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c94abedd250c208eaffa5f8a3e3374f8?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.751ex; height:2.509ex;\" alt\u003d\"C_k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~C_k~\u003c/span\u003e\u003c/span\u003e in the end.\u003c/p\u003e\n\u003ch4\u003eConstraints\u003c/h4\u003e\n\u003cp\u003eAll input data satisfy the following conditions.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/aa047a33cd29ef1943c7e6c8304a55a0?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:16.785ex; height:2.343ex;\" alt\u003d\"2 \\le N \\le 100\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~2 \\le N \\le 100\\,000~\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/b955ea3d3ba97f893fb9a05e841ea02a?v\u003d1714994085\" style\u003d\"vertical-align: -0.505ex; width:17.164ex; height:2.343ex;\" alt\u003d\"1 \\le M \\le 200\\,000\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le M \\le 200\\,000~\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/ee8ce7b881c02090a730f313f4dba68e?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:11.262ex; height:2.509ex;\" alt\u003d\"1 \\le Q \\le N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le Q \\le N~\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/ff758f17194af125a587de8fc54c5fb4?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:12.147ex; height:2.509ex;\" alt\u003d\"1 \\le X_i \\le N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le X_i \\le N~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/0705e466120b56704daf8cedae407554?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:11.573ex; height:2.509ex;\" alt\u003d\"1 \\le Y_i \\le N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le Y_i \\le N~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/716edfaaa4c43b61c11ff389c2c05bd1?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:7.973ex; height:2.676ex;\" alt\u003d\"X_i \\ne Y_i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~X_i \\ne Y_i~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a97245ad4b692abd23ee89bb3aa91fb5?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:16.038ex; height:2.843ex;\" alt\u003d\"(1 \\le i \\le N-1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\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/54943458b3317c8be0da95c7fa31dd64?v\u003d1714994085\" style\u003d\"vertical-align: -1.005ex; width:16.26ex; height:2.843ex;\" alt\u003d\"1 \\le D_j \\le N-1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le D_j \\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/ddb53056bcf2d2f88b5ea75fad8f1589?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.569ex; height:2.843ex;\" alt\u003d\"(1 \\le j \\le M)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le j \\le M)~\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/d899f4143e1ad6638a61bbf642d78e92?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:12.174ex; height:2.509ex;\" alt\u003d\"1 \\le C_k \\le N\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~1 \\le C_k \\le N~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/23f6cd27ae7cfcb6cbcc22121fb37463?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:12.218ex; height:2.843ex;\" alt\u003d\"(1 \\le k \\le Q)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le k \\le Q)~\u003c/span\u003e\u003c/span\u003e.\u003c/li\u003e\n\u003cli\u003eThe values of \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/c94abedd250c208eaffa5f8a3e3374f8?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:2.751ex; height:2.509ex;\" alt\u003d\"C_k\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~C_k~\u003c/span\u003e\u003c/span\u003e are distinct.\u003c/li\u003e\n\u003cli\u003eIf all of the lines are built, there will be a route from one server to another server through the lines.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch4\u003eSubtasks\u003c/h4\u003e\n\u003ch5\u003eSubtask 1 [30 points]\u003c/h5\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/5f78d011064b348854aea87c677e5ec5?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:6.099ex; height:2.509ex;\" alt\u003d\"Q \u003d 1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Q \u003d 1~\u003c/span\u003e\u003c/span\u003e is satisfied.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch5\u003eSubtask 2 [30 points]\u003c/h5\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/66476cc9a24aeaea67bced49cac1f208?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:6.625ex; height:2.509ex;\" alt\u003d\"X_i \u003d i\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~X_i \u003d i~\u003c/span\u003e\u003c/span\u003e, \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/4fc4de2854e3a464051876e28b09698a?v\u003d1714994085\" style\u003d\"vertical-align: -0.671ex; width:10.054ex; height:2.509ex;\" alt\u003d\"Y_i \u003d i+1\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~Y_i \u003d i+1~\u003c/span\u003e\u003c/span\u003e \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a97245ad4b692abd23ee89bb3aa91fb5?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:16.038ex; height:2.843ex;\" alt\u003d\"(1 \\le i \\le N-1)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le i \\le N-1)~\u003c/span\u003e\u003c/span\u003e are satisfied.\u003c/li\u003e\n\u003c/ul\u003e\n\u003ch5\u003eSubtask 3 [40 points]\u003c/h5\u003e\n\u003cp\u003eNo additional constraints.\u003c/p\u003e\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 6 3\n1 2\n1 3\n2 4\n2 5\n1\n2\n1\n4\n4\n3\n1\n4\n5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n5\n4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003ch4\u003eExplanation for Sample\u003c/h4\u003e\n\u003cp\u003eIn the beginning, we assume the server \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1714994085\" 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 \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/30c786c35a4838a6f239f70b39139b93?v\u003d1714994085\" style\u003d\"vertical-align: -0.838ex; width:11.134ex; height:2.843ex;\" alt\u003d\"(1 \\le i \\le 5)\"\u003e\u003cspan class\u003d\"tex-text\" style\u003d\"display:none;\"\u003e~(1 \\le i \\le 5)~\u003c/span\u003e\u003c/span\u003e contains the piece \u003cspan class\u003d\"inline-math\"\u003e\u003cimg class\u003d\"tex-image\" src\u003d\"CDN_BASE_URL/a4e1016e68b8319096078a41bff14fe0?v\u003d1714994085\" 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 of information.\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003eAt time 1, the line 1 is built and the servers 1, 2 become connected. Then, both of the servers 1, 2 contain the pieces 1, 2 of information.\u003c/li\u003e\n\u003cli\u003eAt time 2, the line 2 is built, and the server 1, 3 become connected. Including the line 1, the servers 1, 2, 3 are connected. The servers 1, 2, 3 contain the pieces 1, 2, 3 of information.\u003c/li\u003e\n\u003cli\u003eAt time 3, the line 1 becomes unavailable because it was available just before this moment.\u003c/li\u003e\n\u003cli\u003eAt time 4, the line 4 is built and the servers 2, 5 become connected. Both of the servers 2, 5 contain the pieces 1, 2, 3, 5 of information. Note that the servers 1, 2 can not exchange pieces of information each other because the line 1 became unavailable.\u003c/li\u003e\n\u003cli\u003eAt time 5, the line 4 becomes unavailable.\u003c/li\u003e\n\u003cli\u003eAt time 6, the line 3 is built and the servers 2, 4 become connected. Then, both of the servers 2, 4 contain the pieces 1, 2, 3, 4, 5 of information.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003eAs explained above, in the end, the servers 1, 4, 5 have 3, 5, 4 different pieces of information, respectively.\u003c/p\u003e\n\u003c/div\u003e\n\u003chr\u003e\n\n\u003c/div\u003e"}}]}