Hide
Problem B
Bonsai Classification
Sofie loves to grow bonsai trees. In fact, she has started selling her trees, and business is booming. Unfortunately, Sofietta has started trying to copy Sofie’s method for growing the trees. However, Sofietta hasn’t quite gotten the technique down, so her approach differs slightly.
All trees grown are $0$-indexed and have exactly $1000$ nodes.
Sofie grows her trees in the following way: for each node i in the interval $[1,999]$, add an edge between $i$ and a random node in the interval $[0, i-1]$. After this, shuffle all nodes labels, while retaining the structure of the tree.
Sofietta grows her trees in the following way: while the tree isn’t connected, add a random edge to the tree that doesn’t create a cycle. After this, shuffle all nodes labels, while retaining the structure of the tree.
Sofie wants you to write a program that can help customers distinguish between her and Sofietta’s trees.
Input
The input consists of $999$ lines, each containing integers $a$ and $b$ ($0 \leq a,b \leq 999$), meaning that nodes $a$ and $b$ are connected. These edges are guaranteed to form a tree, that is to say a connected acyclic undirected graph.
Output
If the tree was created by Sofie, print “Sofie”, otherwise “Sofietta”.
| Sample Input 1 | Sample Output 1 |
|---|---|
895 717 13 97 235 927 545 595 233 994 93 605 214 239 446 482 31 392 982 66 998 330 643 520 861 724 566 780 615 272 367 445 320 760 611 805 675 808 133 287 919 531 626 287 501 930 877 961 429 923 284 932 132 151 137 504 989 455 711 919 748 905 549 430 56 686 135 561 397 845 559 260 814 468 933 568 725 539 687 18 713 583 286 586 398 400 905 97 635 511 426 90 102 914 76 367 630 423 772 98 535 927 603 805 963 65 422 641 258 133 126 889 213 0 203 682 839 929 976 916 870 907 724 533 360 0 130 487 997 728 537 725 548 209 595 568 735 728 418 783 764 862 385 429 318 287 793 13 750 945 182 97 464 350 763 408 579 727 508 685 627 246 377 592 22 773 29 22 405 291 198 468 428 256 539 618 384 506 952 33 308 120 730 487 547 878 664 807 260 717 578 865 509 366 77 583 767 890 395 780 241 969 215 175 657 102 33 531 480 186 177 804 587 559 729 890 252 965 918 30 492 407 865 24 264 948 444 12 185 8 491 618 809 864 50 485 493 417 954 199 117 395 383 783 862 134 883 166 614 307 983 574 18 532 167 899 992 747 780 568 425 758 612 355 47 824 71 135 356 249 288 658 505 903 282 309 265 238 262 767 996 884 413 402 191 725 339 178 412 28 938 641 38 470 173 676 613 710 584 912 336 572 436 659 169 971 930 902 456 875 661 112 225 970 807 404 960 256 316 581 238 24 721 657 338 865 379 399 756 862 449 961 201 469 563 327 720 948 10 910 531 780 845 134 381 417 358 470 513 353 806 328 48 393 795 578 115 154 498 849 560 681 110 862 866 229 708 686 680 615 209 850 561 914 273 776 5 934 495 569 723 195 409 902 312 960 940 300 639 43 469 31 511 275 878 953 570 181 144 985 313 49 734 698 62 49 941 911 494 698 798 710 908 743 263 713 835 530 122 975 374 144 490 575 733 482 789 5 389 291 718 201 932 35 815 542 32 938 671 516 591 407 175 200 348 500 424 666 118 959 964 360 799 692 269 890 644 907 483 572 975 369 390 344 716 914 631 80 859 841 368 124 155 218 278 32 766 115 111 291 419 407 623 484 287 773 79 506 407 33 431 152 876 530 812 338 43 174 402 601 481 894 610 914 825 713 344 22 95 697 458 520 66 252 65 445 415 576 266 871 401 260 220 575 782 369 950 182 565 609 969 43 14 735 1 289 681 808 726 959 717 990 224 572 925 939 396 437 478 735 279 535 826 506 289 957 323 870 517 574 676 747 349 352 875 529 340 392 327 849 361 335 802 423 894 835 913 659 439 758 438 793 223 639 465 392 648 764 231 463 784 127 301 824 670 532 440 88 153 669 515 905 886 165 35 933 769 520 586 291 926 238 935 543 542 639 946 463 240 566 634 960 455 500 140 735 37 988 392 709 841 773 621 779 474 342 186 195 936 800 934 592 686 112 816 627 759 758 362 793 754 652 665 565 970 932 797 205 577 452 55 614 134 130 606 98 828 43 944 84 75 965 145 962 72 47 192 238 650 33 653 685 796 514 457 154 949 845 442 102 255 523 109 478 94 578 150 906 15 434 294 932 864 487 526 519 824 185 34 969 486 693 988 46 558 569 904 550 573 432 400 370 319 534 981 919 479 16 907 484 296 169 0 445 753 902 295 878 739 348 888 727 473 210 808 618 423 618 246 595 777 887 608 929 365 933 810 417 999 405 193 579 931 545 854 432 674 901 45 34 746 490 127 988 226 631 771 583 466 463 434 13 574 810 830 507 451 349 11 175 622 338 880 346 406 597 887 870 658 669 651 392 500 470 605 901 249 232 325 200 98 737 184 597 52 450 293 238 250 978 842 346 740 954 668 984 103 43 684 910 682 235 702 717 87 929 25 478 146 597 649 305 518 487 568 88 917 632 247 676 485 566 576 595 506 103 881 822 528 536 564 468 227 715 148 144 811 735 212 583 906 97 600 152 487 620 187 526 597 510 519 581 82 818 948 853 324 104 219 716 90 175 221 933 239 554 291 583 333 845 363 846 778 441 736 286 743 182 354 141 654 15 892 143 943 365 832 12 719 471 562 426 259 892 274 615 697 718 280 457 208 450 58 255 956 173 9 726 124 865 677 767 157 880 599 847 163 393 890 102 67 852 222 460 121 176 28 186 420 710 59 210 910 574 689 853 317 972 821 496 620 88 951 355 234 318 903 943 41 579 968 304 471 639 710 256 236 89 688 655 8 896 978 88 520 531 589 640 761 468 351 997 369 618 979 965 985 896 732 679 541 730 370 601 91 948 328 357 857 957 257 553 879 487 543 538 705 698 538 432 85 477 207 85 462 46 977 659 435 428 204 434 873 947 468 471 512 141 332 848 872 304 916 252 987 770 393 953 995 545 911 659 972 171 773 865 410 538 768 759 421 157 230 199 863 502 738 578 194 87 744 810 99 353 143 679 290 460 974 845 97 581 525 223 297 365 357 895 112 728 685 599 852 209 388 492 309 595 68 392 228 759 640 447 794 780 375 540 731 840 314 780 229 175 343 206 937 23 254 506 84 113 251 617 503 316 844 228 694 939 162 23 704 971 994 14 980 506 524 793 104 445 594 34 834 937 210 188 53 381 24 583 4 852 582 325 472 868 337 823 139 402 432 566 101 775 712 44 516 645 628 459 831 657 382 565 692 233 108 33 200 445 476 200 571 599 707 343 138 461 955 454 353 785 804 950 927 392 283 52 552 576 497 259 414 252 304 520 990 924 803 841 7 242 749 461 580 778 142 296 305 848 779 987 125 890 899 247 205 352 61 487 86 144 762 943 617 198 691 474 119 568 46 355 833 576 329 158 929 284 376 99 342 762 174 531 901 887 722 327 96 450 942 339 244 455 609 953 947 463 359 540 847 623 272 392 404 35 417 392 158 141 966 961 957 238 355 417 801 912 172 951 19 620 939 864 16 960 350 311 70 46 168 581 211 790 60 401 64 115 232 355 858 381 885 106 891 140 632 554 598 552 742 435 416 948 781 552 678 441 170 627 776 19 900 225 572 698 590 566 107 836 958 733 166 266 460 57 334 506 242 5 783 997 629 512 655 561 40 773 30 979 534 927 618 103 470 933 277 627 189 743 51 46 261 759 267 452 727 702 151 469 669 77 218 568 829 304 78 265 270 188 371 91 945 88 394 403 775 351 196 257 522 418 642 334 633 276 380 334 855 716 411 739 751 924 924 568 180 416 822 795 352 769 164 947 645 88 331 328 364 981 706 620 551 170 27 969 760 173 292 733 161 173 893 446 715 848 656 134 147 903 532 336 619 206 271 957 652 11 57 857 971 365 745 876 923 572 553 773 21 800 188 550 850 758 607 762 882 463 445 35 128 90 569 470 953 990 646 461 550 902 581 728 152 465 889 615 690 140 986 804 557 123 820 97 703 842 624 698 484 395 307 195 199 24 237 554 131 545 696 174 408 265 709 531 372 846 447 620 482 223 757 13 790 339 427 287 636 955 585 590 6 370 915 236 909 165 714 722 217 670 477 391 171 303 874 692 165 897 206 4 827 388 311 862 315 347 183 286 647 12 285 77 860 641 699 458 488 531 596 55 450 904 306 127 540 303 63 495 378 897 141 316 851 174 897 568 310 335 303 485 176 530 758 620 179 526 921 507 817 706 693 271 181 379 156 57 74 253 17 146 502 932 666 128 837 37 160 265 12 943 583 130 347 933 575 135 663 495 616 801 755 102 993 132 683 482 787 948 154 218 843 471 100 921 399 314 602 274 330 53 800 756 129 310 298 91 463 97 44 849 604 939 116 865 366 393 341 974 26 962 42 31 322 970 243 173 514 902 805 947 195 520 105 892 869 65 836 934 281 959 770 104 459 984 593 548 253 232 510 303 430 530 448 709 818 904 984 33 504 726 433 446 387 61 321 134 527 620 3 471 136 973 896 850 73 795 673 921 453 271 856 405 792 640 326 841 268 225 216 44 556 656 660 39 248 512 89 348 667 990 912 174 914 620 961 314 533 245 659 897 588 864 774 716 530 365 113 580 454 455 554 304 299 581 700 269 849 886 23 933 54 759 813 582 637 576 489 360 991 579 523 334 871 761 83 822 275 89 788 107 391 947 69 658 443 329 20 375 452 795 840 401 256 493 80 923 967 990 386 877 641 182 403 530 49 307 441 395 39 662 848 14 973 274 695 311 555 911 546 188 190 422 106 261 123 103 475 15 159 35 928 131 867 112 345 552 819 966 2 478 373 543 567 912 81 771 672 538 335 22 679 586 625 188 902 97 300 666 592 676 521 634 747 470 965 531 302 995 36 894 823 874 728 865 544 617 741 417 178 578 959 487 276 970 737 950 496 982 499 740 437 667 467 299 853 316 92 758 765 630 662 794 868 463 202 135 149 218 346 256 898 760 638 266 752 953 846 304 536 645 701 978 197 959 529 615 962 753 920 271 507 865 838 80 922 955 461 996 114 534 786 527 698 24 245 218 785 568 884 452 601 518 120 65 791 898 |
Sofie |
| Sample Input 2 | Sample Output 2 |
|---|---|
217 492 363 457 67 306 504 823 545 357 352 945 917 485 6 219 353 263 664 552 646 754 830 346 765 189 508 722 144 943 37 152 110 523 232 647 4 222 629 948 96 872 976 0 4 658 724 35 84 260 54 735 659 73 597 763 914 708 393 219 697 850 232 503 850 952 625 187 464 746 173 426 814 468 44 815 166 423 433 776 449 226 589 615 897 740 906 480 79 940 148 545 799 79 628 615 925 969 109 572 879 206 20 872 951 878 117 167 751 960 308 134 804 688 401 600 836 253 85 870 144 102 903 819 842 333 276 816 126 642 447 823 347 229 87 251 635 376 682 460 958 355 894 209 318 13 190 910 800 443 677 211 30 125 645 151 222 286 156 112 702 304 360 665 991 141 343 204 727 59 329 705 283 976 782 156 397 431 521 219 72 127 213 768 79 32 356 569 213 359 506 584 593 500 23 625 556 460 25 177 888 268 299 956 972 676 799 995 148 796 912 634 645 519 997 858 804 18 122 249 264 580 332 306 457 337 118 871 744 3 212 408 827 532 904 239 712 316 653 1 305 981 476 445 703 496 543 782 466 4 371 32 789 11 562 130 441 734 255 495 369 727 271 997 743 816 360 242 307 761 898 201 111 468 911 656 225 81 392 78 568 182 180 851 704 600 952 46 111 571 592 368 29 956 90 786 403 114 475 457 397 794 687 785 686 164 379 260 185 794 406 524 925 195 695 645 555 333 27 613 915 914 545 548 334 383 812 901 205 498 314 377 769 311 359 785 130 315 940 678 944 163 978 704 966 568 27 469 40 915 718 85 928 950 644 297 95 204 130 171 333 530 521 968 994 761 378 919 685 164 902 31 745 605 695 128 810 204 33 256 548 823 535 750 577 490 840 74 163 222 735 39 987 748 382 427 546 279 342 858 337 523 591 677 100 40 998 534 979 920 378 411 465 52 88 331 390 614 236 556 559 581 781 127 185 919 755 654 281 716 736 375 255 853 383 355 169 166 922 660 550 352 340 631 441 445 693 935 220 724 236 830 881 241 314 511 425 119 500 122 764 577 202 855 86 244 847 602 79 394 904 480 251 595 1 941 426 685 776 160 650 322 888 212 695 235 617 145 350 973 747 511 111 700 899 221 615 462 254 996 153 953 888 230 680 848 273 106 484 793 603 88 259 37 607 616 314 223 990 543 700 853 542 505 523 882 569 104 649 878 513 60 49 999 126 846 451 881 705 648 121 359 547 220 721 256 441 449 969 843 356 243 825 75 950 335 920 56 920 721 983 103 904 48 606 391 532 176 902 551 851 716 805 182 870 64 984 86 172 278 154 666 706 743 107 972 274 820 549 94 728 901 756 353 156 428 738 793 946 971 83 224 703 426 678 253 492 261 627 971 358 419 662 156 525 694 782 975 733 463 792 122 828 960 166 105 987 706 68 427 466 464 412 255 207 789 625 637 146 392 622 977 539 732 486 213 400 537 740 596 720 618 567 952 685 270 847 857 494 315 155 855 220 835 684 323 528 295 951 398 924 960 719 262 592 69 509 300 612 285 913 551 223 760 395 714 523 454 547 421 8 701 297 157 643 147 474 616 522 275 193 993 950 316 106 40 51 15 871 926 214 140 956 723 917 795 252 908 617 939 350 19 838 996 446 154 771 588 68 22 809 978 194 674 138 532 321 626 778 883 74 767 540 664 282 149 237 245 677 288 974 367 830 530 961 950 556 654 111 523 928 934 515 347 695 970 479 272 145 683 54 7 556 492 399 846 925 129 489 758 913 640 755 63 235 585 793 831 540 147 92 146 866 159 949 831 419 513 885 20 376 579 65 12 87 714 567 30 602 226 964 987 508 191 924 923 599 309 227 855 411 676 165 889 814 917 984 803 70 490 942 181 78 514 326 852 927 705 576 618 645 461 302 616 930 710 330 306 605 672 980 311 411 779 938 970 991 42 995 192 536 392 285 154 248 770 358 651 255 10 402 419 171 425 150 869 477 333 657 956 61 791 700 509 339 381 481 968 854 674 143 582 931 387 44 567 668 849 442 119 409 836 57 933 151 711 474 974 71 459 811 470 464 372 251 902 113 721 668 696 45 577 931 908 770 298 777 859 784 907 306 361 725 183 181 586 479 289 922 459 318 192 9 349 432 604 552 93 889 947 503 893 52 292 509 388 57 407 705 43 416 178 303 548 453 227 838 325 545 81 420 68 99 278 540 2 77 906 31 134 129 50 611 291 741 895 66 348 715 101 190 554 875 1 818 361 810 357 669 808 986 601 135 200 193 699 994 941 633 59 55 91 437 669 190 810 496 328 150 365 586 639 161 365 795 731 444 555 0 277 691 939 86 191 899 559 951 508 258 819 234 700 126 483 460 783 146 596 216 404 860 982 17 204 370 233 999 920 620 97 663 315 791 473 684 536 636 361 448 817 965 775 828 144 806 620 121 279 120 552 936 330 150 971 527 939 976 802 667 959 774 429 838 432 379 821 125 20 272 457 506 358 89 335 387 416 301 749 918 568 762 302 768 373 405 321 140 804 194 357 565 929 631 633 228 935 51 448 484 861 221 2 26 144 806 265 856 333 710 804 197 947 265 8 753 747 865 171 887 320 502 747 693 324 470 962 121 0 9 195 14 929 208 166 573 816 293 353 418 134 693 827 608 621 240 603 834 30 243 361 721 827 661 120 609 366 900 411 396 223 473 167 894 99 674 157 561 527 182 131 781 149 113 544 898 981 380 390 861 577 749 345 777 700 932 884 213 905 138 713 528 880 509 638 825 996 413 423 623 632 692 988 290 590 675 926 835 826 6 840 967 51 205 995 570 989 372 516 669 357 239 642 357 387 273 137 839 387 247 512 0 891 435 306 899 688 40 271 929 936 432 566 518 179 127 675 539 638 557 161 922 668 407 729 905 597 821 198 257 543 431 677 358 226 759 808 479 336 390 258 161 435 893 241 55 426 806 749 389 61 259 360 739 430 44 533 428 379 497 259 360 235 698 249 311 141 893 79 223 266 463 513 754 985 286 313 807 573 135 162 248 457 11 868 776 204 848 458 919 747 72 645 218 699 215 801 295 919 4 218 430 79 459 115 982 394 320 585 989 680 420 681 820 651 317 287 906 175 496 667 18 628 448 114 867 592 565 132 286 290 886 605 745 477 605 354 976 517 410 505 693 156 687 890 707 203 13 317 800 538 653 766 375 651 705 148 16 322 948 293 938 737 726 91 897 309 895 766 14 123 509 93 695 750 154 948 440 213 666 58 576 668 429 896 335 614 187 954 757 414 435 790 965 638 907 767 600 616 103 713 84 471 987 220 519 780 491 53 77 822 866 357 510 341 677 845 578 210 488 829 364 595 103 978 435 646 23 729 381 19 707 598 410 73 507 918 788 550 108 553 567 969 125 624 556 173 611 499 488 29 915 520 226 267 257 7 974 142 564 671 172 555 630 863 487 805 508 510 12 194 610 238 844 981 564 280 307 200 939 68 821 848 297 601 133 987 865 366 978 157 786 472 244 189 501 80 48 125 808 240 580 898 874 841 837 712 548 182 841 682 773 148 685 691 416 884 467 868 370 23 601 957 670 800 898 417 518 294 520 465 278 434 545 787 326 609 520 47 4 567 40 651 206 674 419 391 362 940 374 249 269 721 244 139 485 867 553 656 170 635 730 725 364 82 975 245 384 564 194 583 41 728 716 390 892 723 931 980 567 676 863 198 34 60 575 149 38 439 90 638 813 188 627 196 690 764 864 270 109 508 717 736 897 38 199 810 459 221 130 549 272 224 57 299 836 845 383 311 862 983 912 157 218 414 280 246 473 613 494 834 490 455 614 262 657 443 351 773 563 296 612 310 493 219 531 987 210 248 304 450 722 963 482 865 554 76 99 188 597 294 988 426 937 869 181 626 573 574 541 124 215 219 330 206 972 338 143 361 450 787 515 916 916 940 204 66 467 40 776 408 28 496 689 916 327 554 707 21 832 708 766 772 255 166 168 408 501 456 627 541 19 47 653 840 312 547 183 146 617 249 53 445 539 684 344 737 986 250 319 662 290 537 565 992 342 831 594 619 722 158 190 715 554 165 805 174 281 406 191 778 235 448 563 241 132 701 3 309 742 392 238 212 553 376 718 709 721 845 532 24 676 47 887 877 284 862 878 679 51 623 901 174 660 135 624 512 541 505 560 793 761 526 130 242 883 888 968 456 62 534 607 962 542 851 25 314 509 436 545 758 625 876 797 741 594 870 98 38 353 673 955 778 694 984 523 855 786 411 91 929 962 655 727 380 293 905 475 415 964 36 235 564 19 522 991 62 204 833 181 184 677 635 360 424 322 834 806 529 68 652 586 260 106 953 269 422 47 220 438 627 5 879 167 798 707 644 678 608 31 370 752 185 478 699 909 239 144 265 386 445 395 274 116 859 201 418 873 838 64 165 429 434 452 646 231 171 171 404 673 385 632 622 484 873 213 1 291 994 924 641 58 136 61 132 587 565 889 558 22 945 588 301 543 824 186 806 957 921 |
Sofietta |
