CT41819

The Two Guilds at Gusthaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the windmill fields of Gusthaven, someone must audit the season's records. This year the task falls to Cyrus, armed only with the canals register. Task: Print YES if the undirected graph's nodes can be split into two groups with no edge inside a group, otherwise NO. Input format: First line: n and m. Next m lines: u v. Output format: Print YES or NO. Constraints: 1 <= n <= 1866; 0 <= m <= 3732; self-edges make the answer NO.

Example 1:

Input: 286 892 92 210 240 282 110 148 193 203 63 189 56 279 21 79 189 224 250 252 35 244 131 218 166 198 12 259 8 189 158 181 82 273 129 147 47 115 151 199 84 159 58 267 111 234 28 229 266 270 182 281 123 204 60 93 21 276 9 96 106 117 187 261 51 254 159 257 40 120 20 133 7 206 59 247 136 186 96 112 136 282 11 217 28 207 7 195 77 107 30 140 167 261 20 25 10 260 88 108 84 212 134 261 215 273 122 235 11 52 97 282 6 42 109 201 2 260 14 33 22 259 104 216 32 128 15 179 123 279 117 213 124 193 11 27 185 239 30 277 197 282 40 64 37 188 138 160 135 197 229 234 15 267 264 282 68 84 23 236 72 162 20 60 63 246 63 211 80 154 192 277 72 173 213 269 42 54 61 224 18 194 130 210 178 187 248 275 68 202 151 222 174 215 64 147 239 262 38 200 70 170 24 197 19 164 126 166 138 262 199 269 39 210 105 277 27 103 120 270 …
Output: NO

Example 2:

Input: 1800 1659 421 1652 267 1562 711 1700 447 1543 291 1245 1390 1452 874 1562 513 1112 804 1327 736 1610 1465 1502 816 1246 647 1563 1218 1712 629 1093 408 706 88 1725 398 754 1425 1742 1396 1509 844 1161 555 1242 306 1781 47 179 293 700 343 735 449 1153 858 1532 472 1437 400 751 708 1774 74 1544 1183 1763 1438 1550 370 1188 250 1577 1058 1445 1369 1750 63 663 404 438 889 1668 128 704 30 1005 1595 1660 119 798 736 1736 275 1601 256 1547 520 684 1427 1468 808 1737 859 882 1068 1774 39 1130 813 1398 69 707 237 716 507 1321 352 1381 982 1770 400 1360 54 935 656 1271 271 305 978 1714 22 1526 981 1104 395 1269 807 848 233 1149 286 521 216 450 422 563 834 1627 57 1546 1040 1470 409 1445 1179 1448 288 1793 36 998 496 1357 906 908 1007 1080 802 1487 1525 1672 57 197 621 750 312 1445 925 1468 1311 1729…
Output: NO

Example 3:

Input: 1685 763 626 1500 37 926 111 132 186 1095 754 1227 617 843 306 328 763 1677 474 1013 834 1403 891 1550 1083 1529 530 1507 455 1569 144 1056 767 1400 307 1256 71 612 862 1145 1412 1429 55 1143 144 803 104 1511 970 1604 38 893 627 1199 828 1341 1228 1545 1636 1660 345 823 1617 1669 84 1454 410 1367 121 821 40 996 547 682 233 1595 1420 1615 1043 1294 758 1258 655 1207 198 728 97 1171 120 1555 879 1221 267 1184 1151 1674 277 1029 1539 1669 118 228 765 1226 1077 1242 426 572 632 995 447 772 1485 1629 348 749 417 849 738 869 893 1273 419 1021 274 1566 901 1151 393 673 217 915 159 609 745 1460 81 273 960 1604 153 267 232 1098 37 1627 702 1551 148 1321 79 1660 315 1195 1073 1074 578 1292 354 1270 706 1682 169 1652 470 1186 270 1020 645 1513 980 1581 502 504 114 1664 249 743 121 402 1214 1272 140 1…
Output: NO

Constraints:

1 <= n <= 1866; 0 <= m <= 3732; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
The Two Guilds at Gusthaven - MEDIUM Coding Problem | CodeTikki