CT30280

The Separate Camps of Luminar

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the crystal caves of Luminar as Brewer unrolls the day's manifest of tunnels. The tally will decide the next shipment. Task: An undirected graph has n nodes and m edges. Print the number of connected components. Input format: First line: n and m. Next m lines: u v. Output format: Print the component count. Constraints: 1 <= n <= 947; 0 <= m <= 1894; 1 <= u,v <= n.

Example 1:

Input: 688 1680 50 259 74 76 14 15 187 688 19 564 327 594 204 290 247 306 584 633 459 614 410 632 61 675 105 369 155 643 119 504 349 613 351 684 357 410 319 569 99 599 68 375 137 621 412 560 282 403 114 685 282 366 419 550 203 629 4 146 472 609 10 517 13 389 92 221 12 35 195 329 151 182 106 299 104 369 28 682 259 288 461 525 274 430 223 535 174 553 43 400 172 408 322 334 154 595 314 363 329 500 465 618 307 634 311 434 352 455 294 307 224 529 124 151 171 365 135 453 43 635 133 141 466 498 20 488 65 319 242 511 271 501 96 320 44 524 323 636 303 613 274 431 372 411 109 421 76 157 56 565 374 407 8 562 315 530 479 498 192 245 67 390 129 215 264 678 67 620 79 225 58 436 338 577 319 461 416 437 65 686 11 55 425 548 301 409 452 456 196 485 150 649 130 578 283 590 284 439 497 555 92 655 565 648 209 479 396 511 165 201 48 464 133 416 19 511 126 657 209 240 125 361 346 366 338 361 240 369 19 572 125 497 191 644 22 117 197 653 171 376 34 684 120 397 549 562 125 610 239 508 80 121 172 370 15 468 169 476 132 235 483 596 237 297 21 621 97 267 156 393 35 557 308 508 64 338 52 653 194 506 50 431 184 308 677 679 327 469 1 266 1 471 101 165 308 540 559 629 611 663 22 669 611 682 66 518 130 251 23 599 274 544 119 607 41 208 152 367 357 543 314 341 375 622 250 381 28 150 129 196 268 307 313 426 250 636 22 212 531 553 160 622 120 260 182 323 305 638 397 477 257 505 58 162 79 172 81 101 39 150 189 486 15 562 97 315 436 649 265 513 13 37 90 475 454 471 337 631 20 473 561 569 58 142 480 542 114 640 301 565 496 600 46 365 545 607 286 308 559 640 212 642 484 557 166 645 91 420 418 631 170 389 130 483 472 513 474 603 71 141 66 382 91 152 259 597 123 258 521 608 91 389 334 464 132 250 523 526 39 165 96 475 359 416 118 454 13 632 102 198 11 629 334 526 568 606 450 464 85 267 260 625 318 348 215 280 125 178 27 194 360 415 169 365 343 474 75 479 463 622 80 622 226 662 388 589 518 650 215 490 193 413 598 618 90 264 365 468 487 533 460 472 284 475 214 636 26 251 141 160 82 443 65 274 106 220 217 628 34 545 199 498 421 500 601 684 103 403 409 663 70 72 47 540 306 397 302 658 77 423 107 191 102 470 65 336 330 686 389 424 224 652 57 392 16 395 553 673 491 579 178 673 378 623 298 395 511 675 262 461 116 563 305 527 94 510 53 357 452 687 30 284 500 679 272 423 96 639 406 675 131 277 102 672 43 91 3 393 108 380 20 274 295 657 121 544 253 337 468 531 104 444 344 454 304 343 85 390 343 467 617 640 98 534 373 612 291 526 84 481 150 460 272 350 453 549 476 652 275 640 67 488 139 505 387 483 316 595 210 405 227 516 283 369 468 659 47 256 64 159 141 223 3 348 155 438 191 656 99 205 22 248 415 550 166 243 267 358 575 628 161 221 497 528 158 189 364 603 575 664 175 585 654 674 29 536 460 579 467 635 82 158 46 47 56 283 641 653 513 673 65 540 296 451 392 683 596 632 221 405 236 493 18 22 31 635 90 257 51 394 489 513 625 650 171 500 93 349 480 637 149 242 33 310 438 633 180 540 58 518 15 334 273 303 22 321 518 659 57 143 402 453 268 314 378 406 64 624 290 446 244 393 342 523 357 651 346 623 446 459 140 584 118 415 7 527 37 684 325 683 144 289 131 353 233 386 159 210 616 621 411 496 29 614 85 649 220 609 592 622 180 335 227 406 250 303 110 579 423 480 142 658 192 510 122 507 384 626 97 574 16 330 40 529 319 453 181 434 261 621 74 216 77 215 76 479 165 343 358 534 64 110 258 319 128 240 320 375 24 375 51 627 117 219 59 564 359 418 84 519 166 618 410 478 474 517 332 450 92 470 319 555 200 463 124 197 124 377 83 657 259 330 251 568 245 485 6 107 227 440 70 636 12 475 453 617 9 429 487 644 41 491 351 625 23 603 204 493 46 417 105 356 377 564 53 86 13 129 569 661 111 657 410 627 265 637 449 598 374 378 204 510 361 539 388 523 2 487 161 581 189 581 43 339 284 306 445 453 43 512 312 653 349 483 266 541 129 482 120 131 356 517 50 107 482 615 86 154 278 538 19 93 125 656 22 28 280 486 482 681 310 422 296 597 63 260 573 593 88 134 323 419 39 83 272 362 188 622 424 571 40 599 140 501 519 535 234 370 384 530 26 272 93 178 54 638 11 676 41 641 229 568 429 534 503 669 42 589 146 586 473 662 86 663 40 622 111 430 122 219 362 629 100 623 162 668 444 669 419 576 52 107 159 596 99 421 229 645 327 358 111 503 313 338 110 642 565 622 138 643 8 552 470 556 221 527 477 490 111 617 74 460 302 670 8 82 110 366 69 382 319 338 305 662 121 140 294 548 176 289 235 557 221 518 3 133 83 293 537 562 195 631 157 432 119 393 353 489 303 522 1 509 192 609 156 217 322 336 335 608 157 171 220 225 184 493 78 191 656 670 291 391 45 277 297 473 576 686 605 615 458 677 514 663 17 563 558 573 31 498 513 530 79 503 131 188 301 388 72 547 53 475 334 462 373 444 271 533 19 594 88 231 413 642 379 558 61 251 249 564 341 350 35 214 82 464 227 653 43 221 416 614 248 489 46 95 78 112 237 640 60 430 278 378 250 641 261 554 528 574 387 593 162 448 357 579 126 591 105 124 116 212 62 593 532 680 173 175 348 540 114 488 405 514 302 469 439 505 82 605 310 436 130 409 247 633 469 596 144 521 336 560 195 656 404 667 140 359 435 656 301 543 123 129 13 546 46 416 102 118 455 618 26 501 270 417 310 572 179 584 231 565 610 655 266 383 208 226 206 584 54 231 166 463 10 267 483 549 100 411 153 378 388 465 201 272 461 609 27 449 106 509 69 439 585 629 119 151 278 575 92 471 554 570 64 426 215 569 153 346 62 172 200 456 372 584 44 55 196 502 484 535 539 672 230 366 259 581 205 258 271 430 11 104 345 623 117 159 31 445 451 534 172 258 446 537 227 509 185 569 150 477 166 601 293 608 145 337 455 527 490 562 327 636 143 341 46 369 93 208 245 669 466 471 251 559 337 621 119 480 559 648 57 292 42 297 121 667 122 133 191 684 558 634 35 216 192 656 231 598 239 303 4 110 140 511 105 604 108 659 87 442 330 383 338 482 618 636 362 543 400 678 611 631 434 493 36 462 400 493 260 688 31 565 280 668 100 594 205 456 303 513 9 313 352 502 116 581 12 517 173 360 363 546 156 272 537 587 114 208 388 629 304 380 90 583 78 468 420 574 61 146 236 582 235 421 393 484 464 494 327 598 47 201 201 264 273 676 120 436 297 414 147 197 620 621 98 162 279 297 19 657 152 274 13 562 574 649 53 472 249 541 179 300 447 509 566 612 502 676 544 674 87 458 327 452 47 154 228 487 379 542 261 578 206 276 22 532 412 479 188 315 175 568 462 531 149 488 445 658 613 626 624 675 488 624 411 577 294 584 256 556 266 493 311 492 467 564 317 500 189 659 331 386 472 630 201 401 132 666 102 630 397 435 587 611 439 634 158 221 67 136 333 506 173 243 141 519 147 483 34 544 209 310 152 590 155 177 390 655 540 548 434 546 578 616 84 182 1 239 420 522 12 389 51 395 145 495 241 484 135 557 209 219 100 430 327 615 410 533 185 645 9 35 137 687 247 496 64 678 388 497 253 551 10 26 62 524 99 633 446 680 654 664 311 540 239 506 318 643 428 686 281 305 553 580 252 438 26 186 38 256 128 576 155 352 339 525 161 501 35 313 342 548 326 565 297 438 310 535 307 500 489 508 294 538 463 557 275 448 141 171 132 412 678 688 163 339 76 549 132 272 531 614 386 477 117 273 17 372 270 567 382 615 648 670 153 648 198 551 27 437 300 319 419 644 169 584 322 325 77 471 171 563 659 661 462 488 102 121 5 35 495 552 375 453 494 629 148 207 263 466 3 340 227 667 83 138 244 576 150 487 319 355 94 268 341 497 290 328 320 675 107 514 5 645 37 146 297 668 150 634 39 647 76 152 87 457 127 639 363 406 265 443 451 622 1 665 5 441 361 435 79 117 99 238 637 655 571 600 38 468 179 397 257 665 189 298 414 634 20 266 36 595 38 572 266 429 362 405 112 662 376 387 332 480 437 687 383 527 485 657 32 614 76 419 210 588 302 385 283 663 524 679 280 450 151 277 41 71 157 675 80 424 103 202 547 642 127 610 286 677 114 122 49 162 157 680 228 484 127 572 388 514 68 346 130 660 60 449 429 641 68 113 377 405 193 379 217 420 171 533 389 641 329 480 283 575 71 113 334 344 233 430 153 510 403 432 278 655 69 375 42 420 449 469 18 668 300 424 354 402 156 298 122 408 139 305 87 556 326 364 170 256 212 602 119 212 153 615 250 364 76 673 180 672 251 323 473 653 378 385 87 359 73 450 388 439 21 529 365 567 23 242 379 543 145 403 550 619 22 451 412 457 8 367 444 631 535 676 17 34 86 505 291 635 488 547 511 615 24 487 145 250 491 573 504 634 241 498 240 646 464 587 16 668 216 639 270 451 6 161 356 376 374 675 62 481 391 612 215 273 349 365 48 105 70 371 165 277 458 535 4 332 35 368 552 575 177 192 264 405 573 649 5 473 543 562 362 446 291 396 313 489 142 578 91 526 18 368 310 420 146 282 555 617 92 581 253 614 133 229 167 674 241 320 193 211 308 545 567 610 42 573 111 145 209 419 14 602 553 675 220 574 572 658 267 315 22 546 131 570 400 563 1 116 473 478 38 178 359 687 111 420 85 223 124 301 427 525 463 470 71 658 235 366 639 644 15 235 311 529 89 309 176 621 289 492 389 612 10 19 114 185 159 546 543 676 194 562 192 677 5 54 117 347 237 282 75 524 372 597 360 377 372 611 142 552 420 510 122 540 72 285 119 484 192 425 251 672 368 620 440 576 472 664 157 372 124 251 167 315 59 305 196 677 253 321 4 77 99 371 62 251 115 120 299 316 498 503 113 510 87 580 389 522 314 633 299 534 358 385 163 330 68 407 134 363 186 311 170 269 209 514 88 162 56 482 352 385 181 662 16 122 40 274 441 494 96 440 141 657 261 387 97 243 319 495 59 84 44 189 626 631 61 266 168 193 93 494 433 601 328 427 394 522 469 603 255 299 173 651 2 547 509 673 204 380 431 461 60 356 9 517 662 680 252 330 221 300 447 536 378 459 79 399 153 554 147 655 27 648 45 150 520 531 179 483 17 604 186 245 2 359 174 385 139 551 278 405 337 388 197 583 176 519 404 468 98 284 302 490 307 510 190 646 58 249 22 247 139 312 325 535 32 46 112 357 289 609 185 642 143 484 359 495 589 655 325 631 184 372 148 670 24 75 439 649 264 416 7 168 63 296 436 495 116 280 91 200 361 439 147 274 53 306 112 226 227 671 549 647 293 521 55 163 239 547 93 488 104 253 121 433 119 257 19 502 162 307 61 658 336 591 240 290 222 365 648 658 226 646 145 292 543 610 88 107 27 311 24 264 309 552 142 168 190 259 71 317 168 674 42 616 603 681 409 622 156 159 75 517 244 468 48 578 269 437 217 477 28 568 114 192 70 223 175 432 509 647 27 254 159 636 253 666 140 381 155 345 170 436 350 423 414 450 385 523 466 658 315 431 568 586 182 487 404 634 400 494 179 325 32 269 38 134 298 626 56 517 14 648 428 682 191 469 129 554 46 576 279 424 190 453 82 141 56 76 213 331 205 261 111 309 419 448 145 616 85 441 182 306 96 583 196 242 212 539 583 683 424 500 317 609 56 417 38 205 531 532 43 505 500 615 27 361 583 598 357 390 284 355 360 557 318 471 156 321 71 136 70 574 431 654 577 606 14 383 247 336 96 490 382 536 65 409 397 420 249 259 5 128 103 348 522 591 160 178 443 552 500 544 40 624 324 676 259 321 204 375 7 233 124 250 107 344 124 357 282 575 435 496 169 381 128 431 297 574 7 605 9 595 41 481 429 656 473 658 186 543 47 127 481 539 371 505 247 636 120 251 40 497 452 573 430 526 406 666 203 435 90 617 98 647 94 226 99 330 28 492 197 418 52 319 214 267 23 238 423 614 173 226 37 483 99 300 106 143 197 410 293 391 200 291 496 549 311 596 192 370 147 541 22 209 626 630 435 484 373 410 178 503 84 456 196 362 391 599 616 682 221 664 282 591 108 476 45 104 441 561 515 662 16 314 49 489 294 532 244 546 30 124 271 420 139 447 357 527 105 512 465 657 514 629 488 544 663 679 108 594 127 138 119 246 6 505 149 450 247 360 19 142 468 648 128 168 669 673 231 373 131 301 364 584 419 440 238 346 246 491 54 547 224 254 69 686 457 512 607 634 157 640 74 574 115 571 59 218 42 476 558 626 66 272 575 661 456 580 259 665 106 146 33 458 425 568 311 586 141 663 398 517 204 591 400 516 183 334 225 480 359 617 322 566 248 387 443 445 249 537 367 595 492 573 490 573 129 283 190 432 52 673 200 317 247 359 63 339 635 662 492 507 210 367 95 656 204 210 99 271 477 578 99 321 57 633 274 522 257 267 137 408 262 559 86 605 87 225 119 591 93 258 97 644 251 482 232 617 26 344 265 553 23 136 76 272 92 394 259 570 14 116 172 625 134 230 297 662 127 279 153 550 554 623 43 613 87 389 70 316 101 616 132 251 168 574 120 246 129 153 150 475 645 650 203 251 321 592 91 209 243 482 185 429 159 259 565 641 66 570 213 446 363 521 74 108 321 493 69 640 274 413 101 127 282 357 334 512 355 568 215 516 294 478 175 353 62 624 627 660 505 550 482 636 155 611 128 525 177 678 113 415 63 189 469 683 214 617 135 424 362 552 9 32 2 312 153 369 331 594 107 590 463 651 515 567 64 597 622 625 54 101 259 303 81 462 267 527 340 441 102 657 478 591 587 625 225 631 260 536 355 495 46 544 156 171 398 489 241 560 471 682 264 644 23 149 44 83 189 448 16 235 412 470 363 563 136 540 183 586 85 133 5 110 65 117 93 620 113 153 29 490 77 415 150 229 103 414 304 460 367 425 193 406 65 205 51 100 58 461 226 283 170 584 181 483 550 611 446 588 103 304 128 175 128 509 521 571 259 493 466 620 48 538 77 560 325 595 58 143 391 581 114 327 118 258 310 553 333 430 41 492 544 546 67 614 228 357 576 630 172 640 345 681 404 658 291 435 122 214 287 601 10 230 44 395 71 556 107 524 173 425 421 552 47 92 215 503 464 611 441 652 244 263 52 431 351 676 86 490 638 687 333 586 99 387 315 674 273 614 81 608 249 578 195 408 178 624 222 397 257 638 228 391 263 356 402 641 592 644 57 129 76 124 302 483 1 89 373 381 247 454 161 339 429 671 542 663 56 211 56 111 80 418 12 598 41 631 270 322
Output: 4

Example 2:

Input: 886 136 692 844 557 595 660 670 38 530 139 263 507 565 246 584 104 458 263 744 73 188 270 657 396 885 323 435 437 615 138 198 389 656 806 851 38 878 44 379 753 817 287 323 331 852 151 736 139 407 107 373 522 639 339 811 212 750 354 483 530 597 412 869 374 485 304 332 223 875 446 543 538 793 606 667 314 717 299 601 468 876 42 553 153 633 141 691 753 758 463 866 320 564 136 193 567 619 10 754 216 294 200 225 20 760 394 654 20 317 224 763 509 873 697 812 137 865 186 376 117 294 618 630 645 751 52 223 467 697 530 554 27 762 409 770 378 689 197 411 199 869 454 626 167 882 2 380 132 672 191 525 131 582 196 660 513 793 242 661 795 849 237 607 124 148 134 462 321 742 41 349 292 873 416 442 196 265 370 399 558 646 316 694 220 777 580 780 603 662 91 360 135 200 456 776 89 326 41 781 23 618 487 501 150 734 316 610 100 109 98 449 421 644 243 421 141 149 36 214 182 769 154 203 297 747 263 667 359 485 354 728 364 371 402 818 483 716 557 752 324 465 31 324 558 682 171 420 226 253 454 857 101 614 1 815 573 751 107 329 501 556 530 814 89 90 522 570 564 641 4 106 60 188
Output: 750

Example 3:

Input: 894 520 140 548 131 719 246 286 311 627 709 889 701 846 596 600 143 825 38 286 470 583 218 256 510 836 176 384 323 723 2 132 415 809 396 489 203 442 135 179 393 449 669 690 468 788 263 472 278 504 123 163 413 415 304 864 589 778 337 637 184 491 522 850 577 756 55 858 556 697 14 163 128 621 265 725 627 666 196 807 32 848 18 662 470 879 464 474 442 855 207 485 459 747 12 499 216 785 104 384 221 336 146 183 724 875 142 838 147 744 251 362 643 782 71 345 181 831 356 693 53 413 308 620 391 832 411 507 641 737 503 877 242 849 452 692 334 606 283 698 107 739 653 801 381 666 450 655 221 619 58 648 528 788 5 505 71 654 697 872 350 633 84 478 66 709 258 808 337 813 175 872 427 609 709 726 137 245 38 651 560 658 60 784 255 508 19 575 22 814 13 725 275 295 828 864 786 885 618 740 255 700 352 649 752 787 220 755 241 312 569 684 27 273 476 761 109 285 684 822 24 441 301 533 114 302 53 861 58 408 35 771 144 782 337 777 463 827 610 837 871 888 340 459 330 579 416 706 379 524 176 239 237 842 417 419 34 745 64 380 95 200 14 281 304 837 25 122 816 885 525 870 608 891 134 482 164 291 321 600 479 640 13 61 272 631 96 315 25 562 123 531 269 310 268 388 42 113 113 463 388 573 38 590 218 625 188 252 345 889 54 398 256 463 309 853 587 717 353 471 14 659 516 723 128 498 63 301 3 836 84 629 415 696 129 347 359 463 67 801 113 830 164 447 698 706 282 610 8 644 266 324 328 643 31 278 62 464 815 883 91 894 278 868 31 781 48 802 641 781 563 815 438 739 84 659 200 829 68 446 63 348 533 876 588 629 201 765 46 882 293 466 491 740 220 735 216 871 273 776 18 419 438 453 394 801 340 700 191 451 590 776 161 894 146 617 376 669 275 692 784 863 261 608 133 140 217 562 164 722 38 399 105 367 222 616 146 792 38 506 316 879 55 353 506 831 160 570 177 372 600 825 428 435 764 770 141 672 348 606 19 433 37 534 325 361 116 278 323 755 224 549 85 864 245 393 267 509 294 628 248 635 477 688 10 878 529 794 88 321 574 840 218 704 697 873 248 402 483 674 554 571 348 537 25 599 106 851 193 597 203 275 161 434 52 192 98 670 93 306 144 563 35 93 467 788 362 865 339 465 298 415 714 729 377 783 469 669 496 506 676 749 143 551 576 693 138 444 596 825 379 395 132 709 106 155 567 613 188 532 26 443 562 685 443 551 430 842 240 293 270 809 436 652 21 285 95 821 134 711 445 457 330 409 91 820 413 835 503 634 417 821 453 868 179 884 134 146 280 620 31 328 392 868 833 840 163 476 123 267 323 797 35 51 670 733 300 686 374 843 411 414 67 759 19 651 316 760 620 782 468 577 517 763 293 522 580 882 38 86 594 833 231 573 361 677 516 574 373 455 350 445 51 711 318 710 394 701 252 749 561 687 425 607 361 379 24 166 68 882 239 757 29 475 213 729 120 442 410 889 181 606 68 548 439 572 81 485 69 412 90 750 36 704 316 794 161 752 718 890 566 763 724 787 33 112 739 825 764 893 560 645 503 889 30 412 44 694 237 594 178 440 80 661 120 140 489 677 314 348 67 358 339 789 557 572 651 815 784 816 48 474 608 799 65 421 341 838 564 698 183 352 447 497 645 724 483 773 1 685 279 410 330 806 6 573 388 461 196 573 397 477 170 176 439 884 415 862 140 612 260 458 169 327 315 582 127 817 293 853 108 662 437 797 65 393 648 836 200 715 307 639 103 442 10 154 232 339 291 681 341 569 418 451 50 297 106 669 209 769 256 623 658 695 514 672 97 332 521 685 510 660 130 214 309 480 455 671 583 808 481 672 42 416 272 306 34 585 270 526 36 227 99 225 225 595 580 613 631 642 553 772 343 851 111 212 739 818 223 653 778 796 137 662 683 687 423 428 7 782 146 568 554 673 414 510 385 409 19 22 479 623 279 429 216 275 287 528 418 546 89 580 333 387 118 270 533 571 159 273 117 765 317 763 436 495 352 465 286 866 516 884 258 486 476 798 298 605 6 418 79 636 683 768 233 245 443 745 655 677 271 790 165 213 223 224 220 581 569 789 700 838 38 526 237 633 405 409 167 321 121 557 243 352 482 658 716 865 775 779 113 130 22 448 32 774 390 624 74 756 307 718 635 820 240 554 180 423 485 847 487 702 153 304 266 783 76 889 525 678 549 834 184 287 15 99 453 767 45 114 275 497 251 634 3 51 399 786 105 861 221 763 813 869 340 785 82 494 839 870 185 187 506 614 591 633 339 741 655 711 2 467
Output: 375

Constraints:

1 <= n <= 947; 0 <= m <= 1894; 1 <= u,v <= n.

Loading...
Test Cases:No test cases
No test cases available.