Advent of Code 2017, Day 12

aoc_2017_day12.py

INPUT = """0 <-> 454, 528, 621, 1023, 1199
1 <-> 1335, 1563, 1627, 1679
2 <-> 353, 689
3 <-> 3, 1171
4 <-> 1247
5 <-> 758, 928, 1260
6 <-> 1010
7 <-> 570
8 <-> 710, 1610
9 <-> 9
10 <-> 10, 1822
11 <-> 473
12 <-> 255, 1355, 1999
13 <-> 13, 1026
14 <-> 113
15 <-> 1954
16 <-> 679, 918
17 <-> 1101, 1637
18 <-> 574, 1037
19 <-> 481
20 <-> 22, 815, 963, 1031
21 <-> 1427
22 <-> 20, 316, 802
23 <-> 1328, 1447, 1708
24 <-> 446, 1677
25 <-> 25, 217
26 <-> 184, 1138
27 <-> 142
28 <-> 1340
29 <-> 954, 1174
30 <-> 1185
31 <-> 112, 1111
32 <-> 1851
33 <-> 662
34 <-> 848
35 <-> 315, 1983
36 <-> 239
37 <-> 422, 871, 1903
38 <-> 1450, 1497
39 <-> 923, 1652
40 <-> 201, 434
41 <-> 1878
42 <-> 192, 1233
43 <-> 1457
44 <-> 499, 961
45 <-> 1056
46 <-> 302
47 <-> 100, 1921
48 <-> 1532
49 <-> 728, 1028, 1201, 1301
50 <-> 1662
51 <-> 1186, 1773
52 <-> 228, 1168, 1873
53 <-> 413, 1111
54 <-> 956
55 <-> 477
56 <-> 98
57 <-> 1849, 1960
58 <-> 440
59 <-> 1115, 1389
60 <-> 358, 499, 1392, 1582
61 <-> 1704
62 <-> 425
63 <-> 1562, 1593
64 <-> 916
65 <-> 1842, 1951
66 <-> 1991
67 <-> 1026
68 <-> 711
69 <-> 854
70 <-> 114, 1591
71 <-> 1423
72 <-> 1403
73 <-> 170
74 <-> 508, 831
75 <-> 231, 1070, 1384, 1615
76 <-> 751
77 <-> 1190, 1421
78 <-> 78, 1593
79 <-> 221, 742, 1165
80 <-> 1517
81 <-> 1154
82 <-> 310, 1027, 1358
83 <-> 83, 1554
84 <-> 743, 1208
85 <-> 504, 1723
86 <-> 1630
87 <-> 919
88 <-> 794
89 <-> 1334
90 <-> 1997
91 <-> 494
92 <-> 1210
93 <-> 1619
94 <-> 324, 1183, 1876
95 <-> 300
96 <-> 127, 1849
97 <-> 733
98 <-> 56, 534
99 <-> 1028
100 <-> 47, 402
101 <-> 1053
102 <-> 201, 498, 1016
103 <-> 103, 1412
104 <-> 105
105 <-> 104, 608, 681
106 <-> 106, 1605
107 <-> 468, 1798
108 <-> 1810
109 <-> 789, 1300
110 <-> 348, 550
111 <-> 111
112 <-> 31
113 <-> 14, 136
114 <-> 70, 132, 183, 847
115 <-> 1086, 1409
116 <-> 1220
117 <-> 1047, 1886
118 <-> 729
119 <-> 119
120 <-> 198
121 <-> 1020, 1547
122 <-> 891, 1241
123 <-> 842, 866
124 <-> 124, 1676
125 <-> 1959
126 <-> 895
127 <-> 96
128 <-> 664, 1170
129 <-> 392, 1222
130 <-> 1483, 1744
131 <-> 1696
132 <-> 114
133 <-> 192
134 <-> 134
135 <-> 1696
136 <-> 113, 803, 1064
137 <-> 1738
138 <-> 1486
139 <-> 1811
140 <-> 663, 1355, 1832
141 <-> 226, 803
142 <-> 27, 417
143 <-> 486, 1441
144 <-> 768, 850
145 <-> 180, 669, 1935
146 <-> 1242
147 <-> 345, 1782
148 <-> 1295, 1710
149 <-> 1349
150 <-> 697
151 <-> 834
152 <-> 152, 365
153 <-> 654, 720
154 <-> 1396, 1538
155 <-> 804, 1891
156 <-> 653, 1679
157 <-> 302, 1108
158 <-> 415, 680, 1668
159 <-> 979, 1116, 1449
160 <-> 463, 1627, 1769
161 <-> 161, 232, 446, 874
162 <-> 162, 527
163 <-> 1760
164 <-> 259, 750
165 <-> 211, 945, 1022, 1069, 1071
166 <-> 293
167 <-> 178, 522
168 <-> 301, 408, 622
169 <-> 466, 1485, 1848
170 <-> 73, 1028, 1761
171 <-> 525, 755, 1219
172 <-> 313, 476, 1383
173 <-> 1629
174 <-> 1795, 1977
175 <-> 553, 1001
176 <-> 1330
177 <-> 375, 1013
178 <-> 167
179 <-> 1091, 1295
180 <-> 145, 979, 1151
181 <-> 803, 1107
182 <-> 805, 872, 1366, 1894
183 <-> 114, 685, 1252, 1508
184 <-> 26
185 <-> 402
186 <-> 1748
187 <-> 744, 971
188 <-> 504
189 <-> 814
190 <-> 948
191 <-> 506, 714
192 <-> 42, 133, 854, 1152, 1250
193 <-> 193
194 <-> 1960
195 <-> 382, 1551
196 <-> 1759
197 <-> 197
198 <-> 120, 1070
199 <-> 659, 1161
200 <-> 875, 1572, 1819
201 <-> 40, 102, 898, 1307
202 <-> 436
203 <-> 418, 771
204 <-> 1114, 1224
205 <-> 1011, 1979
206 <-> 206, 882
207 <-> 238
208 <-> 1681
209 <-> 1406
210 <-> 1376
211 <-> 165, 1153, 1916
212 <-> 677
213 <-> 915
214 <-> 1280
215 <-> 533
216 <-> 626, 731
217 <-> 25, 325
218 <-> 1338
219 <-> 596, 779
220 <-> 339
221 <-> 79, 620
222 <-> 775, 1144
223 <-> 439
224 <-> 1825
225 <-> 225
226 <-> 141, 311
227 <-> 1335
228 <-> 52, 1861
229 <-> 578, 727, 1085
230 <-> 1036
231 <-> 75, 766, 1386
232 <-> 161
233 <-> 953
234 <-> 891
235 <-> 1067
236 <-> 419
237 <-> 237
238 <-> 207, 1687
239 <-> 36, 1357
240 <-> 1602
241 <-> 241, 511, 960
242 <-> 888, 1498, 1556
243 <-> 1243, 1418, 1717
244 <-> 364, 753
245 <-> 643, 807
246 <-> 1653
247 <-> 1446, 1902
248 <-> 1164, 1743
249 <-> 645, 669
250 <-> 556
251 <-> 390, 1973
252 <-> 956
253 <-> 1149, 1574
254 <-> 560, 1454, 1826
255 <-> 12, 1214
256 <-> 314, 820, 1087
257 <-> 700, 1540, 1986
258 <-> 258
259 <-> 164
260 <-> 1274
261 <-> 1385
262 <-> 765
263 <-> 1231, 1509
264 <-> 586
265 <-> 586, 748, 1186
266 <-> 1046, 1418
267 <-> 877, 1572
268 <-> 1370, 1688, 1980
269 <-> 782, 1610
270 <-> 789, 1052, 1102
271 <-> 1787
272 <-> 1076
273 <-> 303, 1549
274 <-> 353
275 <-> 360
276 <-> 717
277 <-> 1955
278 <-> 876, 890, 1311, 1920
279 <-> 279, 515
280 <-> 292, 1067, 1345
281 <-> 1525, 1728
282 <-> 1211
283 <-> 1053
284 <-> 312, 1647
285 <-> 1534
286 <-> 1738
287 <-> 517, 1402
288 <-> 514
289 <-> 462, 915, 1401
290 <-> 700, 1428, 1834
291 <-> 1115, 1473
292 <-> 280, 1185
293 <-> 166, 564
294 <-> 320, 1906
295 <-> 850, 1276
296 <-> 1843
297 <-> 544
298 <-> 1208, 1399
299 <-> 577
300 <-> 95, 421, 794
301 <-> 168, 933
302 <-> 46, 157, 1844
303 <-> 273
304 <-> 496
305 <-> 1493
306 <-> 736, 1316, 1622
307 <-> 1495
308 <-> 1286, 1357
309 <-> 309, 1764
310 <-> 82
311 <-> 226
312 <-> 284, 514, 845, 1476
313 <-> 172, 361, 1663
314 <-> 256, 809
315 <-> 35, 1043
316 <-> 22
317 <-> 1418, 1643
318 <-> 404, 1032, 1452, 1534
319 <-> 841
320 <-> 294, 949
321 <-> 699, 925, 1274, 1700
322 <-> 458, 1124, 1549
323 <-> 323
324 <-> 94, 1425, 1655
325 <-> 217
326 <-> 843, 1994
327 <-> 327, 1556, 1952
328 <-> 405, 1081
329 <-> 329, 388
330 <-> 369, 1084, 1846
331 <-> 1700
332 <-> 1772, 1973
333 <-> 695, 1639
334 <-> 703, 932
335 <-> 335
336 <-> 668, 1005
337 <-> 702, 743
338 <-> 517
339 <-> 220, 339, 716, 773, 1132, 1924
340 <-> 362, 1841
341 <-> 885, 1034, 1325
342 <-> 360, 1446
343 <-> 343
344 <-> 1017
345 <-> 147, 1458
346 <-> 1089
347 <-> 925, 1774
348 <-> 110, 1282, 1884
349 <-> 551
350 <-> 1630
351 <-> 714
352 <-> 619, 1926
353 <-> 2, 274, 1824
354 <-> 1459, 1854
355 <-> 355
356 <-> 399, 1251, 1600
357 <-> 466, 1818, 1825
358 <-> 60, 358
359 <-> 570
360 <-> 275, 342, 1768
361 <-> 313, 361, 1303
362 <-> 340, 580, 747, 1433
363 <-> 1678
364 <-> 244, 494
365 <-> 152
366 <-> 874
367 <-> 367, 735, 1139
368 <-> 459
369 <-> 330
370 <-> 881
371 <-> 1133, 1213, 1438
372 <-> 1290, 1963
373 <-> 846, 1829
374 <-> 780, 996
375 <-> 177, 1126, 1223
376 <-> 474, 1467
377 <-> 1485, 1544
378 <-> 1105, 1815, 1895
379 <-> 507, 1936
380 <-> 529, 806, 1654
381 <-> 1306, 1606
382 <-> 195, 676, 736, 1268
383 <-> 383, 624, 1379
384 <-> 384, 856
385 <-> 1463
386 <-> 495, 629, 1578
387 <-> 836, 1670
388 <-> 329
389 <-> 488, 1477, 1866
390 <-> 251
391 <-> 391
392 <-> 129, 828, 1877
393 <-> 1436
394 <-> 1495
395 <-> 776, 879
396 <-> 793, 1298
397 <-> 523, 1192, 1693, 1712
398 <-> 398
399 <-> 356, 399, 1499
400 <-> 400, 1104
401 <-> 1039
402 <-> 100, 185, 1600
403 <-> 706, 1550
404 <-> 318, 1374, 1697
405 <-> 328, 1511
406 <-> 602, 905
407 <-> 407, 1910
408 <-> 168, 1120, 1584
409 <-> 1945
410 <-> 1763
411 <-> 1915
412 <-> 448, 1486
413 <-> 53, 681
414 <-> 414
415 <-> 158
416 <-> 848, 1051
417 <-> 142, 1717
418 <-> 203, 1226, 1537
419 <-> 236, 1144
420 <-> 1027, 1793
421 <-> 300, 671, 705
422 <-> 37
423 <-> 1013, 1607
424 <-> 424, 437, 1332
425 <-> 62, 774
426 <-> 426, 1359
427 <-> 1373
428 <-> 718
429 <-> 429, 1940
430 <-> 1410
431 <-> 554, 1941
432 <-> 1845
433 <-> 718, 1630
434 <-> 40, 1780
435 <-> 650
436 <-> 202, 1467, 1853
437 <-> 424
438 <-> 680, 1018, 1538
439 <-> 223, 1042, 1397
440 <-> 58, 1860
441 <-> 1138
442 <-> 640, 723, 1322
443 <-> 492, 958, 1736
444 <-> 444
445 <-> 533, 1530
446 <-> 24, 161, 1735, 1892, 1898
447 <-> 1998
448 <-> 412, 1266
449 <-> 972, 1397
450 <-> 732, 1147
451 <-> 1339, 1435, 1729
452 <-> 520
453 <-> 1810
454 <-> 0
455 <-> 1677
456 <-> 1915
457 <-> 1024, 1790
458 <-> 322
459 <-> 368, 1181
460 <-> 460
461 <-> 1181
462 <-> 289, 557, 1804
463 <-> 160
464 <-> 822, 1330
465 <-> 658
466 <-> 169, 357, 1248
467 <-> 467, 1278
468 <-> 107
469 <-> 1480
470 <-> 1503
471 <-> 1376, 1717
472 <-> 1835
473 <-> 11, 597
474 <-> 376, 687, 1478, 1730
475 <-> 701, 866
476 <-> 172
477 <-> 55, 1985
478 <-> 478
479 <-> 843, 1333, 1555
480 <-> 609, 712
481 <-> 19, 591, 1141
482 <-> 1698, 1883
483 <-> 664
484 <-> 1367, 1965
485 <-> 534, 1276
486 <-> 143, 1380, 1757
487 <-> 487
488 <-> 389
489 <-> 572
490 <-> 1053, 1465
491 <-> 840, 1074
492 <-> 443, 1728
493 <-> 631
494 <-> 91, 364
495 <-> 386, 1273, 1726, 1838
496 <-> 304, 772
497 <-> 572
498 <-> 102
499 <-> 44, 60
500 <-> 1078
501 <-> 642
502 <-> 561, 587, 686, 816, 1905
503 <-> 956, 1614
504 <-> 85, 188, 518, 790, 1891
505 <-> 1444
506 <-> 191
507 <-> 379, 1892
508 <-> 74, 1522
509 <-> 1429, 1863
510 <-> 510
511 <-> 241, 1797
512 <-> 1487
513 <-> 1280, 1997
514 <-> 288, 312, 1699
515 <-> 279, 1532
516 <-> 516, 1714
517 <-> 287, 338, 1364
518 <-> 504, 1852
519 <-> 762
520 <-> 452, 666, 1139
521 <-> 862, 1492
522 <-> 167, 616, 1644, 1956
523 <-> 397, 568
524 <-> 1038, 1896
525 <-> 171, 1239, 1847
526 <-> 1272, 1907
527 <-> 162, 1966
528 <-> 0, 1623
529 <-> 380
530 <-> 1479
531 <-> 1529
532 <-> 1085, 1939
533 <-> 215, 445, 1422, 1597
534 <-> 98, 485, 1337, 1960
535 <-> 880
536 <-> 1518
537 <-> 1009, 1274
538 <-> 1535, 1620
539 <-> 1971
540 <-> 540
541 <-> 565
542 <-> 1679
543 <-> 1374
544 <-> 297, 740
545 <-> 1461
546 <-> 546
547 <-> 547, 1019
548 <-> 1436
549 <-> 1589, 1980
550 <-> 110, 573
551 <-> 349, 1555
552 <-> 1725
553 <-> 175, 553, 1410
554 <-> 431, 776, 897
555 <-> 1859
556 <-> 250, 875
557 <-> 462, 998, 1124
558 <-> 1409
559 <-> 912
560 <-> 254
561 <-> 502, 561
562 <-> 1679
563 <-> 1299
564 <-> 293, 1259
565 <-> 541, 1312, 1441, 1913
566 <-> 1907
567 <-> 1159
568 <-> 523
569 <-> 1873
570 <-> 7, 359, 869
571 <-> 1752, 1779
572 <-> 489, 497, 811, 953
573 <-> 550
574 <-> 18, 1238
575 <-> 1771
576 <-> 1442, 1630
577 <-> 299, 1453
578 <-> 229, 1142, 1868
579 <-> 1878, 1977
580 <-> 362
581 <-> 1811
582 <-> 1675
583 <-> 765, 1632
584 <-> 983
585 <-> 1201
586 <-> 264, 265
587 <-> 502, 1680, 1968
588 <-> 616
589 <-> 1354, 1575
590 <-> 1106
591 <-> 481, 1179
592 <-> 1946
593 <-> 733, 1670
594 <-> 1129, 1271
595 <-> 1280
596 <-> 219, 1168
597 <-> 473, 876
598 <-> 1089
599 <-> 1334
600 <-> 1308
601 <-> 604, 870, 1817, 1946
602 <-> 406, 1369
603 <-> 1442
604 <-> 601
605 <-> 862
606 <-> 1355
607 <-> 1157
608 <-> 105
609 <-> 480, 756
610 <-> 1040, 1657
611 <-> 987, 1259
612 <-> 612, 1672
613 <-> 613, 1631
614 <-> 1602, 1795
615 <-> 646, 894
616 <-> 522, 588, 850
617 <-> 617, 1254
618 <-> 1352
619 <-> 352, 1855
620 <-> 221, 620
621 <-> 0
622 <-> 168, 1373
623 <-> 700
624 <-> 383
625 <-> 1321, 1343
626 <-> 216
627 <-> 1034
628 <-> 1271
629 <-> 386, 1172, 1973
630 <-> 1544, 1954
631 <-> 493, 1334
632 <-> 1375, 1491
633 <-> 1456
634 <-> 1982
635 <-> 924, 1054, 1617
636 <-> 825
637 <-> 1653
638 <-> 1098, 1321, 1404, 1790
639 <-> 639
640 <-> 442, 640, 1507
641 <-> 1519
642 <-> 501, 1401
643 <-> 245
644 <-> 714, 1348
645 <-> 249, 1329
646 <-> 615, 1733
647 <-> 1912
648 <-> 1598
649 <-> 933
650 <-> 435, 1895
651 <-> 1537
652 <-> 652, 1240, 1879
653 <-> 156, 1920
654 <-> 153, 1749
655 <-> 1248
656 <-> 700, 919, 1118, 1969
657 <-> 657, 1851
658 <-> 465, 1474
659 <-> 199, 818, 920
660 <-> 660
661 <-> 745
662 <-> 33, 1115, 1978
663 <-> 140, 1726
664 <-> 128, 483, 1780
665 <-> 1520
666 <-> 520
667 <-> 806
668 <-> 336, 934
669 <-> 145, 249, 1846
670 <-> 819, 1526, 1802
671 <-> 421
672 <-> 1870
673 <-> 931, 1018, 1211
674 <-> 1627
675 <-> 675
676 <-> 382, 819
677 <-> 212, 1163
678 <-> 733
679 <-> 16, 1149, 1402, 1959
680 <-> 158, 438, 886
681 <-> 105, 413, 1385
682 <-> 1309
683 <-> 1539
684 <-> 1034, 1520, 1801, 1927
685 <-> 183
686 <-> 502
687 <-> 474
688 <-> 786
689 <-> 2, 1671
690 <-> 1673, 1946
691 <-> 1732
692 <-> 1853
693 <-> 1230
694 <-> 694, 1823
695 <-> 333
696 <-> 1214
697 <-> 150, 697
698 <-> 1181
699 <-> 321, 1292, 1480
700 <-> 257, 290, 623, 656
701 <-> 475, 1205
702 <-> 337, 1597
703 <-> 334
704 <-> 912, 989, 1613
705 <-> 421, 849, 1215, 1270
706 <-> 403, 1648
707 <-> 1396
708 <-> 1081, 1687
709 <-> 1237
710 <-> 8, 826, 926, 1685
711 <-> 68, 711
712 <-> 480
713 <-> 1438, 1461, 1824, 1996
714 <-> 191, 351, 644
715 <-> 1058, 1875
716 <-> 339
717 <-> 276, 983, 1582, 1888
718 <-> 428, 433, 1227, 1239
719 <-> 1339, 1341
720 <-> 153, 1101, 1411
721 <-> 754, 878, 1794
722 <-> 1255, 1862
723 <-> 442, 760, 896
724 <-> 1033
725 <-> 1115
726 <-> 825, 1562
727 <-> 229, 994
728 <-> 49, 752, 947, 1589
729 <-> 118, 759, 985, 1070, 1760
730 <-> 1072
731 <-> 216, 1755
732 <-> 450, 1264
733 <-> 97, 593, 678, 1259
734 <-> 1099, 1531, 1811
735 <-> 367, 1586
736 <-> 306, 382, 1625
737 <-> 1886
738 <-> 1991
739 <-> 1684, 1827
740 <-> 544, 1539, 1694, 1737
741 <-> 741
742 <-> 79
743 <-> 84, 337, 743
744 <-> 187, 1992
745 <-> 661, 1266, 1856
746 <-> 1674
747 <-> 362, 1383
748 <-> 265, 1429
749 <-> 1299
750 <-> 164, 1216, 1336, 1469, 1734
751 <-> 76, 1011
752 <-> 728
753 <-> 244, 803
754 <-> 721, 1890
755 <-> 171
756 <-> 609, 1470, 1934
757 <-> 1098, 1885
758 <-> 5
759 <-> 729, 1092, 1363
760 <-> 723, 946
761 <-> 1321, 1704
762 <-> 519, 1317, 1776
763 <-> 1693
764 <-> 1093
765 <-> 262, 583, 1250, 1545, 1642
766 <-> 231
767 <-> 835, 1395
768 <-> 144
769 <-> 984
770 <-> 1232
771 <-> 203
772 <-> 496, 1437
773 <-> 339
774 <-> 425, 774, 1015
775 <-> 222
776 <-> 395, 554
777 <-> 1278
778 <-> 778, 991, 1062
779 <-> 219, 1993
780 <-> 374
781 <-> 917, 1716, 1929, 1962
782 <-> 269
783 <-> 1381
784 <-> 1075, 1790, 1965
785 <-> 914, 1504
786 <-> 688, 1319, 1440, 1771, 1981
787 <-> 1161, 1750
788 <-> 1279, 1632
789 <-> 109, 270, 853, 865, 1806, 1840
790 <-> 504
791 <-> 791
792 <-> 1041
793 <-> 396, 1562, 1827
794 <-> 88, 300, 817
795 <-> 956
796 <-> 1323, 1816
797 <-> 921, 1331
798 <-> 1621
799 <-> 1871
800 <-> 800
801 <-> 1608, 1823
802 <-> 22, 1326
803 <-> 136, 141, 181, 753, 1082, 1374
804 <-> 155, 1252, 1487
805 <-> 182
806 <-> 380, 667, 1623
807 <-> 245, 844, 1564, 1567, 1724
808 <-> 1193
809 <-> 314, 1033, 1333
810 <-> 1643
811 <-> 572
812 <-> 812, 1681, 1799
813 <-> 1726
814 <-> 189, 1861, 1912
815 <-> 20, 939
816 <-> 502
817 <-> 794
818 <-> 659, 1488
819 <-> 670, 676
820 <-> 256
821 <-> 821
822 <-> 464, 997, 1338
823 <-> 823
824 <-> 1016
825 <-> 636, 726, 1988
826 <-> 710, 1060, 1576
827 <-> 1027, 1214
828 <-> 392
829 <-> 829
830 <-> 1504, 1532
831 <-> 74
832 <-> 1730
833 <-> 944, 1778, 1980
834 <-> 151, 862
835 <-> 767, 1755
836 <-> 387, 1202, 1256
837 <-> 871, 1233
838 <-> 1028, 1246
839 <-> 1158, 1468
840 <-> 491
841 <-> 319, 841
842 <-> 123, 1759
843 <-> 326, 479
844 <-> 807
845 <-> 312
846 <-> 373, 1541, 1550
847 <-> 114, 1533, 1614
848 <-> 34, 416, 1116, 1391
849 <-> 705, 870
850 <-> 144, 295, 616, 1466, 1746
851 <-> 1169, 1329
852 <-> 1796, 1912
853 <-> 789
854 <-> 69, 192
855 <-> 1089
856 <-> 384, 1007
857 <-> 1720
858 <-> 1338
859 <-> 1338, 1822
860 <-> 1028, 1334
861 <-> 1093, 1457, 1552
862 <-> 521, 605, 834, 1309, 1903
863 <-> 1232, 1960
864 <-> 1823
865 <-> 789, 1299
866 <-> 123, 475, 1543
867 <-> 945, 1573
868 <-> 1569
869 <-> 570, 1035
870 <-> 601, 849
871 <-> 37, 837, 1786
872 <-> 182, 979
873 <-> 1146, 1220
874 <-> 161, 366, 1439
875 <-> 200, 556
876 <-> 278, 597, 1148
877 <-> 267
878 <-> 721, 1678, 1709
879 <-> 395
880 <-> 535, 1459
881 <-> 370, 1481, 1643
882 <-> 206, 1374, 1970
883 <-> 1948
884 <-> 884
885 <-> 341, 1664
886 <-> 680, 1217, 1515
887 <-> 887
888 <-> 242
889 <-> 1972
890 <-> 278
891 <-> 122, 234, 962, 1762
892 <-> 1845
893 <-> 1692
894 <-> 615, 1365
895 <-> 126, 1948
896 <-> 723, 965, 1002
897 <-> 554, 897
898 <-> 201, 1767
899 <-> 1127, 1723, 1929
900 <-> 1100, 1956
901 <-> 1099, 1919
902 <-> 1428
903 <-> 1416
904 <-> 1062
905 <-> 406, 1991
906 <-> 1253
907 <-> 1616
908 <-> 1744
909 <-> 1261, 1824
910 <-> 1773
911 <-> 1340
912 <-> 559, 704, 1289, 1369
913 <-> 1420
914 <-> 785
915 <-> 213, 289
916 <-> 64, 1481
917 <-> 781
918 <-> 16, 1304
919 <-> 87, 656
920 <-> 659, 950
921 <-> 797, 1755
922 <-> 1274, 1635
923 <-> 39
924 <-> 635
925 <-> 321, 347
926 <-> 710, 926
927 <-> 1393, 1666
928 <-> 5, 1981
929 <-> 1570
930 <-> 1864
931 <-> 673, 1245
932 <-> 334, 1203, 1642
933 <-> 301, 649, 1164
934 <-> 668, 1047, 1540, 1887
935 <-> 1617
936 <-> 1187
937 <-> 937, 1353
938 <-> 949, 1913
939 <-> 815
940 <-> 1649
941 <-> 941
942 <-> 1125
943 <-> 943, 1404
944 <-> 833, 1112
945 <-> 165, 867, 964
946 <-> 760
947 <-> 728, 1596
948 <-> 190
949 <-> 320, 938, 1931
950 <-> 920, 1992
951 <-> 1590
952 <-> 1422
953 <-> 233, 572, 1127
954 <-> 29, 1074
955 <-> 1672
956 <-> 54, 252, 503, 795
957 <-> 995
958 <-> 443, 1275
959 <-> 966
960 <-> 241, 1297, 1641, 1839
961 <-> 44, 1050
962 <-> 891
963 <-> 20, 1144, 1875
964 <-> 945, 1623
965 <-> 896, 1768
966 <-> 959, 1394
967 <-> 1155
968 <-> 1154, 1609
969 <-> 1652, 1738
970 <-> 970
971 <-> 187
972 <-> 449, 1135, 1707
973 <-> 1029
974 <-> 1267
975 <-> 1587, 1928
976 <-> 1248
977 <-> 977, 1932
978 <-> 1906
979 <-> 159, 180, 872, 1218, 1560
980 <-> 1086, 1830
981 <-> 1426, 1689
982 <-> 1671
983 <-> 584, 717, 1408
984 <-> 769, 1121
985 <-> 729, 1344
986 <-> 1486
987 <-> 611
988 <-> 988, 1800
989 <-> 704
990 <-> 1398
991 <-> 778
992 <-> 992
993 <-> 1537
994 <-> 727
995 <-> 957, 1909
996 <-> 374, 1848
997 <-> 822, 1159
998 <-> 557, 1691
999 <-> 1393
1000 <-> 1083
1001 <-> 175, 1528
1002 <-> 896
1003 <-> 1003
1004 <-> 1828, 1846, 1859
1005 <-> 336
1006 <-> 1871
1007 <-> 856, 1362
1008 <-> 1256, 1514, 1835
1009 <-> 537, 1646
1010 <-> 6, 1232
1011 <-> 205, 751, 1976
1012 <-> 1964
1013 <-> 177, 423
1014 <-> 1123
1015 <-> 774, 1944
1016 <-> 102, 824, 1557, 1912
1017 <-> 344, 1017, 1113, 1649
1018 <-> 438, 673, 1962
1019 <-> 547
1020 <-> 121, 1020
1021 <-> 1909
1022 <-> 165
1023 <-> 0, 1601
1024 <-> 457
1025 <-> 1372, 1699
1026 <-> 13, 67
1027 <-> 82, 420, 827, 1383, 1686
1028 <-> 49, 99, 170, 838, 860, 1961
1029 <-> 973, 1029
1030 <-> 1174
1031 <-> 20, 1496, 1766, 1951
1032 <-> 318, 1108
1033 <-> 724, 809, 1917
1034 <-> 341, 627, 684, 1269
1035 <-> 869, 1061
1036 <-> 230, 1181, 1522
1037 <-> 18, 1470
1038 <-> 524, 1038, 1445, 1561
1039 <-> 401, 1972
1040 <-> 610
1041 <-> 792, 1041, 1787
1042 <-> 439, 1853
1043 <-> 315
1044 <-> 1549, 1570, 1957
1045 <-> 1719
1046 <-> 266
1047 <-> 117, 934
1048 <-> 1468
1049 <-> 1078, 1568, 1755
1050 <-> 961
1051 <-> 416
1052 <-> 270
1053 <-> 101, 283, 490, 1490
1054 <-> 635, 1231
1055 <-> 1061, 1260
1056 <-> 45, 1056
1057 <-> 1945
1058 <-> 715
1059 <-> 1933
1060 <-> 826
1061 <-> 1035, 1055
1062 <-> 778, 904
1063 <-> 1496, 1502, 1666
1064 <-> 136, 1943
1065 <-> 1979
1066 <-> 1171
1067 <-> 235, 280, 1657
1068 <-> 1068
1069 <-> 165
1070 <-> 75, 198, 729
1071 <-> 165
1072 <-> 730, 1224, 1456
1073 <-> 1073
1074 <-> 491, 954, 1979
1075 <-> 784, 1739
1076 <-> 272, 1617
1077 <-> 1636
1078 <-> 500, 1049, 1285
1079 <-> 1770
1080 <-> 1103, 1472
1081 <-> 328, 708, 1803
1082 <-> 803
1083 <-> 1000, 1803
1084 <-> 330
1085 <-> 229, 532
1086 <-> 115, 980, 1086
1087 <-> 256, 1351, 1933
1088 <-> 1088, 1872
1089 <-> 346, 598, 855, 1840
1090 <-> 1193
1091 <-> 179
1092 <-> 759
1093 <-> 764, 861, 1406
1094 <-> 1094
1095 <-> 1128, 1398
1096 <-> 1477
1097 <-> 1673
1098 <-> 638, 757, 1364
1099 <-> 734, 901
1100 <-> 900
1101 <-> 17, 720
1102 <-> 270
1103 <-> 1080, 1103, 1394
1104 <-> 400, 1720
1105 <-> 378, 1515
1106 <-> 590, 1782
1107 <-> 181
1108 <-> 157, 1032
1109 <-> 1799
1110 <-> 1251
1111 <-> 31, 53, 1541
1112 <-> 944
1113 <-> 1017
1114 <-> 204
1115 <-> 59, 291, 662, 725, 1616, 1617
1116 <-> 159, 848
1117 <-> 1176
1118 <-> 656
1119 <-> 1461
1120 <-> 408
1121 <-> 984, 1436, 1518
1122 <-> 1573, 1774
1123 <-> 1014, 1606, 1678
1124 <-> 322, 557
1125 <-> 942, 1378, 1760
1126 <-> 375, 1516, 1914
1127 <-> 899, 953
1128 <-> 1095, 1907
1129 <-> 594, 1676
1130 <-> 1774
1131 <-> 1131, 1516
1132 <-> 339, 1421
1133 <-> 371
1134 <-> 1227, 1669
1135 <-> 972
1136 <-> 1136, 1163
1137 <-> 1654
1138 <-> 26, 441, 1361, 1593
1139 <-> 367, 520, 1140
1140 <-> 1139
1141 <-> 481, 1141
1142 <-> 578
1143 <-> 1980
1144 <-> 222, 419, 963
1145 <-> 1145
1146 <-> 873, 1273
1147 <-> 450, 1686
1148 <-> 876, 1690
1149 <-> 253, 679
1150 <-> 1276
1151 <-> 180
1152 <-> 192, 1284
1153 <-> 211, 1529
1154 <-> 81, 968
1155 <-> 967, 1205, 1954
1156 <-> 1637
1157 <-> 607, 1452
1158 <-> 839
1159 <-> 567, 997
1160 <-> 1160, 1541
1161 <-> 199, 787
1162 <-> 1880
1163 <-> 677, 1136
1164 <-> 248, 933, 1667
1165 <-> 79, 1313
1166 <-> 1636
1167 <-> 1810
1168 <-> 52, 596, 1277
1169 <-> 851
1170 <-> 128, 1650
1171 <-> 3, 1066
1172 <-> 629
1173 <-> 1537
1174 <-> 29, 1030, 1175
1175 <-> 1174
1176 <-> 1117, 1385
1177 <-> 1875
1178 <-> 1887
1179 <-> 591, 1191
1180 <-> 1569, 1743
1181 <-> 459, 461, 698, 1036
1182 <-> 1652
1183 <-> 94, 1724, 1734, 1974
1184 <-> 1184
1185 <-> 30, 292, 1308, 1625
1186 <-> 51, 265, 1186, 1963, 1972
1187 <-> 936, 1187
1188 <-> 1494
1189 <-> 1360, 1876
1190 <-> 77
1191 <-> 1179
1192 <-> 397
1193 <-> 808, 1090, 1619
1194 <-> 1194
1195 <-> 1195
1196 <-> 1957
1197 <-> 1263
1198 <-> 1198
1199 <-> 0
1200 <-> 1200
1201 <-> 49, 585, 1201, 1557, 1890
1202 <-> 836
1203 <-> 932
1204 <-> 1911
1205 <-> 701, 1155, 1350
1206 <-> 1228, 1318, 1665
1207 <-> 1373, 1741
1208 <-> 84, 298
1209 <-> 1485
1210 <-> 92, 1626, 1775
1211 <-> 282, 673
1212 <-> 1807
1213 <-> 371
1214 <-> 255, 696, 827
1215 <-> 705, 1378
1216 <-> 750, 1538
1217 <-> 886
1218 <-> 979, 1523
1219 <-> 171
1220 <-> 116, 873
1221 <-> 1553, 1827
1222 <-> 129
1223 <-> 375
1224 <-> 204, 1072, 1660, 1757
1225 <-> 1661, 1683, 1812
1226 <-> 418
1227 <-> 718, 1134
1228 <-> 1206, 1490
1229 <-> 1237
1230 <-> 693, 1274, 1826
1231 <-> 263, 1054, 1424
1232 <-> 770, 863, 1010
1233 <-> 42, 837
1234 <-> 1342
1235 <-> 1235
1236 <-> 1805, 1881
1237 <-> 709, 1229, 1390, 1589, 1590
1238 <-> 574
1239 <-> 525, 718
1240 <-> 652
1241 <-> 122
1242 <-> 146, 1473
1243 <-> 243
1244 <-> 1244
1245 <-> 931, 1282
1246 <-> 838
1247 <-> 4, 1662, 1679
1248 <-> 466, 655, 976
1249 <-> 1588
1250 <-> 192, 765
1251 <-> 356, 1110
1252 <-> 183, 804
1253 <-> 906, 1842
1254 <-> 617
1255 <-> 722, 1255
1256 <-> 836, 1008
1257 <-> 1437
1258 <-> 1587
1259 <-> 564, 611, 733
1260 <-> 5, 1055
1261 <-> 909
1262 <-> 1912
1263 <-> 1197, 1513
1264 <-> 732, 1453
1265 <-> 1864
1266 <-> 448, 745, 1266
1267 <-> 974, 1267, 1637, 1807
1268 <-> 382
1269 <-> 1034
1270 <-> 705
1271 <-> 594, 628
1272 <-> 526
1273 <-> 495, 1146
1274 <-> 260, 321, 537, 922, 1230
1275 <-> 958
1276 <-> 295, 485, 1150
1277 <-> 1168
1278 <-> 467, 777
1279 <-> 788
1280 <-> 214, 513, 595, 1377, 1971
1281 <-> 1658, 1812
1282 <-> 348, 1245, 1978
1283 <-> 1669
1284 <-> 1152
1285 <-> 1078, 1867
1286 <-> 308, 1352
1287 <-> 1560
1288 <-> 1674, 1749
1289 <-> 912
1290 <-> 372, 1689
1291 <-> 1495
1292 <-> 699
1293 <-> 1381, 1432, 1565, 1669
1294 <-> 1926
1295 <-> 148, 179, 1788, 1901
1296 <-> 1296
1297 <-> 960
1298 <-> 396
1299 <-> 563, 749, 865, 1733, 1882
1300 <-> 109, 1423
1301 <-> 49
1302 <-> 1664
1303 <-> 361
1304 <-> 918, 1848
1305 <-> 1376, 1659
1306 <-> 381, 1482, 1638
1307 <-> 201
1308 <-> 600, 1185
1309 <-> 682, 862
1310 <-> 1310, 1857
1311 <-> 278
1312 <-> 565
1313 <-> 1165
1314 <-> 1357, 1816
1315 <-> 1315
1316 <-> 306, 1417
1317 <-> 762, 1730
1318 <-> 1206
1319 <-> 786, 1489
1320 <-> 1723
1321 <-> 625, 638, 761
1322 <-> 442
1323 <-> 796, 1594, 1953
1324 <-> 1755
1325 <-> 341
1326 <-> 802, 1864
1327 <-> 1327
1328 <-> 23, 1513
1329 <-> 645, 851, 1682
1330 <-> 176, 464
1331 <-> 797, 1913
1332 <-> 424
1333 <-> 479, 809
1334 <-> 89, 599, 631, 860, 1493
1335 <-> 1, 227
1336 <-> 750
1337 <-> 534
1338 <-> 218, 822, 858, 859
1339 <-> 451, 719
1340 <-> 28, 911, 1958
1341 <-> 719
1342 <-> 1234, 1417
1343 <-> 625
1344 <-> 985
1345 <-> 280
1346 <-> 1758
1347 <-> 1347
1348 <-> 644, 1907, 1927
1349 <-> 149, 1882
1350 <-> 1205, 1755
1351 <-> 1087
1352 <-> 618, 1286, 1837
1353 <-> 937
1354 <-> 589, 1909
1355 <-> 12, 140, 606, 1646
1356 <-> 1590
1357 <-> 239, 308, 1314, 1990
1358 <-> 82
1359 <-> 426
1360 <-> 1189
1361 <-> 1138
1362 <-> 1007
1363 <-> 759
1364 <-> 517, 1098
1365 <-> 894
1366 <-> 182, 1366
1367 <-> 484
1368 <-> 1765, 1963
1369 <-> 602, 912
1370 <-> 268
1371 <-> 1877
1372 <-> 1025
1373 <-> 427, 622, 1207
1374 <-> 404, 543, 803, 882
1375 <-> 632, 1414
1376 <-> 210, 471, 1305
1377 <-> 1280
1378 <-> 1125, 1215
1379 <-> 383
1380 <-> 486
1381 <-> 783, 1293
1382 <-> 1382
1383 <-> 172, 747, 1027
1384 <-> 75
1385 <-> 261, 681, 1176, 1651
1386 <-> 231
1387 <-> 1387
1388 <-> 1565
1389 <-> 59
1390 <-> 1237
1391 <-> 848
1392 <-> 60
1393 <-> 927, 999
1394 <-> 966, 1103
1395 <-> 767
1396 <-> 154, 707
1397 <-> 439, 449, 1479, 1782
1398 <-> 990, 1095, 1945
1399 <-> 298
1400 <-> 1907
1401 <-> 289, 642
1402 <-> 287, 679
1403 <-> 72, 1624
1404 <-> 638, 943
1405 <-> 1572
1406 <-> 209, 1093, 1707
1407 <-> 1496, 1618
1408 <-> 983
1409 <-> 115, 558, 1805
1410 <-> 430, 553
1411 <-> 720
1412 <-> 103
1413 <-> 1733
1414 <-> 1375, 1796
1415 <-> 1601
1416 <-> 903, 1718, 1971
1417 <-> 1316, 1342, 1626
1418 <-> 243, 266, 317, 1418, 1468, 1505
1419 <-> 1419
1420 <-> 913, 1836
1421 <-> 77, 1132, 1502
1422 <-> 533, 952
1423 <-> 71, 1300, 1947
1424 <-> 1231
1425 <-> 324
1426 <-> 981
1427 <-> 21, 1575, 1696, 1798
1428 <-> 290, 902, 1581
1429 <-> 509, 748
1430 <-> 1430
1431 <-> 1967
1432 <-> 1293
1433 <-> 362, 1922
1434 <-> 1486
1435 <-> 451, 1779
1436 <-> 393, 548, 1121, 1514
1437 <-> 772, 1257, 1462, 1493
1438 <-> 371, 713, 1557
1439 <-> 874
1440 <-> 786
1441 <-> 143, 565, 1629
1442 <-> 576, 603
1443 <-> 1445
1444 <-> 505, 1444, 1703
1445 <-> 1038, 1443
1446 <-> 247, 342
1447 <-> 23
1448 <-> 1935
1449 <-> 159
1450 <-> 38, 1450
1451 <-> 1528, 1817
1452 <-> 318, 1157, 1633
1453 <-> 577, 1264
1454 <-> 254
1455 <-> 1487
1456 <-> 633, 1072
1457 <-> 43, 861
1458 <-> 345, 1858
1459 <-> 354, 880
1460 <-> 1718
1461 <-> 545, 713, 1119
1462 <-> 1437
1463 <-> 385, 1886, 1995
1464 <-> 1862
1465 <-> 490
1466 <-> 850
1467 <-> 376, 436, 1991
1468 <-> 839, 1048, 1418, 1558, 1792
1469 <-> 750
1470 <-> 756, 1037
1471 <-> 1878
1472 <-> 1080, 1571
1473 <-> 291, 1242
1474 <-> 658, 1482
1475 <-> 1930
1476 <-> 312
1477 <-> 389, 1096
1478 <-> 474, 1588
1479 <-> 530, 1397
1480 <-> 469, 699
1481 <-> 881, 916
1482 <-> 1306, 1474
1483 <-> 130
1484 <-> 1558, 1877
1485 <-> 169, 377, 1209, 1647
1486 <-> 138, 412, 986, 1434
1487 <-> 512, 804, 1455
1488 <-> 818
1489 <-> 1319, 1489
1490 <-> 1053, 1228, 1490
1491 <-> 632
1492 <-> 521, 1566
1493 <-> 305, 1334, 1437, 1620, 1732
1494 <-> 1188, 1600
1495 <-> 307, 394, 1291, 1495
1496 <-> 1031, 1063, 1407
1497 <-> 38
1498 <-> 242
1499 <-> 399
1500 <-> 1998
1501 <-> 1557
1502 <-> 1063, 1421
1503 <-> 470, 1503
1504 <-> 785, 830
1505 <-> 1418
1506 <-> 1723, 1958
1507 <-> 640
1508 <-> 183
1509 <-> 263
1510 <-> 1642
1511 <-> 405
1512 <-> 1697
1513 <-> 1263, 1328
1514 <-> 1008, 1436
1515 <-> 886, 1105
1516 <-> 1126, 1131
1517 <-> 80, 1850
1518 <-> 536, 1121
1519 <-> 641, 1809
1520 <-> 665, 684
1521 <-> 1521
1522 <-> 508, 1036, 1593
1523 <-> 1218
1524 <-> 1747
1525 <-> 281, 1525
1526 <-> 670
1527 <-> 1527
1528 <-> 1001, 1451
1529 <-> 531, 1153
1530 <-> 445
1531 <-> 734
1532 <-> 48, 515, 830
1533 <-> 847, 1549
1534 <-> 285, 318
1535 <-> 538
1536 <-> 1742
1537 <-> 418, 651, 993, 1173, 1999
1538 <-> 154, 438, 1216, 1693
1539 <-> 683, 740, 1539, 1982
1540 <-> 257, 934
1541 <-> 846, 1111, 1160, 1758
1542 <-> 1612
1543 <-> 866
1544 <-> 377, 630
1545 <-> 765
1546 <-> 1907
1547 <-> 121, 1938
1548 <-> 1548
1549 <-> 273, 322, 1044, 1533
1550 <-> 403, 846
1551 <-> 195, 1915
1552 <-> 861, 1865
1553 <-> 1221
1554 <-> 83
1555 <-> 479, 551
1556 <-> 242, 327
1557 <-> 1016, 1201, 1438, 1501
1558 <-> 1468, 1484
1559 <-> 1618
1560 <-> 979, 1287
1561 <-> 1038
1562 <-> 63, 726, 793
1563 <-> 1, 1563, 1634
1564 <-> 807
1565 <-> 1293, 1388
1566 <-> 1492
1567 <-> 807, 1594
1568 <-> 1049
1569 <-> 868, 1180
1570 <-> 929, 1044, 1833
1571 <-> 1472
1572 <-> 200, 267, 1405
1573 <-> 867, 1122
1574 <-> 253
1575 <-> 589, 1427, 1622, 1705
1576 <-> 826
1577 <-> 1780
1578 <-> 386
1579 <-> 1579
1580 <-> 1699
1581 <-> 1428
1582 <-> 60, 717
1583 <-> 1583
1584 <-> 408
1585 <-> 1585
1586 <-> 735
1587 <-> 975, 1258, 1587, 1619
1588 <-> 1249, 1478
1589 <-> 549, 728, 1237
1590 <-> 951, 1237, 1356
1591 <-> 70, 1639
1592 <-> 1592, 1992
1593 <-> 63, 78, 1138, 1522
1594 <-> 1323, 1567
1595 <-> 1966
1596 <-> 947
1597 <-> 533, 702
1598 <-> 648, 1615
1599 <-> 1622, 1694
1600 <-> 356, 402, 1494
1601 <-> 1023, 1415
1602 <-> 240, 614, 1813, 1925
1603 <-> 1645
1604 <-> 1969
1605 <-> 106
1606 <-> 381, 1123
1607 <-> 423
1608 <-> 801
1609 <-> 968, 1684
1610 <-> 8, 269
1611 <-> 1840
1612 <-> 1542, 1933
1613 <-> 704, 1725
1614 <-> 503, 847
1615 <-> 75, 1598
1616 <-> 907, 1115
1617 <-> 635, 935, 1076, 1115
1618 <-> 1407, 1559
1619 <-> 93, 1193, 1587
1620 <-> 538, 1493
1621 <-> 798, 1672, 1911
1622 <-> 306, 1575, 1599
1623 <-> 528, 806, 964
1624 <-> 1403, 1989
1625 <-> 736, 1185
1626 <-> 1210, 1417
1627 <-> 1, 160, 674
1628 <-> 1844
1629 <-> 173, 1441, 1930
1630 <-> 86, 350, 433, 576
1631 <-> 613
1632 <-> 583, 788
1633 <-> 1452
1634 <-> 1563
1635 <-> 922
1636 <-> 1077, 1166, 1636
1637 <-> 17, 1156, 1267
1638 <-> 1306
1639 <-> 333, 1591
1640 <-> 1640
1641 <-> 960
1642 <-> 765, 932, 1510
1643 <-> 317, 810, 881
1644 <-> 522
1645 <-> 1603, 1719
1646 <-> 1009, 1355
1647 <-> 284, 1485
1648 <-> 706, 1785
1649 <-> 940, 1017
1650 <-> 1170
1651 <-> 1385
1652 <-> 39, 969, 1182, 1652
1653 <-> 246, 637, 1919
1654 <-> 380, 1137, 1923
1655 <-> 324
1656 <-> 1986
1657 <-> 610, 1067
1658 <-> 1281
1659 <-> 1305
1660 <-> 1224, 1869
1661 <-> 1225
1662 <-> 50, 1247
1663 <-> 313
1664 <-> 885, 1302, 1870
1665 <-> 1206
1666 <-> 927, 1063, 1903
1667 <-> 1164
1668 <-> 158, 1989
1669 <-> 1134, 1283, 1293, 1669
1670 <-> 387, 593, 1884
1671 <-> 689, 982
1672 <-> 612, 955, 1621
1673 <-> 690, 1097
1674 <-> 746, 1288
1675 <-> 582, 1675
1676 <-> 124, 1129
1677 <-> 24, 455, 1979
1678 <-> 363, 878, 1123
1679 <-> 1, 156, 542, 562, 1247
1680 <-> 587
1681 <-> 208, 812
1682 <-> 1329
1683 <-> 1225
1684 <-> 739, 1609
1685 <-> 710
1686 <-> 1027, 1147, 1939
1687 <-> 238, 708, 1740
1688 <-> 268
1689 <-> 981, 1290, 1814
1690 <-> 1148
1691 <-> 998
1692 <-> 893, 1862
1693 <-> 397, 763, 1538
1694 <-> 740, 1599
1695 <-> 1695
1696 <-> 131, 135, 1427
1697 <-> 404, 1512
1698 <-> 482, 1930
1699 <-> 514, 1025, 1580
1700 <-> 321, 331, 1945
1701 <-> 1749
1702 <-> 1702
1703 <-> 1444
1704 <-> 61, 761
1705 <-> 1575
1706 <-> 1706
1707 <-> 972, 1406
1708 <-> 23, 1791
1709 <-> 878
1710 <-> 148
1711 <-> 1848
1712 <-> 397
1713 <-> 1899
1714 <-> 516, 1860
1715 <-> 1715
1716 <-> 781
1717 <-> 243, 417, 471
1718 <-> 1416, 1460, 1785
1719 <-> 1045, 1645, 1719
1720 <-> 857, 1104
1721 <-> 1971
1722 <-> 1742, 1998
1723 <-> 85, 899, 1320, 1506
1724 <-> 807, 1183
1725 <-> 552, 1613
1726 <-> 495, 663, 813
1727 <-> 1727
1728 <-> 281, 492
1729 <-> 451
1730 <-> 474, 832, 1317
1731 <-> 1858
1732 <-> 691, 1493
1733 <-> 646, 1299, 1413, 1733
1734 <-> 750, 1183
1735 <-> 446
1736 <-> 443
1737 <-> 740
1738 <-> 137, 286, 969
1739 <-> 1075
1740 <-> 1687, 1942
1741 <-> 1207
1742 <-> 1536, 1722, 1742
1743 <-> 248, 1180, 1743
1744 <-> 130, 908, 1744
1745 <-> 1745
1746 <-> 850
1747 <-> 1524, 1747
1748 <-> 186, 1748
1749 <-> 654, 1288, 1701, 1871
1750 <-> 787
1751 <-> 1751
1752 <-> 571
1753 <-> 1753
1754 <-> 1754
1755 <-> 731, 835, 921, 1049, 1324, 1350
1756 <-> 1935
1757 <-> 486, 1224
1758 <-> 1346, 1541
1759 <-> 196, 842
1760 <-> 163, 729, 1125
1761 <-> 170
1762 <-> 891
1763 <-> 410, 1763
1764 <-> 309
1765 <-> 1368
1766 <-> 1031
1767 <-> 898, 1955
1768 <-> 360, 965
1769 <-> 160
1770 <-> 1079, 1868
1771 <-> 575, 786
1772 <-> 332
1773 <-> 51, 910
1774 <-> 347, 1122, 1130
1775 <-> 1210
1776 <-> 762, 1776
1777 <-> 1948
1778 <-> 833
1779 <-> 571, 1435, 1779
1780 <-> 434, 664, 1577
1781 <-> 1958
1782 <-> 147, 1106, 1397
1783 <-> 1846
1784 <-> 1784, 1866
1785 <-> 1648, 1718, 1937
1786 <-> 871
1787 <-> 271, 1041
1788 <-> 1295, 1962
1789 <-> 1789
1790 <-> 457, 638, 784
1791 <-> 1708, 1791
1792 <-> 1468
1793 <-> 420
1794 <-> 721
1795 <-> 174, 614
1796 <-> 852, 1414
1797 <-> 511
1798 <-> 107, 1427
1799 <-> 812, 1109
1800 <-> 988
1801 <-> 684
1802 <-> 670
1803 <-> 1081, 1083
1804 <-> 462
1805 <-> 1236, 1409
1806 <-> 789
1807 <-> 1212, 1267
1808 <-> 1841
1809 <-> 1519, 1947
1810 <-> 108, 453, 1167, 1943
1811 <-> 139, 581, 734, 1955
1812 <-> 1225, 1281, 1812
1813 <-> 1602
1814 <-> 1689
1815 <-> 378
1816 <-> 796, 1314
1817 <-> 601, 1451
1818 <-> 357
1819 <-> 200, 1858
1820 <-> 1834, 1904
1821 <-> 1821
1822 <-> 10, 859
1823 <-> 694, 801, 864
1824 <-> 353, 713, 909
1825 <-> 224, 357
1826 <-> 254, 1230
1827 <-> 739, 793, 1221
1828 <-> 1004, 1948
1829 <-> 373
1830 <-> 980
1831 <-> 1831
1832 <-> 140
1833 <-> 1570
1834 <-> 290, 1820
1835 <-> 472, 1008
1836 <-> 1420, 1963
1837 <-> 1352
1838 <-> 495
1839 <-> 960
1840 <-> 789, 1089, 1611
1841 <-> 340, 1808
1842 <-> 65, 1253
1843 <-> 296
1844 <-> 302, 1628
1845 <-> 432, 892, 1971
1846 <-> 330, 669, 1004, 1783
1847 <-> 525
1848 <-> 169, 996, 1304, 1711
1849 <-> 57, 96
1850 <-> 1517, 1972
1851 <-> 32, 657
1852 <-> 518
1853 <-> 436, 692, 1042
1854 <-> 354, 1854
1855 <-> 619, 1855, 1893
1856 <-> 745
1857 <-> 1310
1858 <-> 1458, 1731, 1819
1859 <-> 555, 1004
1860 <-> 440, 1714
1861 <-> 228, 814
1862 <-> 722, 1464, 1692
1863 <-> 509
1864 <-> 930, 1265, 1326
1865 <-> 1552
1866 <-> 389, 1784
1867 <-> 1285, 1918
1868 <-> 578, 1770, 1957
1869 <-> 1660
1870 <-> 672, 1664
1871 <-> 799, 1006, 1749
1872 <-> 1088
1873 <-> 52, 569
1874 <-> 1896
1875 <-> 715, 963, 1177
1876 <-> 94, 1189
1877 <-> 392, 1371, 1484
1878 <-> 41, 579, 1471
1879 <-> 652
1880 <-> 1162, 1880
1881 <-> 1236
1882 <-> 1299, 1349
1883 <-> 482
1884 <-> 348, 1670
1885 <-> 757
1886 <-> 117, 737, 1463
1887 <-> 934, 1178
1888 <-> 717
1889 <-> 1899
1890 <-> 754, 1201
1891 <-> 155, 504
1892 <-> 446, 507
1893 <-> 1855
1894 <-> 182
1895 <-> 378, 650
1896 <-> 524, 1874
1897 <-> 1922
1898 <-> 446
1899 <-> 1713, 1889, 1899
1900 <-> 1900
1901 <-> 1295
1902 <-> 247
1903 <-> 37, 862, 1666
1904 <-> 1820
1905 <-> 502
1906 <-> 294, 978
1907 <-> 526, 566, 1128, 1348, 1400, 1546
1908 <-> 1908
1909 <-> 995, 1021, 1354
1910 <-> 407
1911 <-> 1204, 1621
1912 <-> 647, 814, 852, 1016, 1262
1913 <-> 565, 938, 1331
1914 <-> 1126
1915 <-> 411, 456, 1551
1916 <-> 211
1917 <-> 1033, 1946
1918 <-> 1867
1919 <-> 901, 1653
1920 <-> 278, 653
1921 <-> 47
1922 <-> 1433, 1897
1923 <-> 1654
1924 <-> 339
1925 <-> 1602, 1951
1926 <-> 352, 1294
1927 <-> 684, 1348
1928 <-> 975
1929 <-> 781, 899
1930 <-> 1475, 1629, 1698
1931 <-> 949
1932 <-> 977
1933 <-> 1059, 1087, 1612
1934 <-> 756, 1934
1935 <-> 145, 1448, 1756
1936 <-> 379
1937 <-> 1785
1938 <-> 1547
1939 <-> 532, 1686
1940 <-> 429
1941 <-> 431
1942 <-> 1740, 1942
1943 <-> 1064, 1810
1944 <-> 1015
1945 <-> 409, 1057, 1398, 1700
1946 <-> 592, 601, 690, 1917
1947 <-> 1423, 1809
1948 <-> 883, 895, 1777, 1828
1949 <-> 1949
1950 <-> 1950
1951 <-> 65, 1031, 1925
1952 <-> 327
1953 <-> 1323
1954 <-> 15, 630, 1155
1955 <-> 277, 1767, 1811
1956 <-> 522, 900
1957 <-> 1044, 1196, 1868
1958 <-> 1340, 1506, 1781
1959 <-> 125, 679
1960 <-> 57, 194, 534, 863, 1960
1961 <-> 1028
1962 <-> 781, 1018, 1788
1963 <-> 372, 1186, 1368, 1836
1964 <-> 1012, 1964
1965 <-> 484, 784
1966 <-> 527, 1595
1967 <-> 1431, 1967
1968 <-> 587
1969 <-> 656, 1604
1970 <-> 882
1971 <-> 539, 1280, 1416, 1721, 1845
1972 <-> 889, 1039, 1186, 1850
1973 <-> 251, 332, 629
1974 <-> 1183
1975 <-> 1975
1976 <-> 1011
1977 <-> 174, 579
1978 <-> 662, 1282
1979 <-> 205, 1065, 1074, 1677
1980 <-> 268, 549, 833, 1143
1981 <-> 786, 928
1982 <-> 634, 1539
1983 <-> 35, 1983
1984 <-> 1984
1985 <-> 477, 1985
1986 <-> 257, 1656, 1986
1987 <-> 1987
1988 <-> 825
1989 <-> 1624, 1668
1990 <-> 1357
1991 <-> 66, 738, 905, 1467
1992 <-> 744, 950, 1592
1993 <-> 779
1994 <-> 326
1995 <-> 1463
1996 <-> 713
1997 <-> 90, 513
1998 <-> 447, 1500, 1722
1999 <-> 12, 1537"""

TEST = """0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5"""

from collections import defaultdict


def part_one(input):
	connections = {}
	group_zero = set("0")
	for line in input.splitlines():
		print line
		port, cons = line.split(" <-> ")
		cons = set(cons.split(", "))
		ports = cons | set([port,])
		print ports
		if ports & group_zero:
			group_zero = group_zero | ports
		connections[port] = cons

	while True:		
		added = False
		for port, cons in connections.items():
			if port not in group_zero:
				print "checking:", port, cons #, group_zero
				ports = cons | set([port,])
				print ports
				if ports & group_zero:
					group_zero = group_zero | ports	
					print "   added"
					added = True
		if not added:
			break
						
	return len(group_zero)

print part_one(TEST)
print part_one(INPUT)


def part_two(input):
	groups = []
	def _add_group(ports, groups):
		for group in groups:
			if ports & group:
				group |= ports
				break
		else:
			groups.append(ports)
			
	for line in input.splitlines():
		print line
		port, cons = line.split(" <-> ")
		cons = set(cons.split(", "))
		ports = cons | set([port,])
		_add_group(ports, groups)

	
	while True:	
		print "cycle"
		coalesced = [groups[0],]
		for ports in groups[1:]:
			_add_group(ports, coalesced)
		if coalesced == groups:
			break
		groups = coalesced
				
	return len(groups)
print part_two(TEST)
print part_two(INPUT)