P17717 [HackerEarth] There are N candies in a room labelled from 1 to N and there are N - 1 directed path between these candies such that every candy has at least 1 path leading to the candy or away from it.
提高
题目描述

There are N candies in a room labelled from 1 to N and there are N - 1 directed path between these candies such that every candy has at least 1 path leading to the candy or away from it.

K and L want to eat all the candies in the room but they don't know where to start.

If K starts with the candy labelled c (1 ≤ c ≤ N), then he can eat all the candies which can be reached from the position of the candy c. Similarly, if L starts with the candy labelled d (1 ≤ d ≤ N), then he can eat all the candies which can be reached from the position of the candy d. Note that both, K and L, can start from the same candy position.

Now, they will be able to eat all the candies in the room if there exist candy positions c and d such that any other candy in the room can be eaten by at least one of them. In order to make this possible, they want to change the direction of some number of paths. You have to calculate the minimum number of paths that need to be changed so that K and L can eat all the candies.

Input Format

The first line of input contains the number of candies, N(1 ≤ N ≤ 3000). Each of the next N-1 lines contains 2 space separated integers ai and bi (1 ≤ ai,bi ≤ N; ai != bi) denoting that there exists a directed path from candy ai to candy bi. Candies are labeled from 1 to N.

Output Format

In the only line of output print the minimum number of paths that need to be changed so that K and L can eat all the candies.

SAMPLE INPUT
4
1 4
2 4
3 4

SAMPLE OUTPUT
1

Explanation

In the sample case, the graph is such that we need to change at least one road to achieve our target. One of the possible ways is to reverse the road from (1, 4) to (4, 1) and then select C, D as 2, 3 respectively.

输入格式

见题面

输出格式

见题面

样例输入
3000 1 2 1783 3 2795 1783 1277 2795 2 1757 1277 355 1826 2795 2795 688 2728 355 1826 589 75 1783 3 653 262 355 2 2460 1508 75 2458 1277 365 75 2795 639 2460 230 688 919 688 378 787 1757 1965 688 653 1734 75 1842 589 1751 198 589 1015 2460 355 1353 1734 1540 2845 378 2728 2235 53 1842 653 2382 2458 1477 1353 2668 653 381 1734 159 53 1952 688 2654 1125 355 749 2728 1125 7 355 8 378 475 230 822 7 2955 1751 2492 787 686 2918 378 2845 2142 2396 2955 2235 1865 1958 7 2858 378 2053 822 1434 230 1965 2322 589 2636 1434 2532 2178 919 192 749 589 259 2460 2001 1865 1271 2795 1468 3 327 2947 2178 1631 1734 2359 2178 1434 1951 2122 2492 1946 688 2701 2918 1271 2420 315 1958 1633 2322 305 381 1633 488 305 1334 2 2670 1474 1842 2728 372 2736 488 475 2943 2589 1783 1370 159 639 2380 2774 2918 2203 2359 2086 1477 93 639 701 2774 1525 1468 1182 787 688 1418 2903 1434 39 1842 2410 2235 230 664 2795 673 378 2516 2589 2041 1783 1397 675 2380 1125 1601 1148 1540 19 1525 1301 2410 589 1942 2410 2031 2774 949 1633 610 182 1015 2523 198 262 1459 2233 2654 2322 274 259 1272 2968 1370 413 2396 93 1482 1971 2589 1298 2203 2235 2683 2578 93 2017 93 1757 595 2943 2592 351 1148 365 1696 749 207 2578 772 639 2700 875 365 1808 1951 1918 1334 1792 488 688 1536 2670 1144 1631 2334 1125 2502 1783 57 581 1826 407 653 2450 1272 378 936 1561 2774 2573 2903 611 407 57 2566 44 581 2883 2532 2502 2239 2604 2031 2134 1182 1826 863 2683 27 1757 1898 53 1303 1865 574 1303 1598 936 2641 191 589 2573 2539 2918 330 2535 75 2420 836 207 464 936 1625 1090 407 1734 1260 1418 554 2903 2756 1418 2856 1918 1641 401 2856 2839 1148 2239 2913 2086 1294 401 757 167 2589 576 2736 103 1015 2017 1891 2604 2536 405 2031 595 393 262 523 2566 43 2539 2898 159 2694 1100 673 2045 1865 488 1620 2968 1013 1808 707 653 778 2911 611 1865 294 121 1144 849 2523 2458 1118 496 1260 427 574 162 1118 2045 394 2334 2260 540 2701 863 608 2142 577 1619 2883 1144 878 114 192 315 1925 1540 599 2249 1865 2403 664 475 348 757 966 1144 1670 598 2883 2124 2053 2232 1842 1131 182 609 2260 2700 1002 2041 2488 876 2322 2065 2955 376 2654 2337 2535 1492 2134 1525 2751 2918 1231 574 1618 2090 1958 2944 1148 1920 2756 224 2856 1482 1656 325 305 365 1790 27 2540 2395 2420 822 560 1918 771 1542 2947 376 1439 1152 1783 1508 807 376 1364 1013 412 757 2559 1616 2239 540 723 1476 2001 1066 2134 1648 1808 446 2090 563 822 2539 86 708 807 2053 1665 2178 2213 45 1601 2797 1090 2 2242 921 673 807 880 259 476 707 2761 1706 878 2239 794 1942 2227 272 1301 381 424 2566 1405 405 379 2670 41 2774 1659 272 564 912 949 205 2 191 1355 1355 1214 900 598 2332 771 1536 2790 420 1958 2990 1792 2636 2447 1760 1898 2391 2458 2611 2898 2947 1983 191 2554 2358 2420 2307 2358 145 2903 2134 255 2539 1200 2955 1172 175 540 2142 2637 2227 1705 2955 2238 1808 2576 1769 1561 2227 2794 503 2124 1272 751 2728 1262 2609 7 955 2858 1342 2322 2936 1648 1561 1308 1665 1179 2053 1031 1131 2645 330 500 2866 639 2498 1303 2299 2589 2694 31 1711 365 1422 1397 2075 2728 2447 2282 798 1131 721 393 1736 2609 2536 713 1277 1113 370 1434 416 1918 2693 2968 2539 938 1619 2825 446 2448 2124 855 462 589 836 2938 2740 1200 2739 2938 2359 2501 476 593 749 2581 2756 2037 2667 723 1013 1820 235 2573 549 1620 1214 1904 706 1125 1763 2410 280 2492 2516 1166 394 975 2396 2071 721 335 192 1169 2589 2872 412 2074 2798 2532 2460 716 1078 1355 1033 716 2410 2621 2054 167 2507 1706 2872 429 798 396 742 2621 598 620 1144 2976 523 2618 1248 1002 491 1665 2664 2332 2260 2789 2560 598 2053 194 22 599 2637 342 2872 2206 2813 523 1904 1673 1078 2073 2395 1447 620 2984 2206 935 2041 256 525 1942 1808 1361 547 1540 1567 2589 949 567 1166 2454 2670 58 500 1392 2288 315 1284 1540 694 2825 1508 237 1976 2944 1405 2503 2358 2209 1807 2856 413 13 1860 1308 1811 2701 1271 868 526 574 2536 360 2996 2756 553 207 372 1880 878 1456 2806 1482 2955 2888 2194 1976 739 2683 2560 695 2498 2909 471 1492 2925 2086 1152 727 121 1743 1755 1743 910 2645 2362 2938 1721 2740 680 401 2556 2282 274 974 577 1563 1711 241 581 1737 880 2022 1631 1335 2774 465 45 486 2645 72 1412 1468 256 1962 761 1492 2898 2986 416 2873 2112 1364 1292 1904 627 2507 2825 354 2996 2800 2765 2670 2396 166 589 2709 1125 785 149 1620 420 1902 1958 881 1369 785 2233 357 1613 1125 2622 235 480 1214 2774 637 2197 598 653 271 2739 1374 1450 713 72 1377 878 1784 1437 523 907 2913 677 1392 2071 539 205 2646 1808 1850 1795 836 606 1476 59 2122 2354 1656 1328 2622 335 1933 1006 427 554 1698 876 1515 1026 475 2938 1480 523 131 2664 1791 305 2730 2127 1294 2619 1625 274 2818 564 1668 880 123 1680 205 1756 1090 1885 503 2175 1542 680 1067 372 2517 2285 595 2090 789 2552 241 1808 104 2966 19 961 1898 2637 1589 2222 351 1412 1432 2556 1469 1774 446 1469 2314 2720 471 1456 2158 837 751 1169 2191 1674 175 532 1469 1631 266 794 1333 810 2709 2804 2873 1033 2912 2572 1743 180 166 2074 1358 1474 862 636 836 2720 2921 426 1743 2011 1656 875 1552 1231 2820 980 486 1690 1983 1508 877 2874 1774 2806 1427 2315 564 1427 2895 416 1223 2604 233 1737 1785 45 2151 2018 688 1078 2092 273 547 794 2884 1865 1697 1850 307 2794 1486 878 2715 595 1291 1486 2125 2084 1891 2411 393 414 103 250 606 2458 410 2675 2622 771 2762 2399 1721 912 2920 1601 2585 19 2908 2636 2547 1161 1619 761 2885 2178 943 977 789 2474 1933 1432 161 263 1850 1707 1392 157 491 1127 2913 1127 60 595 1380 2825 2749 472 1946 1434 1017 2420 153 1691 372 1373 2675 2673 549 2566 1635 1850 601 304 259 1945 2054 1299 2912 2644 2458 2232 2495 2617 427 1784 279 620 767 874 424 61 771 1690 2941 756 2873 1295 2943 922 1026 1029 2884 2512 1756 1062 943 2317 205 632 921 2531 414 53 1967 1295 824 57 844 2730 2835 874 2262 1169 1417 949 2300 975 978 772 1446 571 2054 2284 1707 1404 1468 2677 2966 1600 2589 2619 2457 1648 1520 2525 2700 2533 1066 2330 2410 1520 469 1618 699 1866 2238 1165 1552 230 2659 1547 1659 2611 1281 1492 1609 662 370 1378 1656 775 789 1540 1162 514 2299 167 1835 665 2359 1049 727 2073 2538 1085 1397 1728 2818 224 2983 1299 2783 2657 739 1368 2358 2150 2790 870 2536 712 2888 241 1340 2535 734 149 948 2492 1401 749 1176 2516 2146 1235 1769 2332 213 641 1447 1724 486 2359 1572 360 2340 2817 1619 461 1567 471 1061 539 90 1852 2622 1976 1955 1552 679 2552 124 2122 2016 2134 101 2057 1295 1104 794 1069 2621 1626 237 110 2084 9 1962 194 1167 1619 100 71 2284 1629 2517 149 800 2155 2458 2828 2883 1804 2908 1162 1887 14 560 2966 333 1137 577 2213 129 12 2888 278 563 1618 143 2407 713 1231 34 1656 2010 679 113 2980 707 1926 2203 2610 1432 837 326 1444 1085 1467 1335 1535 1182 939 632 1380 1689 1318 372 101 1913 426 2505 1785 1578 818 1450 762 1167 1525 2006 1248 958 1453 1373 1689 2741 217 2090 271 1543 441 2065 837 2520 1231 2064 2727 688 1763 905 2824 2299 1567 1927 2939 665 402 1670 549 585 2959 1453 347 413 1887 902 969 476 1873 2053 335 1815 2566 2393 2969 2683 2239 2083 2892 1335 105 427 8 1319 1531 2783 502 1792 601 2712 2576 2115 2851 969 350 1137 2830 708 1364 346 955 2537 2338 966 1705 2853 1595 1734 2303 305 996 1567 1708 2576 2531 2005 1815 1612 2566 752 443 2334 1601 37 2786 2396 14 2752 2661 1697 875 1139 996 797 357 184 552 1477 2820 2896 86 1426 10 273 126 2818 1432 1881 2602 326 149 120 752 1851 577 667 956 1137 2963 2828 1251 279 667 84 271 1464 1590 2817 2012 2045 1541 1161 840 1214 1520 542 369 2535 1950 1061 1943 7 34 1018 2736 2283 1647 61 1823 1447 2 2595 15 224 2559 661 9 2929 644 2667 1790 1841 121 115 2715 2168 1000 1945 609 2731 2661 1138 1369 1960 2767 396 1446 2847 1130 2585 1697 1718 2862 948 1043 1364 1453 2519 2886 2332 2969 1632 1895 113 2795 2152 342 909 716 1858 1216 2610 1122 1736 252 525 2347 2238 2087 532 177 2300 496 926 2637 2473 809 1763 2117 2938 1967 1411 546 2537 948 1645 822 186 540 799 2005 122 1065 1850 598 1894 1698 40 915 571 1058 2501 1025 1426 2458 2528 1509 1860 1019 2262 664 2067 12 2832 2782 938 687 376 405 1610 2640 2503 827 2595 2603 996 1487 177 1700 145 2168 621 426 477 1258 280 2036 1231 100 1443 720 2969 1150 461 2725 878 1736 187 1232 1698 1891 2480 1815 2171 2834 2495 840 392 1392 888 1869 2209 229 2197 2845 1949 1613 1445 165 563 1783 2030 427 2737 340 874 335 1171 588 2359 1397 1528 1458 1262 780 198 1791 264 2269 1552 65 2090 1497 2576 2041 2489 1374 562 2514 836 2435 608 238 926 2326 2053 338 1492 1125 2779 1540 1178 2073 1389 304 1466 2740 2154 1419 1616 2645 2140 2164 57 2536 2846 2391 201 393 1916 2726 2736 2605 2756 941 2767 1073 335 391 1869 1998 1459 1626 1253 2334 438 2469 546 407 582 2879 2523 252 212 348 1408 2323 514 1274 429 2435 763 75 2383 1282 53 2822 902 961 2002 475 1767 2142 1105 1712 2006 122 2375 1488 39 1268 1700 2457 2923 1673 200 2731 181 2075 2599 868 1089 57 517 2031 830 2134 1188 1887 164 2806 2145 1487 2405 593 1723 2591 694 1884 1137 2036 2496 1716 1335 2318 810 2013 761 1459 2543 2908 781 2276 1303 161 630 2661 371 2551 131 2083 1802 2511 589 1785 575 1314 2790 317 2858 2668 1037 2605 435 1619 2748 359 1700 1497 1929 2120 593 2297 90 2064 710 1297 2495 527 1851 2619 285 2765 1947 1540 2563 2976 2008 1524 581 2746 1334 376 2453 563 417 333 504 2038 609 2572 993 1169 1586 2645 2107 2462 771 2973 53 2489 2325 1640 1536 2036 2273 1767 543 2767 730 227 2480 2711 1670 52 305 2898 1695 43 1992 523 2588 577 2590 2237 2845 1406 2955 1468 2594 2727 1781 2592 1899 717 1536 1125 92 2130 2637 1000 242 76 1405 2774 112 2207 780 2871 980 836 1044 2224 1807 2646 490 1303 1325 2064 530 837 2234 2328 1674 1369 2493 1273 330 871 1273 678 1369 2731 460 2762 1666 1325 626 1226 503 274 437 1982 2578 2947 783 2837 113 2252 1411 1331 1235 2411 1587 2837 1516 2591 1675 2094 1508 2522 1572 804 491 1092 1417 2710 2460 2521 1949 75 2342 1840 2765 155 198 1083 1723 2117 651 2539 1857 993 2974 19 649 1225 184 381 1745 783 963 324 255 2410 1070 1916 1317 1105 2840 1569 1840 493 926 1216 848 483 1916 2605 1577 2413 324 1348 963 250 142 813 1308 813 1877 901 1297 2411 1566 1162 125 135 2774 1983 386 2429 2090 1542 1351 2813 2179 783 2481 1691 1286 238 1562 453 31 2485 2938 2572 1584 938 1356 1520 1050 477 1438 694 650 57 1839 2610 520 2241 922 443 2427 2742 453 1261 213 1822 783 310 734 2916 2921 1597 567 2665 357 452 1061 2840 2902 2485 1495 2728 1337 1674 1077 1599 1050 191 729 507 2609 1208 1037 1867 122 601 1611 2043 1698 108 2283 2275 2347 1131 994 441 140 1755 657 1952 1247 1725 233 2152 1012 1920 2160 1823 2020 96 1474 2189 650 350 1521 2002 366 2930 1369 781 2292 1784 1238 388 2008 2911 536 2385 1815 924 162 2505 934 111 1406 22 1414 548 2767 14 2630 945 739 329 1540 486 451 2542 1673 2210 599 1752 2694 169 708 285 843 545 2847 828 52 740 2354 975 1362 1439 865 1690 203 2681 2798 555 2171 1083 1203 1056 44 878 1517 2929 1246 2514 988 1542 592 2644 1574 354 747 2694 732 1675 1424 1116 2127 2847 1184 487 201 667 1094 1782 2020 2130 884 2963 1957 862 1330 1783 1658 1509 321 324 1642 394 1921 1307 941 3 650 2035 1037 2720 1499 1110 1434 532 1636 230 852 1382 2297 1640 1828 2253 2858 1670 2971 2503 873 2397 1807 1728 2333 2984 805 977 1575 2116 2234 1989 2073 1724 2148 126 2997 2521 332 367 1131 1689 1336 1158 1200 270 294 2384 145 2580 2262 923 304 2641 2546 1741 1012 2235 1694 1083 74 2688 1248 570 1033 974 206 704 734 188 1085 69 1597 2563 2139 1801 229 2533 973 765 2275 1199 140 1297 1764 1133 1094 2696 370 2286 1620 2493 1864 1863 2317 2235 1832 2087 2170 666 1633 887 142 2703 721 1061 2814 2254 1942 2818 1667 879 429 257 1043 2339 2966 2620 2559 1587 299 2084 1496 756 683 2481 2999 1511 1499 2265 1509 1472 2591 1624 1083 1149 1857 2935 723 1100 724 543 2650 1258 1024 157 2940 2584 2002 210 2955 2535 1095 2216 926 1783 1730 1611 1385 2667 622 2537 1052 774 701 1437 731 1589 2406 490 714 1828 1900 367 1435 1632 702 2282 1907 1449 263 1210 1982 655 2789 1251 2137 212 2309 2085 453 1954 294 1698 2438 48 1967 744 2999 2762 2370 2226 1231 2238 2374 2352 104 1510 939 2255 1435 2225 2736 2731 1132 2669 2560 217 2056 1936 1377 709 2709 2995 2727 908 1535 804 2854 529 2155 636 1560 2210 265 898 973 2130 1901 2854 297 68 1598 1986 1763 849 2705 2457 2894 293 2073 2615 1774 868 619 310 1079 2603 1870 858 359 1446 1646 2928 938 2355 875 2661 1829 2499 2751 1001 1480 975 533 866 1314 503 220 1298 1038 2215 774 2306 1361 2406 1504 2852 1925 2000 1936 465 1551 532 16 363 996 1357 1578 1963 242 991 491 2460 1196 86 2952 1069 817 118 1636 398 22 2142 2123 224 2100 2714 517 1419 1296 730 1534 114 444 938 1415 2025 650 146 877 2286 1605 247 2209 1107 665 1736 2026 1781 173 1053 2551 2030 1123 134 2237 582 891 638 2237 602 1094 858 2440 1387 1291 1903 2952 881 1367 1665 499 2807 452 2604 2808 1193 1542 2043 2298 2123 1739 2365 1029 307 2204 710 2414 154 721 2475 935 688 51 2412 2020 1381 1962 1700 1758 2057 2138 1384 1674 1274 1814 2357 1705 728 2325 1060 1178 1653 53 1860 2378 1368 190 1921 2153 1243 1427 520 2128 1951 1787 1968 2215 2227 646 2598 699 349 2966 1439 1580 278 1494 2408 809 2401 2525 308 1061 2762 1720 927 71 2599 1011 1491 2790 1321 1563 952 2959 1178 681 2037 1229 1558 376 472 1154 1107 2266 108 2713 2228 1647 1393 1127 2331 2525 1683 1625 1728 1502 1437 2417 67 1528 1732 873 312 1148 1689 1345 2135 2622 2733 1567 2220 863 1381 2747 565 1321 1519 2334 329 35 1894 1875 2612 706 875 1265 1021 1658 1150 457 2228 1395 151 1885 359 2088 1601 2208 780 2369 681 1430 2145 947 2342 1912 1671 651 542 442 62 2668 944 1745 1427 1639 2772 2983 1206 61 217 705 1525 2372 1160 2025 2394 1377 439 1852 83 1223 2867 961 2369 2096 636 2381 2979 1449 421 1223 1213 2365 2312 1636 2144 905 243 2726 2905 2920 271 11 2526 1477 5 514 1156 880 2039 887 2647 206 1362 2950 2125 623 1048 744 1233 2895 1822 375 1228 2130 923 607 1005 2134 2846 1806 1257 1711 1865 214 696 740 2681 423 1509 254 2327 416 488 776 2920 1505 2318 2625 108 286 393 1463 1109 2830 1074 2241 2341 2496 2486 2038 274 2816 939 1549 2355 2932 1494 1266 1049 2310 767 2470 96 2744 578 388 448 1957 334 162 1825 2705 716 468 1089 2607 1515 614 1804 1288 1061 80 2876 2839 733 2522 145 2509 761 2550 1645 415 39 1606 150 956 1507 1711 457 2451 120 2181 2938 2044 523 2735 423 1622 1282 2476 81 974 546 2586 1344 2700 997 876 2037 2881 1259 490 865 1275 298 2828 1804 2167 2753 477 2828 1917 648 2911 2150 940 326 1818 2061 2071 2962 2333 1452 2401 1969 1210 755 2814 2863 1161 2243 61 2238 613 1140 961 1239 877 563 406 126 829 1070 538 2213 2793 245 1050 12 1051 2275 239 2674 335 968 2282 647 2410 1323 2551 1052 850 795 1902 1523 452 2987 968 452 2891 32 1943 2776 129 2880 1156 1345 635 981 2499 1367 1740 1118 2121 2659 770 1441 599 73 614 1411 2805 1626 390 1260 1375 1704 2399 1809 2476 1452 296 1215 2486 440 1139 2566 1153 2104 1884 1004 2825 1874 2469 2795 1084 1706 1915 1895 2732 2370 2922 892 324 525 851 1151 523 2049 1382 1403 851 1790 816 960 1176 951 1308 2680 96 2951 2337 2957 1590 1920 972 2903 1934 1255 2884 190 1565 2898 928 831 194 74 138 943 2099 1337 49 778 1990 2092 1341 306 2310 76 1242 721 508 2214 2016 1556 1006 1841 2729 284 1818 1090 985 2732 2461 1483 1521 517 1614 910 189 2036 753 2807 1219 2132 2275 705 2236 2887 96 121 1280 2415 1083 2408 1548 2449 1633 105 2815 669 1863 1236 1125 2819 1308 492 2866 1071 2867 877 1630 734 2755 843 971 2317 2697 1491 1359 700 306 66 129 2131 601 663 908 2837 2003 1954 1931 2012 1250 1698 594 1537 700 1858 1099 2764 376 2945 44 2262 2541 2708 1495 2221 1188 961 1186 982 2881 601 2308 1647 2961 1519 1075 1959 153 2645 1663 1413 1286 590 2254 2011 2472 1043 1442 44 2784 903 472 1656 2250 1803 2971 372 1506 341 1874 1718 1819 260 1600 2556 1862 2959 1322 1871 844 1169 1022 209 67 2813 33 1040 2980 417 987 1465 2020 2567 1138 2808 1780 456 2288 2283 572 1243 1501 751 2032 2541 1423 1571 807 1547 1433 1751 1283 846 570 878 2953 2756 318 587 2645 2060 948 2499 1120 1650 1842 941 56 1597 1583 450 396 1098 31 415 1890 824 1088 554 1183 2956 908 452 231 2071 20 1190 1809 1724 449 1505 906 2900 2749 710 2176 2954 875 1739 1789 1534 1276 2039 1664 2689 1469 1647 2706 1310 2010 1241 707 2443 1152 302 1049 1201 2399 1157 2764 1096 2976 318 1097 1112 2733 1850 36 2373 567 688 2386 1975 14 1710 1418 2937 111 2915 2338 1520 782 147 2739 1620 2431 2085 857 1796 2429 191 1906 2118 327 1712 2042 1770 1629 2234 2050 467 2694 1961 1050 354 886 723 236 2431 261 1187 1877 1345 2289 1856 1521 405 2548 1991 2995 2912 2803 2407 385 1845 2008 2055 41 2826 2197 1797 613 1970 1219 2816 1928 849 811 1545 2394 2297 586 2329 2018 1863 2893 1718 1327 2126 639 692 2708 2484 59 1714 370 1455 1433 2741 1198 2518 2 1767 2754 356 1561 2106 830 1653 819 1548 219 204 207 2404 1375 368 2453 270 918 553 2970 596 1519 2262 485 580 333 1682 2805 1402 149 215 778 134 1812 959 2895 1474 754 2261 2566 1008 1248 1439 1269 2052 675 2633 2552 959 1861 2553 2669 2614 901 2516 1759 2793 364 1485 1587 1555 1288 312 2313 2019 135 467 1699 1287 1718 309 574 661 30 410 2229 1679 1337 842 1656 2789 957 851 2247 1341 1750 2936 2162 1334 629 1590 2723 2851 397 1539 1337 2428 2303 2969 1748 1888 1508 1220 2700 1252 2412 1919 681 860 1861 1686 2250 1637 862 1821 2303 479 908 1640 812 2126 531 856 2892 2675 1202 2156 2396 246 2715 1200 1722 319 755 1044 612 12 495 1234 2473 202 2016 2432 2071 1514 2022 1115 1250 1500 1482 586 395 225 2846 1882 2591 1055 1933 702 1087 2780 238 356 522 1141 1789 1624 2294 1300 1260 2924 939 2637 615 1735 1165 368 853 2296 247 2463 2943 1685 449 2637 1068 605 1276 1254 1511 2977 1506 2167 1615 743 75 2864 350 2168 1719 463 866 900 2263 1836 305 426 2878 196 851 641 1312 485 2785 846 281 130 2892 418 888 2888 1102 2871 1974 2163 2401 995 2621 2410 1844 2054 1923 1658 1944 1232 2707 320 2451 1625 1753 1194 1819 2885 550 1350 2448 1421 653 679 746 2655 1960 236 1676 2511 2418 2216 1532 534 285 1056 1677 1461 1501 1747 1331 1727 2115 1119 2674 1914 1789 2735 1816 1257 2445 2654 1688 859 2276 2497 2966 191 17 446 459 2676 130 2890 560 1253 2734 1295 1222 1077 992 387 2052 2068 2499 106 1622 2430 2307 2205 1333 2635 2505 2283 1762 1348 1879 2810 1998 1424 4 2984 569 2747 1209 2784 2865 2663 2854 164 1754 1848 169 2199 2720 1990 1376 156 480 50 912 2682 752 2003 2040 940 2291 2144 1136 2128 2850 2477 245 2089 2537 720 1937 2364 1269 760 2083 557 118 894 184 1143 1334 1788 2682 1309 1551 1047 1424 401 2304 111 718 3 2165 1650 2658 2048 2797 1225 1853 2333 400 964 778 825 1962 1003 2310 99 996 1713 2714 1695 2919 1164 2709 1909 2461 2549 1640 2064 1379 2444 713 1627 2852 643 1322 2000 2257 2329 179 2984 430 1455 2796 1000 447 1364 2193 1041 2427 2672 1029 2114 2896 45 1240 1616 221 2368 1890 369 2246 990 1004 1475 2655 2506 140 2248 164 1605 2606 2607 2287 1301 1966 2430 2409 2568 204 189 1956 539 2849 1761 653 635 839 1738 2655 2293 2193 818 989 724 2051 2416 2984 300 641 2706 833 47 534 404 360 1170 1322 1127 1207 2921 2757 698 2826 9 2007 1590 2642 915 21 78 48 2892 1701 2190 429 1200 750 2934 2867 1100 509 1157 2687 872 1069 2933 681 1128 2796 2726 537 535 1699 1337 1263 2476 2801 1006 2390 2951 1124 1902 218 2200 2397 1971 2345 2975 1109 1881 183 1152 2624 116 1364 2220 603 2834 408 1159 1571 1736 2490 557 482 1648 2721 586 2861 2302 1845 566 457 2029 1658 568 1682 1320 1747 344 2921 1953 1848 2920 2240 2028 2584 1344 845 2125 2843 2457 792 1067 2223 2948 2602 2885 1289 1245 298 632 1343 2569 2607 2190 2070 1665 847 880 2110 1265 2280 1512 1277 2596 2048 2324 733 1449 769 1351 2079 2135 2692 2769 2794 81 1985 2597 2342 942 307 25 1976 127 2736 2580 1490 134 544 2245 1601 411 1586 1150 498 2452 2369 383 666 1334 2367 1841 481 1040 2320 397 766 2369 2882 1361 2172 1370 1212 2042 160 335 1922 861 1563 1411 2295 2153 2059 457 1080 2815 1908 379 2439 2802 78 202 428 496 2363 1622 2021 2121 2716 2924 1121 2974 864 2655 600 2426 261 1746 798 1581 233 2722 1266 974 633 2771 1858 2381 634 1390 1065 1399 2756 1607 941 1362 2829 786 34 1253 1237 2626 1770 94 2663 1109 2264 2166 997 1178 232 178 942 2578 1106 771 885 127 711 2515 1362 890 2393 617 1985 2402 938 2072 644 1448 2672 581 2093 1224 2552 379 685 170 2891 719 536 222 2744 2651 147 1327 2989 1074 2719 2467 340 148 1300 1587 1396 470 1022 461 1843 2775 1021 2628 1704 2990 2188 773 2144 724 737 374 2025 2648 1037 439 889 950 1314 2828 1824 198 208 1996 2449 47 268 48 1349 2773 2197 579 351 1026 89 2699 1419 1718 77 2341 2760 2745 1745 2062 155 2806 1180 2803 584 620 2434 1175 2873 2256 2408 777 2820 2982 500 2787 2669 1126 907 2627 1745 1854 500 1317 2212 500 1684 1836 1185 1700 2600 2452 2078 804 882 2355 336 1538 2818 115 98 1591 1094 2462 2494 2021 283 1185 1218 2243 87 423 976 1303 117 2034 1422 448 1436 2809 732 2951 1799 2186 2617 2799 1865 1656 1878 1849 868 1380 2965 1535 2259 54 1480 631 2822 2624 986 269 2447 768 1127 329 1661 2159 2432 758 1434 518 797 274 2272 2398 1528 1057 1190 1602 2029 1349 2690 75 2910 1460 1236 2360 106 2281 831 1977 1844 41 616 1158 253 1394 2799 422 2687 1205 274 2325 1588 1218 970 1619 1932 925 2000 1680 1765 2218 470 1191 114 1580 2608 628 852 1012 1930 2768 333 439 2351 1094 1883 834 1475 2738 1752 2311 886 498 1660 1529 1180 132 2771 779 1517 1131 290 587 436 2684 2135 1990 689 2775 2202 1604 1878 1454 606 425 25 2842 1959 1889 281 2555 233 718 478 846 967 933 355 2198 2391 249 926 937 1321 2518 803 1773 2700 1470 2144 1557 1060 269 2319 1489 198 1639 841 1181 708 2201 1774 1318 2632 2149 934 1865 323 2841 1607 1890 353 2823 493 2048 1163 2643 2806 2558 685 2058 978 1885 2831 897 606 836 211 1911 978 18 2789 1027 140 1288 1973 1062 2833 1518 1170 2147 2746 1108 1784 2669 2638 1905 2451 1789 2270 2207 358 1778 336 1431 2257 2355 276 2747 1383 2431 1681 2656 178 1982 979 1278 921 2862 2788 340 1744 308 808 2897 994 1378 1338 2143 2546 361 2632 42 449 2283 1346 2465 2734 913 1297 525 1101 61 2066 2868 1384 1352 206 2115 1649 160 1086 1939 1983 823 1673 932 2270 255 1570 1352 1111 2677 2091 894 1306 474 1069 1940 1377 1749 2620 2563 1230 367 1155 2747 2230 2346 739 2843 2570 2336 354 2753 2301 668 979 2972 1418 1249 2997 2076 1095 609 703 930 1406 2904 1760 1481 937 1483 1847 788 1933 1059 1415 352 2999 2183 1002 2682 1655 2447 693 57 2792 2456 1287 1210 97 1229 946 2216 2098 452 528 651 929 2491 2849 2777 2632 1890 2468 583 1163 396 1081 1651 2000 2691 1424 267 1472 915 1592 1990 1693 216 919 2899 2673 2343 290 896 2882 511 14 194 999 2920 1897 2350 1598 2276 2353 965 1882 237 1016 2992 1460 1875 2335 2221 303 1195 2810 676 2691 1667 2446 399 1680 2348 627 2913 1564 1813 1902 1981 823 2006 1995 782 2173 2908 1886 1021 521 2071 2534 512 259 79 934 2556 2981 1715 1295 838 2569 2516 1554 1285 1201 1495 738 730 1173 1115 1634 1145 1554 2623 1592 1112 1416 2781 734 631 2014 38 1382 1391 1690 1410 2523 288 2972 510 346 1200 2422 2917 2164 1069 377 2185 399 1843 1621 2570 1372 2271 2701 1732 1366 798 2133 71 1042 1751 445 2356 468 2991 1554 2400 2903 2647 802 1230 670 1493 2820 291 1069 2267 2851 2844 778 2203 2575 264 2479 1583 1177 1849 2024 689 82 368 2421 1787 962 867 1254 2472 2666 2836 492 359 1409 2483 359 2458 28 2361 298 1790 1204 93 1484 1866 1800 2195 58 820 151 2932 1709 2082 1791 642 318 1613 2102 1426 109 815 2331 1890 466 2275 1146 2349 1155 2587 333 2124 1256 745 2432 266 2109 2073 1217 786 2366 1281 484 2057 1692 1893 81 1014 1105 1970 2077 2876 1498 85 2874 930 2459 971 2023 2739 561 378 2702 1472 292 2726 1573 2500 2329 1619 2704 660 1893 2232 1798 199 786 2047 1977 174 2604 141 1141 1195 2033 2574 1857 1054 315 1042 152 2180 1229 1622 172 954 449 1777 160 916 1110 2825 419 2487 58 2770 2952 1085 793 520 2557 435 2196 2376 864 1098 524 917 1043 684 853 791 1262 2159 2577 671 1843 458 429 979 248 516 2961 56 1478 1469 2827 406 1731 2686 418 2389 1246 76 2437 597 1346 482 2009 1007 84 1924 993 899 2308 550 2946 1654 2435 1231 1270 2129 2879 2922 1593 71 869 1658 2601 674 2396 1006 920 1046 1075 2169 1122 107 1176 2529 534 2901 1226 2169 228 2958 1077 2281 1332 1217 1103 1617 2802 2097 1933 640 846 1028 1907 2069 280 1368 1425 740 2268 524 1742 251 1057 366 2750 2999 2157 1234 2513 2712 736 2583 2235 449 2998 984 547 992 1072 1311 2484 1546 547 165 176 1644 687 1503 2214 2863 328 1507 1302 506 1864 2113 873 2469 1669 559 2981 2685 856 66 1984 904 181 1974 2278 1134 2372 1174 2577 1491 513 2219 766 1147 1272 2250 2855 1470 2161 1093 2123 705 1623 1374 2562 2518 1872 547 1771 2686 2743 2719 1948 350 2759 856 1831 1706 697 945 403 1686 1672 738 2964 1703 2528 115 163 2582 2467 1145 1585 1426 801 1191 2967 2447 2277 2959 790 1533 334 195 1481 22 1032 2649 576 1770 1429 1627 2927 1574 2392 2818 185 1887 193 1371 516 2589 102 2259 1643 835 2563 50 1978 275 478 171 1474 2003 2141 1377 2174 854 2874 619 1859 2508 1346 1766 1147 2222 277 1380 519 92 1211 1768 2029 1114 1884 1993 2018 225 953 1018 2015 1386 2137 295 211 75 1938 2108 724 188 1316 1064 1436 654 262 188 1030 2187 210 538 373 1691 893 2251 948 1704 1363 1009 391 1657 1699 1926 128 119 1861 2877 119 2480 618 2450 1550 2510 2781 2571 2225 1433 345 1423 1428 257 1935 389 112 1374 1076 2177 1515 1769 1817 261 645 1803 2080 2177 1997 769 1360 2046 178 219 2544 1510 2698 322 422 226 2725 2634 1092 955 1479 1918 1979 730 432 197 143 1217 1135 2143 2244 2771 455 2848 547 2433 1714 616 1988 1868 1650 1837 527 2665 1398 1203 796 2792 2593 809 656 2887 70 706 1830 1559 2881 2860 2677 316 2194 741 2362 2750 2321 444 2660 136 2334 1994 442 2758 1371 2811 2726 1315 145 2506 1168 137 484 1513 2086 1326 1952 717 1293 222 2455 1955 1776 258 1887 405 1244 454 2149 2572 691 409 1867 2377 1389 748 2707 2204 624 2931 208 1495 1779 972 1082 486 431 1596 874 380 1752 590 931 2420 1117 1525 223 1257 2631 2942 2236 2074 2857 2482 2437 289 2950 459 2695 2675 2101 1133 1010 244 1213 2270 144 2304 1733 574 384 2471 2023 1091 165 1582 1342 1225 287 1959 1910 2838 2779 515 2188 2985 2729 1838 259 556 188 1420 949 810 2565 1279 1469 301 2094 313 2982 1628 2249 334 573 345 1775 2478 1002 1532 658 659 1241 1235 139 541 342 1175 2821 895 588 2469 652 2633 1603 581 382 1227 515 1142 1667 477 1400 2051 2441 2103 1797 494 828 1999 1820 1365 1291 725 1573 1931 1221 580 505 2662 514 2716 1833 1063 837 2900 1197 1938 2524 55 779 2279 2935 1591 1652 2493 2211 2052 983 826 1009 2998 3000 497 1966 343 2343 1846 1734 2561 322 814 701 1329 546 2067 1793 1232 2105 543 2290 1622 362 1878 998 2949 104 2196 1192 2875 1636 1404 168 2945 2960 2425 342 1655 2004 240 848 502 2371 2159 883 764 1765 2612 2791 1974 88 2274 1083 2935 2231 2438 2870 23 2397 2015 2119 2744 2436 551 1232 914 2958 2458 1638 1058 1544 331 836 2878 1678 1533 1388 2599 2258 64 470 1045 204 451 1729 604 823 2926 1664 2466 236 2617 473 337 892 1440 2108 688 1471 95 1602 2859 13 765 2671 1034 245 268 2652 806 2783 1594 2501 2020 1662 2111 1514 541 2679 2746 6 528 726 63 2006 321 2182 2639 1461 2763 2924 1435 2027 1189 758 2527 1110 2297 1023 271 2616 2464 2764 2889 2517 433 108 1941 629 2812 2534 2978 2849 2026 1964 1188 1305 2621 2778 2063 727 690 2259 2914 649 909 1313 1527 893 339 376 821 1626 1010 2081 282 764 227 1972 1706 2344 2423 2021 2305 1373 2963 46 2450 1473 398 911 2572 2419 2840 625 181 26 2657 2564 2379 2054 170 1526 2442 774 2168 722 1579 819 1827 1392 784 850 2893 2316 1339 1044 2631 2869 1617 2678 279 434 2504 307 2994 1923 1772 1610 1703 2579 1290 2436 2464 1608 100 2717 1987 46 1020 2190 817 1530 2266 558 1810 644 1892 2377 133 1218 672 2707 1726 2648 1694 1407 234 209 981 1462 2474 2545 867 1855 2486 759 2401 2766 1267 1141 1354 1967 2009 1568 2724 2670 1051 2095 2252 1451 2629 873 1873 2136 178 1324 2424 204 2906 1539 2718 1149 715 2716 985 832 1992 2653 1414 314 1025 2988 1647 1805 1794 2215 2774 2613 1876 1731 2798 91 2023 1717 501 421 570 2530 1553 387 1035 2086 1980 2036 1188 1264 1457 1493 320 682 1834 2054 2192 144 591 2481 199 2387 2004 1786 2046 1347 2398 29 1576 932 774 1522 2342 1039 678 1687 2693 1702 2279 158 1684 735 1129 2918 311 1252 24 908 1896 323 1727 489 220 1036 2217 1592 2184 2805 2907 331 733 1304 2388 114 2993 435
样例输出
1473