Parallel bi-directional BFS in Golang for fewest-hops paths
A simple implementation of parallel bidirectional BFS for point-to-point queries in graphs. This mostly exists to help me test my newfound knowledge of Go's concurrency patterns, but it's pretty fast too. The included data is one of the smaller sets (15 MB) from the 9th DIMACS implementation challenge. The link contains bigger graphs you can download and try for yourself.
The search starts two goroutines, one searching from the source and the second searching from the destination. Each goroutine sends newly found nodes to the other along a channel. When a node the other has visited is found, each goroutine reconstructs their half of the path and sends it to the main thread, which combines the data appropriately.
$ go run . 12 251243
Data loaded; graph has 264346 nodes
Searching for fewest-hops path from node 12 to node 251243
BFS starting from 251243 visited 14952 nodes and 22504 edges
BFS starting from 12 visited 14683 nodes and 18252 edges
Search took 29.6079ms
[12 1 1363 1358 1355 1274 1143 1264 1239 1265 1229 1228 1227 941 936 933 935 923 930 919 927 925 924 906 901 755 677 663 660 659 366 365 364 349 347 345 342 320 343 297 294 295 196 202 181 4503 4502 4739 4735 4733 4730 4725 4724 4723 4701 4699 4639 4638 4640 4617 4481 4482 4480 4467 4478 4458 4457 4456 4429 4422 4428 4430 4420 4427 4426 4423 4425 4412 4436 260337 259696 259692 259691 258332 258330 258314 258313 258312 244615 244579 244582 244581 244592 244589 244555 244551 244552 244553 244567 244561 244562 244536 244560 244558 244533 244532 247201 247203 247198 247205 247215 247209 247212 247279 247280 247283 247282 245555 245549 245547 245546 245532 245534 245552 245537 245747 245699 245698 245573 245574 245572 245235 245229 245205 245204 245193 245188 245187 245186 245121 245120 244809 245119 245116 245115 261251 261253 261254 245136 241450 261256 261255 245152 242255 263784 242258 242257 263783 242263 242262 242267 242272 242211 242210 242335 242339 242338 250179 250178 250177 250190 249596 249580 249577 249573 249571 249572 249574 250203 250202 249728 249727 249730 249744 249748 238158 238157 249988 249989 250072 250069 249916 249915 249920 249877 249893 249925 249926 249928 249927 251243]
You can see that the search visits only about half of the graph's nodes, which is the reason to use bidirectional search.
The largest graph in the DIMACS dataset contains 23 million nodes and 58 million edges. Serialized, the file weighs in at 13 GB. My highly anecdotal and not-at-all scientific method of randomly typing in numbers (I did it more than twice!) yields search times highly dependent on the start and end points (as expected). Here's the output for one of the longer paths (4.5k nodes) which ends up searching only 65% of the nodes and 32% of the edges in the graph.
$ go run . 12 15042564
Data loaded; graph has 23947347 nodes
Searching for fewest-hops path from node 12 to node 15042564
BFS starting from 12 visited 7770000 nodes and 9249150 edges
BFS starting from 15042564 visited 7878449 nodes and 9696723 edges
Search took 17.5973489s
[12 11 2097153 3 2097157 66132 67236 1114654 2124294 66117 1114644 1114651 63845 1112376 1114673 1114680 66145 66146 34012 1082528 1082527 33962 33972 1082538 34009 2111097 1082536 1082537 63745 63746 63747 1112277 2123317 1112283 2123316 63744 1112276 1230219 1230218 1230220 1230221 181704 2171722 181734 1230231 1230230 181706 181707 1230252 1230246 1230247 2171719 181721 1230241 1230227 2171720 1230261 1230250 181724 181164 1229685 1230139 181615 1230140 181611 2171687 1230134 181613 1230138 181660 181645 1230136 2171689 181614 2171688 1230142 1230141 1230173 1230172 2171698 2171690 181370 181369 1229891 181367 2171584 1230038 2171588 2171656 181515 181381 1229892 181365 1229888 2171582 181364 1229886 181363 1229885 181366 1229889 181546 181360 181361 181362 1229881 181358 1229877 1229831 1229762 1229761 181239 181240 2171531 181235 1229756 181238 181237 1229759 1229758 2171532 1229754 93402 1141709 2135392 93188 93374 1141704 93335 93185 1141451 2135273 92896 92916 1141439 92903 92908 1141429 1141397 92868 1141393 92920 1141461 92919 92818 1141342 92817 92816 92760 92761 1141288 1141289 1141375 92800 1141279 1141278 92750 1141362 92756 92755 92758 92711 2135202 2135201 1141195 92668 2135187 1141203 1141204 2135188 92678 1141202 1141199 92673 92674 92727 2135185 92667 1141193 92699 92700 90968 1139484 1139485 90961 90960 2134480 90953 2134481 90964 1139492 90965 90941 90942 1139466 2134473 90970 1139494 1139357 90833 90834 90832 1139353 1139350 2134427 90817 1139334 1139340 90818 90815 1139332 90806 2134418 2134416 90804 1139326 90803 1139312 2134411 90787 1139307 1139322 1139320 2134414 2134415 90797 1139319 90918 1140788 90934 1139457 1139458 1139682 2134454 90899 1139283 90892 90900 2134451 1139417 1139372 1139416 90901 91934 2134877 91936 1139406 2134878 1140460 1140462 1140514 1140470 91947 91981 2134886 1140480 91975 91956 1140556 1140498 92035 92079 1140600 92078 1140616 1252780 204210 204211 1252661 204113 2180848 203967 1252518 203971 1252551 203966 1252516 2180858 1252511 2180850 203960 1252493 203854 203940 1252403 1252401 2180808 203848 203946 2180842 1251697 1251696 203830 2180805 1252381 203828 1252380 1252379 2180800 203833 2180801 1252417 203842 203841 203843 2180818 203851 2180809 203850 1252426 204022 204021 1252572 1252573 10342408 11131247 11131248 11131246 11130852 12179580 12179581 12179556 12179557 10342217 10342218 10342215 11130848 12179547 12179546 12179548 11130849 11130850 11130801 11130803 11130804 11130792 11130667 12179420 12179419 12179418 12179415 12179416 12179403 12179405 10342180 10342182 12179400 10342166 10342165 11130646 11130645 12179228 12179226 12179222 12179221 10342002 10342003 11130471 10342095 11130188 12178934 12178935 11130183 11130184 11130178 11130177 11130172 11130164 11130162 12178915 12178901 12178902 11169585 11169586 12218327 12218321 12218322 10356029 10356030 11169580 11169576 11169561 12218314 11169562 11169563 11169564 11169545 11169565 12218310 11169133 12217807 12217806 11169047 11169048 12217788 12217789 11169054 11169041 10355833 10355834 11169035 10355832 11169051 11169029 11169028 11169026 11169027 11169014 11169016 11169045 11169013 12217773 12217774 11169044 11169042 11169043 12271265 12271266 10374864 10374808 10374805 10374804 10374803 11222277 11222309 12271009 12618535 10374783 10374785 11222247 11222248 11222243 11222244 12271028 11222236 11222232 12270994 12270996 10374796 12271000 12270999 12271001 12271002 12270997 11222229 11222228 12270227 10374497 12270194 11221309 10374439 10374495 11221304 11221305 10374406 10374407 11221295 11221296 11221292 10374408 10374409 11221204 11221196 11221194 12269970 12121329 12121328 12121331 12121330 12121257 12121258 11072523 11072525 11072527 11072675 11072552 11072539 11072541 11072537 11072538 11072551 11072579 10321471 12121239 12121238 12121230 12121231 12121236 12121235 10321474 10321467 10321468 12121256 11072510 11072511 11072512 12121229 11072496 11072295 11072304 12120997 12120998 12120910 12120996 11072279 11072280 12120978 12120979 12120977 12120971 11072390 12120976 12120975 12120967 12120973 12120972 12120969 10321408 12120989 12120988 11072277 10321383 12120999 11072190 11072188 11072229 12120941 11072206 11072205 11061406 11061405 12110115 12110114 12110099 12110424 12110421 12110420 12110129 12110130 12110112 12110110 12110109 12610772 10317527 10317523 10317524 11061398 11061401 11061363 11061367 11061366 11061368 12110095 12110066 12110068 12610771 12110062 10317510 10317512 12110064 12110063 12110065 12213126 12213127 12213124 12213125 11164378 11164367 11164369 10354164 12615736 12213109 12213108 12213066 12213065 12213069 12213067 12118078 12118077 11069338 11069343 11069344 11069345 11069364 11069340 11069363 11069342 11069341 12118080 12118079 12118081 12118083 12118084 12118066 12118067 12611211 12118063 12118065 10320333 10320334 11069334 10320332 11069401 11069329 11069208 10320291 10320290 11069255 11069254 12611150 10320297 10320295 12117939 12117938 12117979 12117978 12117944 12117942 12117992 12117990 10320306 11069262 12117946 12117945 12117948 11069108 11069106 10320258 10320257 10320271 12117867 12117843 12117842 11069167 11111385 11111391 11111389 11111388 11111392 11111393 11111384 11111390 11113314 12162065 11111402 11111395 11111394 10335317 11111400 11111401 11112289 12160244 12160245 12161034 12161050 11112288 12161039 11112295 11112294 11112292 12161373 10335735 10335734 10335736 12161399 12161401 12161403 10335739 10335738 10335740 10335741 12161406 10335620 12160982 11112275 10335671 10335672 12161233 12161112 12161111 12161121 12161120 12161132 11112388 11112392 11112399 11112404 11112403 10335676 10335677 11112400 11112188 11112402 11112499 11112497 11112498 12161114 12161115 12161000 12161002 12160981 12160980 11112236 11112185 10335606 12160906 12160911 12160909 11112170 11112169 12161054 12161055 11113504 11113503 11113501 11113490 11113491 11113487 11113488 11113492 11146528 11146526 11146527 11146481 10347787 11146477 10347791 10347790 10347792 10347793 10347794 11146471 11146464 11146480 11146479 12162222 11113477 11113475 10336056 11113481 11113478 11113470 11113466 11113467 11113464 11113465 12162218 12162221 11113391 12162131 12162133 12162128 12162126 12162124 12162125 12162121 12162122 10366500 12247706 12247707 12247704 12247703 10366483 10366475 12247767 10366480 10366478 10366479 11199009 11198968 11198967 11198952 11198950 11198951 12247539 10366421 10366423 10366422 12617400 12247532 11198873 11198808 11198807 11198421 11198809 11198810 11198815 11198814 11198818 11198820 11198819 12247564 12247563 11198854 11198855 12247566 12247565 10366430 10366431 12247621 12247543 11198806 11198804 11198756 11198755 12247498 12247497 11214736 11214737 11216048 11216050 11216051 11216058 11216053 11216056 11216055 11216059 11216061 12264806 12264807 12264795 11215956 11215959 11215962 12264620 12264619 12264622 12262685 11215853 11215852 11215864 11215862 11215863 10372517 11215858 11215860 11215861 10372522 11215921 11215922 10372094 10372095 11215866 10372513 10372496 11215875 10372499 10372497 10372170 12263694 11214976 12263812 12263696 12263695 12263698 12263699 12263700 11214939 11214941 11214940 10372168 10372169 12263822 11215060 11214942 10372113 11214775 1309290 1308321 1308320 259730 2203732 1308289 1308290 259724 1308283 259723 2203729 1308280 259721 259722 1308279 259457 1308014 2203620 1308278 1308004 259447 2203616 2203613 259624 1307997 259439 259440 259599 259239 2203535 259237 2203534 1307802 1307801 1307792 1307793 259282 259233 1307791 2203533 1307829 259231 1307788 1307787 259274 2203545 1307790 1307789 2203531 259230 1307786 259228 1307785 259156 259103 259102 2203476 259100 259140 1307691 259099 1307658 1307690 1307657 259098 1307704 2193900 235779 235778 1284334 2193901 1336646 235783 1284339 235777 2193899 2193898 1284331 1284324 1284323 2193895 1284330 2194090 2194057 1284718 1284719 235771 2193896 235770 235768 1284322 235769 1284325 1284326 1284317 2193892 1336544 287980 1336559 1336545 235765 2215323 1336541 287979 287978 287977 1336539 2215300 287882 1336446 1336444 2215281 287878 287881 1336443 1336441 1336442 287873 287874 287912 1336468 287858 2215271 287857 1336461 1336414 287852 287855 1336417 2215270 1336424 287795 287777 2215236 1336376 2215241 1336349 235716 2193873 1284272 235715 1284275 235720 1284278 2193875 235721 235727 253520 253519 1302058 1302062 1302065 253523 253518 253517 2201182 1302060 1302061 253525 254768 254767 1303314 1303362 1303374 2201698 1303316 254815 2201699 1303319 254816 2201718 1303428 2201727 254833 2201701 1303324 254782 1303329 1303328 254781 2201684 1303271 254724 254725 1303264 254716 1303265 1303267 254745 254744 1303293 1303294 2201683 1303269 1303270 1303297 2201680 1303262 1303268 2201682 1303266 254720 254705 254706 1303300 1303050 1303185 1302932 1302928 254383 254378 254379 1302915 254373 254369 1302913 254371 2201539 1302920 2201538 254375 256366 256358 1304910 1304918 256354 256353 2202354 1304902 1304903 1304900 1304901 256107 256106 256104 256101 255957 2202191 255956 255949 2202186 255943 255942 255941 255955 1304502 1304503 256050 256048 1304601 255897 1304433 255885 1304422 255875 1304423 1304414 255862 255863 256014 2202149 255859 255811 255812 1304562 2202096 255856 1304400 255845 1303933 255386 255261 1303799 1303792 1303788 255244 1303858 255299 255230 255226 1303774 255296 2201917 1303755 255209 2201881 1303757 2201879 255207 1303754 1303743 255195 1303741 255193 1303740 1303861 1409156 360542 1409108 360544 360534 1409099 360533 2245106 360532 1409098 1409095 360492 360380 1408946 1409053 2244945 360126 1408687 1408683 2244941 360117 1408681 2244940 1408679 360114 1408701 1408700 360121 360120 1408685 360118 360119 360134 1408677 2244938 1408641 360075 1408646 360080 360081 2244924 1408642 2244923 1408634 1408636 1408632 1408633 360066 360067 360089 2244917 1334253 285684 1334242 285698 285453 285454 285677 285676 2214378 2213988 284717 285690 285696 1334231 2214375 1333901 285333 1333891 1333898 1333899 285236 285246 285247 2214198 1333794 1333797 1309566 261009 1309554 260996 2204255 1309553 1309564 1309545 1309546 1309543 260993 260988 2204250 260986 260987 1309580 260984 260985 260982 2204248 1309538 1309537 260980 260977 260978 261013 260976 1309533 1309527 1309528 1309525 260968 260967 260960 1309517 261397 260936 1309446 2204211 1309440 1309441 262864 262865 1311417 262801 262795 262796 1311402 2205015 262857 262776 262779 2204989 262780 1311410 1311326 1311335 262783 262784 262872 1311329 2204988 1311440 262889 2204985 2204298 1309664 262855 262854 2204873 1311049 262498 262499 1311142 2204908 2204912 262597 262494 2204872 1311046 262568 2204871 262491 1310801 2204767 262479 262093 1310612 1310613 262057 262058 1311011 1310609 1310610 2204707 2204690 1310607 262056 262082 1310634 1310615 262062 1310614 262071 1310611 1310606 1310604 2204689 1310597 262043 262035 1310588 2204680 262029 262030 2204676 1310575 1310571 262019 1310472 261919 261922 1310474 2204632 1310473 2204633 1310477 1310475 1310478 2204606 261847 261849 1310403 261850 2247882 367260 2247877 367261 1415833 2247885 1415832 367263 367262 1415792 1415732 2247839 2247838 1415730 1415731 1415770 1415728 1415729 367156 367155 1415723 1415724 367152 367153 367199 367200 1415831 367259 1416479 1416477 2247755 1415537 366963 366958 366955 1415510 2247744 367942 367133 1415644 1415503 366930 366931 1415020 1415019 1415021 2247543 366450 366451 366487 2247560 366488 2247554 366465 1415033 2247539 366441 366458 366440 1415009 1415042 366439 1415007 2247538 1416577 1415054 1415003 366435 1415043 366438 2247537 366434 1415004 1415006 366436 366437 1415067 1414986 1414985 366295 366393 1416601 1416602 368034 1416603 1414862 366290 366291 1414908 2247495 366287 1414860 1414858 366286 1414897 1414855 1414851 366278 1414849 1414850 366276 1414847 1414846 355185 355186 1403750 1403751 1403740 355175 354734 1403289 354716 354715 1403738 1421115 2250051 372552 1421111 1421112 2250048 372550 372559 1420488 371923 1420466 1420467 371924 371948 2249780 371900 1420485 1420463 1420464 1420510 1420480 1420481 371932 371912 1420461 2249778 371893 371830 371831 371869 1420434 1420394 2249749 2249748 371823 2249474 371153 1419623 2249435 371090 2250191 1419730 371102 371103 1421459 1419636 1419637 371154 1419725 2249441 371041 1419599 1419605 371069 371087 1419655 371014 2249417 1419579 371012 1419588 371001 1419570 1421276 1419558 370990 1419535 370965 371171 371173 371070 370958 1419520 1419506 370936 2249386 1419515 1419509 2249383 1419491 1419484 370929 2249381 370934 370935 1419668 1419487 370923 370925 370917 1419477 370897 370889 1419458 370886 1419453 2249362 370883 371217 2249498 1419434 2249354 370308 370302 1418864 1418826 370299 370261 370241 1418806 370243 1418770 2249085 370244 15424579 17206779 16221824 16221823 15424578 17206778 16221822 16221821 15424516 16221710 17206677 15424533 17206706 15424534 17206751 16221792 17206713 15424538 16221705 16221704 16221702 17206670 17206671 15424512 16221767 15424511 16221701 17206669 15424545 16221763 15424546 16221765 16221627 16221626 16221227 17206257 17206258 16221098 15424180 16221101 15424181 17206157 17206156 16221539 17206527 17206592 17206533 16221545 16221551 17206521 15424418 17206536 17206537 16221602 15424426 16221546 17206531 15424425 17206584 15424424 16221543 15424456 16221600 17206530 17206529 17205205 16220006 16220005 17205196 17209136 17205190 16220000 15423592 16219998 16219995 17205187 17205207 16224784 16220019 16219994 15423606 16224718 15426163 17209361 17205202 16220016 15423580 17205188 17205189 15423381 17204872 17204873 16219623 16219622 17204867 17204866 15423378 16219624 17204879 17204874 16219634 16219633 16219626 15423367 16219582 16219581 17204830 15423355 17204832 15423337 16219553 17204812 17204850 15423354 17204831 16219606 17204816 15423353 16219562 17204811 15423349 17204823 16219575 17204824 16219577 17204825 15423351 16219580 16219579 17204845 16219779 17204837 16219588 16219607 17204840 16219592 15423360 17204773 16219518 16219516 16219517 16219537 15423328 16219510 17204767 17204496 15423145 17204764 15423128 16219172 16219343 16219344 17205018 16219330 17204609 16218917 17204248 16219331 17204608 16219328 16219329 16219325 17204605 15423213 16219324 17204978 17204603 17204604 16219076 16219077 15423193 16219288 16219287 17204572 16219275 15423186 16219276 16219277 17204564 17204565 15423192 16219286 17204562 15423185 16219271 15423183 17204546 16219254 16219251 16219250 16293216 15463686 15463649 15463568 16293200 17268971 17268966 17268965 16293183 15463650 15463645 16293194 15463652 16293198 16293329 15463722 17268982 16293203 16293202 15463653 16293201 15463655 17269092 15463656 16293206 16293220 17269014 17268992 17268991 16293214 15463661 17268993 16293218 17269034 15463664 17268998 17269000 16293225 17269004 17269003 15463669 16292992 15463538 15463539 17268798 15463542 17268803 17268804 15463557 17268826 16293645 17269372 17269373 15463898 16293646 16293648 17269255 17269256 17269335 16293609 17269254 15463824 15463854 17269252 17269253 17268633 17268634 16292800 16292852 16292801 17268632 15463435 16292799 16292850 16293614 17269247 17269246 16293506 15463823 17269263 16293523 16293525 17269265 17269264 16293528 17267298 16293524 17266697 16293617 17269259 17269251 16293510 16293599 15463818 16292839 16292798 16292793 17268264 17268265 16292371 17268259 17268258 15463199 17268257 15463198 15463204 16292367 17268256 17268300 17268301 15463197 16292418 15463225 15464054 17269573 16293879 16293878 17269574 15464025 16293877 16293880 16293875 15464022 17269569 16293940 17269568 17269562 17269588 17269583 15464031 16293899 16205924 16205927 17192936 17192934 15415870 16205935 17192938 17192323 16205344 17192322 15415846 17192927 15415862 16205913 15415853 16205896 16205897 17192922 16205894 16205895 16205602 17192649 17192650 15415693 16205604 17192651 16205612 17192657 17192658 15415698 16205613 17192662 15415700 16205616 16205653 15415682 16205583 17192712 16205584 17192634 17192637 15415683 16205585 17192703 17192692 16205586 17192635 16205643 17192691 17192690 16205644 17192688 15415715 17192689 17192636 15415684 16205587 15415523 17192380 17192378 17192375 17192376 15415517 16205277 16205278 16205275 17192362 17192215 15415421 16205102 15415458 16205089 17192206 17192193 16204675 15415408 17192274 16205078 17192196 17192195 16205081 15415409 15415405 16204394 17191599 15415029 16204393 16204326 15415020 16204372 15415037 17191541 17191521 16204307 17191519 16204300 17191516 17191513 17191514 17191536 16204230 17191511 15414976 17191510 16204146 15472396 16309147 16309149 15472395 16309146 16309144 16309145 17282887 17282877 15472394 15472397 15472398 17282873 16309138 17282874 16309133 16309126 15472382 15472370 16309102 16308931 16308930 17282689 16308932 15472307 16308988 16308966 17282679 16308986 16308987 16309065 17282738 16308973 16308974 16308691 17282481 16308681 16308682 17282473 17282427 16308628 17282436 17282435 16308654 17282449 16308625 17273648 16298559 15466580 16298547 17273637 17273635 16298537 16298539 15466586 17273630 15466575 16298530 17273623 15466570 16298529 17209859 16225363 17209856 15426514 15426455 16225252 17209763 17209754 16225240 17209753 17209747 15426444 16225233 15427140 17212206 15427989 16228059 16228076 17209746 17212220 16228065 15426821 17212204 17212205 16228050 17212198 15427999 16228069 16228044 17212192 16228130 16227839 17212014 17212013 15427869 17212111 16227829 16227827 16227828 17211997 17212061 16227947 16227822 15427860 16227821 17211996 15427858 16227816 16227817 17211994 16227814 16226037 15426876 16226020 16226066 15426841 17210375 15426840 16225953 17210449 16226016 16225944 16228396 16225947 17210367 16225946 15426886 16226018 16225943 17210365 15426873 17210364 16225942 15426871 16225940 16225941 17212678 17212677 16225936 17210358 15426868 16226005 17210357 16225934 16225935 16225927 17210350 17212476 17249999 15451792 15451738 16269824 17246000 17248409 17248408 16269600 16266815 17250084 17248406 16266761 15450737 17248402 15450718 16269557 15450717 15450713 17245915 16269548 16269549 16268318 17247292 15450034 17247284 17247244 15450005 16268256 15450003 15449440 17246341 16267227 16267209 17246326 16267205 16267204 17246319 16267202 17249364 16270696 16271179 16267072 16271028 15451520 16271178 17249657 16266959 16271934 17249654 16271029 16267071 16267051 15449345 17242428 17249366 17249649 17249650 16270698 15451339 16270699 16270700 15451340 15451312 16270647 17241908 17241907 17241904 16262022 16262133 16262023 15446591 15446589 17249469 17241792 15446582 16259847 17239901 16259828 16259827 15445387 17239892 15445386 16259796 16259795 17239867 15445370 17239866 16259787 17142059 16147498 15383870 17142039 16147451 17141997 16147429 16147428 15383832 17141186 16146505 17141961 17141962 15383819 16147382 15383812 17141950 17141934 15383800 15383036 17140696 17140695 16145941 17140687 15383019 16145926 17140683 15383015 17140664 15383004 15420526 16214407 16214397 16214399 15420515 16214425 17200315 16214403 15420518 16214404 16216338 15421576 17202003 17202002 15421577 17202004 16216341 17202005 17202006 17201959 17201953 17201954 16216291 16216287 17201871 15421534 16216264 16216258 16216259 17201925 15421530 17201858 16216177 15421487 16216176 17201855 15421485 16216210 17201853 16216170 17201848 16216165 17201849 16216166 17201850 15378928 16138444 15378685 17133785 17133783 17133784 17133782 16137993 17133779 15378658 17133777 17133776 15378679 16137984 17133667 15378611 17133737 16137861 17133657 17133658 15378428 16137525 17133371 16137516 16137515 17133363 17133422 15378415 16137508 17133387 17133349 17133346 16137490 17133340 15378438 17133331 16137454 17133284 17132930 17132931 17132932 16137023 17132926 16137014 16137006 17132919 15378141 17226157 16244061 16244048 16244049 16244050 16244041 17226141 15436746 16242699 17224969 17226136 17226059 16243952 17226056 17226051 16243935 16243932 17226049 16243938 17226048 16243482 16243395 16243372 17225557 16243359 16243362 15436374 16243352 17225541 15436450 15436445 15436367 16243348 16243347 15436366 16243346 16243339 16243340 17225531 15436362 16243326 16243253 16243254 16243252 17225451 16243247 16243250 16243249 17225449 17225450 15436312 15436340 17225448 17225419 15436292 16243215 17225442 16242784 16242785 15436057 16242777 16242778 17225047 17225040 17225002 16242738 15436031 16242759 17225004 16242740 15436032 16242739 16242737 16242736 16242735 17224955 15435999 16242680 15436001 16242685 17224956 16242683 16242682 17224954 16242681 17224953 16346573 17314983 15492571 15492566 16345976 15492587 16346016 16345975 16345982 17314979 15492569 16345980 17314977 16345979 15492567 17314975 17314976 16345978 17314872 16345855 16345856 17314871 16345854 16345853 15492499 17314869 17314870 15492484 17314844 16345827 15492472 16345808 15492474 17314828 16345804 17314821 17314077 16344941 16344938 17314068 15491996 16344932 15491993 16344933 17314065 17314030 15491972 17314031 16344895 15491973 16344896 16344897 17314032 17314033 16344898 16344870 17314007 17314008 17190047 17190046 16202603 15414049 17190039 17190040 16202605 16202608 16202607 15414051 17190033 16202597 17190034 16202598 16202447 17189899 15413959 16202442 17189894 16202438 15413956 15413966 16202412 15413932 16202391 17189849 17189867 17189847 17189848 16202389 16202390 17189846 16202392 16202409 17189853 16202394 17189854 16202393 16202398 16202399 15413936 17189857 17189856 15413935 17189995 15413916 17189823 16202361 16202356 17189817 15413910 17189814 17189808 16202344 16202353 17189815 15413911 17189813 16202347 16202348 15413908 16202345 17189810 15413905 17189805 15413903 16202292 17189765 16202293 15413879 15413613 17189340 16201803 15413609 17189335 16201798 16201797 17189328 17189269 15413565 16201718 15413562 17189265 17189260 16201712 17189261 16201710 16201711 15413557 16201708 15413555 15413553 15413379 16201389 17188970 17188964 17188957 17188954 17188946 16201353 16201354 16201404 17188989 17188944 16201349 5241665 7333281 5241662 6284711 7333278 6284708 6284698 6284688 7333254 7333242 7333238 7333224 7333225 6284657 7333212 6284650 5241646 7333207 5241645 6284640 6284717 7332877 6284300 7594984 6284299 6284297 6284290 6284284 7594980 7332851 7332852 7332845 6284272 5241580 6284271 7332838 5241579 6284260 7594972 6284255 7332821 7332599 7332595 7332596 7594920 7333562 6285000 6283992 7332560 6283985 7333548 6284974 7333537 7333535 6284969 5241706 7595143 6284962 7333522 6284961 7333520 7333488 7333489 8468564 7657123 7657124 8411933 7614353 7614354 7614351 9452143 9452142 8411788 8411789 9452150 8411802 8411778 7614232 9452119 9452120 8411768 7614099 7614090 8411574 9451998 7614082 7614081 7614076 8411559 8411560 7614068 9452002 8411550 7614071 7614070 8411553 8411551 9457235 9457233 9457236 8419752 9457204 9457205 8419677 8419672 8419673 8419671 8419670 8419669 7620172 7620173 9457037 8419419 8419418 9457038 9457039 7619999 9457027 8419404 8419402 9457024 7619978 7619975 9457010 7619966 7619921 8419191 8419192 9456970 8419330 8419331 8419334 9456981 7619914 7619918 7619919 9456883 8419188 8419180 7619823 9456877 8419176 8419175 8419164 7619801 7619802 9456868 7612693 7612692 7611890 9450810 9450811 9450806 8409722 7612682 9450799 8409714 8409382 8409381 7612424 9450584 9450583 9450582 9450581 7612395 7612389 8409332 8409328 8409333 9450488 9450487 9450511 8409213 7612304 8409212 7612303 7612301 9450436 9450437 7612300 7612297 8408966 7612118 9450316 9450317 9450318 9450319 9450320 9518552 9518553 8514857 9518548 7692147 7717872 7717871 8548867 8548871 8548872 8548851 8548850 8548852 8548853 9540456 9540457 9540458 9540459 9540461 9540460 9540463 8548849 8548848 8548843 8548845 9540433 8548815 8548814 9540434 9540436 8548811 7717821 8548797 8548776 8548775 8548777 8548778 8548779 8548774 7620823 7620822 7620825 7620824 7620736 8420345 8420347 8420343 8420342 8420341 9457710 9457712 9457711 8420424 8420423 8420422 8420425 8420426 8420459 7620650 7620649 7620646 7620564 7620563 7620562 7620559 7620560 8420149 7620556 8420144 7620557 9457508 9457482 7620520 7620522 2741789 2741790 3509241 4492130 3509219 4492109 4492110 2741775 3509216 3509217 4492092 3509197 2741763 3509198 4492093 3508957 2741762 4492091 3509193 4492089 3509155 4492095 3509195 3509183 3509151 4491882 2741612 3508939 4491881 4491877 3508936 2741608 2702527 2702528 3442704 4437615 3442698 2702526 4437571 3442644 3442639 4437558 3442637 4437563 2702490 4437363 3442374 4437346 3442372 3442369 4437344 3442368 3442366 2702240 3442213 3442210 3442211 4437210 3442208 4437206 2702236 3442203 3442030 4437064 4493310 2742639 3510672 4493299 4493298 2742630 4493293 4493290 2742641 4493123 3510458 2742505 3510447 4493111 3510440 4493105 3510429 2742520 3510476 3510477 2742514 3510473 4493167 4492793 2742222 3509968 3509969 3510045 4492781 2742259 4492780 3510040 4492764 3510017 4492757 2742243 3510058 4492750 4492438 3509615 4492431 4492430 2742006 4492424 2741978 2741975 3509556 2741971 3509552 2742721 4493420 4492319 2741933 4493418 3510818 3510817 4493412 4493411 3592621 2790916 4560408 3592617 3592613 2790804 4560252 2790801 4560246 4560244 2790797 3592415 3592409 3592410 4560098 3592244 3592242 3592243 3592240 4560097 3592239 4560096 4560085 3592237 4560099 4559967 3592082 2790580 3592081 3592080 4559961 3592046 3592045 3592047 4559936 4559937 3592043 2790571 4559927 2790568 4560942 4560940 3593262 4560883 3593260 2791292 4560880 4560925 3593190 4560879 3593188 3592999 3592998 4560723 4553535 4553534 2785963 3584217 3584213 3584108 3584109 3584210 4553523 4553520 4553519 2785951 2785950 3584128 4553456 2785906 3584127 3584124 4553452 2785903 3584118 4553448 4553447 4552728 3583234 3583236 4552731 2785382 3583229 2785379 4552726 4552727 2785380 4552624 2785263 3583100 3582993 2785239 4552619 2785302 4552620 3582991 4552528 4552527 4552525 3582982 2785221 4552465 3582917 3582911 4552467 2785196 4509603 2754313 4509596 3530550 2754308 2754306 3530548 3530434 2754240 4509501 2755509 3532591 4511255 3532588 4511253 4510365 3531496 4509503 3532587 4511254 3532586 3532604 4511268 2755517 3530437 4511252 3532582 4509557 3530504 4509559 3532574 3532573 3532566 4509540 3530482 3530487 3532565 4511237 3532579 4511168 3532479 4511167 2755444 3532483 3532484 3532480 4511169 3532441 3532439 2755420 3532438 2755419 4511134 2786321 4554018 3584808 4554019 2786306 2786304 3584806 4554015 2786305 4554024 4554014 2786281 3584763 4553991 4553980 4553978 3584768 4553983 4553984 3584766 3584767 2786280 3584761 4553979 3584756 4553932 2786247 3584703 4553930 2786246 4553949 3584700 3584698 2786241 4553924 3584696 4553819 2786166 3590076 4558329 4558328 2789420 3590073 2789418 4558343 2789416 3590072 3590095 3590068 3590065 4558318 2789409 2789400 2789182 4557998 3589672 4557997 3589669 4557996 3589670 4557995 3589668 3589667 4557990 4557988 3589655 4557985 2789152 4557942 3589601 4557732 2788988 3589345 2788994 4557729 4557728 2788987 2788986 4557725 3589333 3589289 4557683 3589288 4557682 3589286 2788953 3589285 23037017 23866316 23866312 23037016 23866313 23037014 23866308 23866306 23037013 23866305 23866244 23866243 23036566 23865150 23036989 23866242 23036988 23036986 23866237 23866257 23866231 23036981 23866229 23036998 23864138 23036169 23864082 23864135 23864965 23864136 23036168 23864124 23864122 23864121 23036162 23864118 23864116 23864092 23036144 23864072 23864071 23864073 23864070 23863770 23036024 23036000 23863705 23863704 23035828 23863338 23863260 23863259 23863243 23863234 23862808 23862791 23862809 23035012 23861176 23862616 23862609 23862614 23862309 23862305 23862302 23862258 23035433 23862248 23862242 23862243 23862246 23861350 23861351 23861348 23861347 23861345 23861346 23861255 23861254 23861250 23861247 23035039 23861243 23861109 23861108 23861105 23861111 23861172 23035011 23861174 23034994 23861115 23861114 23861113 23861001 23034948 23861000 23861004 23034949 23861005 23860989 23860987 23860988 23034942 23860959 23780601 23780524 23780525 23780523 23780589 23003261 23779889 23779890 23775202 23001433 23775201 23779808 23779769 23779770 23779768 23779773 23003215 23779800 23779771 23779764 23003212 23779288 23778932 23778930 23778931 23002885 23778927 23778926 23778918 23002881 23002911 23778891 23002870 23002867 23778882 23778876 23778874 23778871 23779159 23775685 23775686 23779247 23778858 23778837 23778829 23778828 23002842 23778818 23003003 23003550 23779174 23779175 23002979 23779173 23779013 23778709 23002763 23778541 23778542 23003542 23003563 23778359 23777317 23777318 23780633 23780634 23778275 23778276 23002614 23002609 23778218 23780613 23778088 23777988 23777989 23777979 23777980 23777973 23777959 23777958 23777464 23777457 23777424 23777425 23002295 23002293 23777409 23002312 23002306 23777436 23777437 23777450 23777451 23002269 23777345 23777344 23002268 23777343 23777260 23777259 23777257 23777258 23002263 23777333 23000441 23772662 23772729 23000467 23772724 23772725 23772653 23772654 23772597 23000414 23772594 23000402 23000403 23772596 23800389 23800353 23800354 23800349 23800347 23800344 23800341 23011251 23011272 23011271 23800390 23800279 23800275 23800212 23800213 23800262 23800263 23800271 23011219 23011187 23800188 23800192 23800191 23011190 23011188 23800187 23800179 23011127 23800167 23011182 23800168 23011178 23800161 23800159 23011177 23011220 23799094 23799075 23010755 23010752 23799064 23799081 23799082 23010748 23799056 23799091 23799089 23798908 23798906 23798907 23798902 23798897 23798898 23010719 23010718 23798881 23798880 23010680 23010679 23798876 23798874 23798872 23798873 23798983 23798068 23798069 23798800 23010628 23010627 23798745 23798753 23798801 23010608 23798690 23798689 23798688 23798685 23010605 23010607 23010610 23798693 23010609 23798716 23798719 23798591 23010566 23798384 23798383 23010486 23798382 23798378 23798377 23798375 23798372 23010481 23010199 23797644 23797683 23797671 23797670 23797698 23797699 23798369 23798374 23798478 23798376 23010484 23798361 23798362 23010478 23798346 23797562 23010162 23797559 23797571 23797576 23010160 23797554 23797538 23797539 23010170 23797515 23797514 23797517 23010145 23013441 23797509 23013429 23805911 23013425 23805909 23805910 23013466 23805908 23013426 23805912 23805913 23806002 23013427 23805914 23805915 23805354 23013208 23805353 23805352 23805331 23805333 23805316 23013193 23805762 23013368 23805305 23805296 23013184 23013183 23805283 23805284 23805285 23013178 23805274 23013180 23805276 23805273 23805064 23013097 23805066 23012983 23804784 23804783 23804772 23804770 23804765 23804763 23804774 23804780 23804707 23012953 23804720 23012954 23804711 23012950 23804702 23804703 23012951 23804705 23804704 23804713 23804977 23804721 23804712 23804708 23804696 23804698 23012949 23804697 23804662 23918494 23918495 23057408 23918492 23918493 23918504 23057383 23918434 23918435 23057384 23918438 23918436 23918437 23918407 23918411 23057374 23918412 23918413 23918414 23918363 23918357 23918359 23057352 23918360 23057353 23918353 23918352 23057367 23922565 23922562 23058992 23922559 23922554 23922552 23922551 23922550 23060056 23925277 23922491 23922489 23922476 23922475 23922473 23058959 23922480 23922472 23922481 23922451 23922452 23922453 23058945 23922440 23058947 23922441 23922443 23922442 23922431 23922432 23922445 23922447 23922951 23059148 23922952 23922909 23922908 23059131 23922911 23922855 23922724 23922723 23922716 23922740 23922739 23922738 23922736 23059060 23922735 23922731 23060598 23926664 23926660 23926659 23926652 23926651 23926656 23926658 23060593 23926663 23926670 23926607 23060573 23926611 23060574 23060586 23926615 23926614 23926620 23060578 23926625 23926624 23926627 23060580 23926628 23926567 23926566 23060760 23927089 23927090 23927088 23926574 23060759 23060762 23927096 23927100 23927099 23927113 23927107 23927115 23060771 23927114 23060757 23927067 23927066 23927070 23060752 23913970 23055642 23927073 23927058 23927051 23927032 23927028 23060736 23927057 23926332 23922465 23913864 23913863 23926877 23926876 23926878 23926888 23926887 23060682 23060683 23926893 23926892 23926952 23926895 23060685 23926896 23926894 23926890 23926900 23926899 23060688 23926908 23926907 23060691 23927002 23060690 23926846 23060666 23926844 23926843 23926845 23060673 23060670 23926855 23926813 23060653 23926798 23926796 23926797 23060647 23926792 23060643 23926786 23926780 23926781 23058874 23058872 23922256 23922252 23922244 23922245 23922228 23872052 23872051 23871417 23871416 23872056 23039262 23872045 23039261 23872044 23872046 23039267 23872047 23872048 23872054 23039265 23039269 23872229 23872248 23039336 23039328 23872209 23872211 23872222 23872223 23872224 23872207 23039326 23872206 23937534 23064839 23937496 23937497 23937498 23937536 23064843 23064830 23937502 23937515 23937514 23937513 23937478 23937477 23937476 23937474 23064819 23937441 23937442 23937443 23937444 23937469 23937470 23064817 23937463 23937461 23937460 23937459 23064800 23937415 23937414 23937416 23937417 23064797 23937409 23064793 23937408 23937406 23937405 23937392 23937393 23933632 23933633 23933595 23933504 23063269 23933507 23933596 23933506 23063303 23933509 23933508 23933513 23933512 23933447 23933446 23933448 23933451 23933454 23933455 23063248 23063250 23933343 23934166 23934175 23934176 23934177 23934178 23933390 23933389 23063222 23933388 23934169 23934473 23934172 23934171 23063530 23933140 23063125 23933137 23933139 23063124 23933136 23063123 23933187 23933184 23933145 23063127 23933146 22374939 21498716 21498717 21498720 20596908 22374941 20596886 21498683 21498685 20596887 21498687 20596889 20596891 20596890 21498690 22374951 21498735 20596919 22373274 21496208 21496244 21496210 22373275 21496240 22373276 21496212 20595093 22373280 20595092 21496218 21496236 20595081 22373260 21496182 20595076 21496191 20595073 22373262 21496187 20595071 22373258 20595068 21496178 21496173 20595065 22373250 22373246 21496166 21496167 20595059 21496172 20636531 20595049 22373239 20595048 21496156 21496170 22373247 20595046 21496155 22373238 21496157 21496171 21496158 22373232 21496144 21496145 20595039 21496146 21496058 20594982 21496131 21496086 20595010 21496088 21496129 22373194 21496082 21496083 20595030 22373223 21496125 22373199 20595003 21496121 20595000 21496090 21496095 22373193 20594995 20595006 20594994 21496097 20594999 22373197 21467941 21467940 20574786 22412113 20638466 22413910 20638471 20638470 20638472 22413909 20638473 21469403 20575858 21469400 20575340 22354282 21468010 21468696 21468695 20575339 21468692 21468690 22354746 21468693 20575338 22354591 21468464 20575169 21555387 21555385 22413077 20637558 21555344 22413076 21555343 22413075 20637555 21555340 21555325 22413074 22413069 21555328 21555320 22413064 21555322 22413065 20637536 21557640 21555290 20637521 21555289 21555286 20636847 20637516 22413037 21555284 20637515 20637509 21555277 20636837 22412403 20636827 21554325 20636826 21554260 21554242 22412346 21554241 20636758 20636761 21554230 21554174 22412298 21554173 21554166 21554165 20636709 20636707 21554161 22412283 20636701 21554148 21554149 21554140 20636695 21554142 22412281 21554141 20636696 22412280 22412279 21554139 22412203 21554026 20636612 20636570 21553968 22412150 21553951 22412154 22412164 20636550 21553931 20636547 21553982 20636585 22412170 21553944 22412171 22412174 20636589 22412177 21553992 21460331 22349166 21460302 22349162 21460327 21460330 20569315 22349164 21460301 21460300 20569284 22349138 20569273 22349126 21460270 21460269 20569244 21460238 22349101 21460242 22349104 20569250 22349105 20569251 22349115 20569266 22349116 22349117 21460262 21460264 22349168 21460333 21460332 22349167 21460675 20569557 22349400 20569558 21460677 22394978 21528476 22394980 20618292 21528475 20618291 21528552 20618350 22395089 22395092 22395093 21528642 21528643 20618412 21528644 22395096 21528648 20618414 21528647 20618411 21528633 20618407 22395087 21528632 20618406 21528631 20618402 21528625 21528627 22395078 22395077 20618396 20618393 22395072 22395064 21528603 20618382 21528577 21528576 20618364 22395048 21528575 20618366 22395050 21528578 21528496 22394998 20618310 21528498 22394999 20618311 21528504 20618314 22394863 20618165 22394862 21528295 20618164 21528296 22394883 14439941 14439942 13402982 14439937 15045873 14439729 13402781 14439720 15045782 14439923 13402978 14439934 13402969 13402968 13402960 13402959 14439915 13402963 14439917 14439919 13402943 15045861 15045862 13402946 14439899 14439916 13402962 15045855 14439878 13402925 14439876 15045868 13402957 13402764 13402756 14439694 13402688 14439619 13402685 14439614 13402683 13402684 14439615 14439658 14439656 14439605 14439601 14439602 13402669 14439596 14439586 15045722 14439635 13402650 15045719 13402645 13402565 15045680 13402567 13402879 13402878 14439824 14439798 14439797 13402854 14439796 15045817 15045818 13402856 14439799 15045819 14439800 14439802 14439801 13402858 14439816 13402861 13402860 14439807 15045821 14439805 15045810 13402840 13402847 15045809 13402838 14439778 15045807 14439437 13402466 15045635 14439402 14439762 15045802 14439765 13402824 15045803 14439764 15045643 15045637 13402470 13402423 14439356 14439357 14439348 14439346 14439345 13402415 14439347 14439350 13402418 13402409 13402410 15045624 13402441 13402442 13402437 13402402 15045605 14439335 13402397 13402398 13401633 14438540 13401661 14438579 14438532 14438531 14438571 15047126 14438570 14438539 13401660 14438537 15045258 14438548 14438549 13401625 13401626 15045249 14438525 15045238 13401620 14438524 14438523 14438522 13401615 13401616 13401614 13401611 13401612 14438563 13401598 15045228 14438547 14438545 14438544 14438542 13401635 14438512 14438511 15045232 14438486 13401605 13401604 13401606 15045222 13401581 14438483 13401579 14438480 13401548 13401547 14438449 13401575 14438476 15045223 13401572 13401573 13401529 13401530 13401493 14438385 13401492 15045184 14438395 13401506 14438389 14438388 13401512 13401532 13401531 14438432 13401534 13401533 14438369 14438349 14438348 14438351 13401461 14438376 15045174 15042792 14433124 14433099 14433098 13396438 15042781 13396439 14433101 13396437 13396436 13396463 14433096 13396377 15042751 15042778 14433089 13396430 14433032 14433031 15042753 13396378 14433033 14433034 15042752 13396376 14433030 14433029 13396375 13396150 15042643 14432790 15042599 14432691 15042602 14432697 14432783 14432696 14432695 15042601 13396058 14432690 13396161 13396052 15042596 13396047 14432676 15042590 13396040 14432668 15042589 14432666 14432665 13396031 15042584 13396027 15042582 13396018 14432646 14432642 14432636 14432635 15042573 14432623 13395997 15042568 14432620 14432617 13395991 13395990 13395992 14432612 15042564]