CT64045

Tanya's Bronze tunnels

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Tanya runs the stall at the anvil district of Hammerfall. Today the books show a list of tunnels, and the numbers must be worked out before sundown. 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 <= 930; 0 <= m <= 1860; self-edges make the answer NO.

Example 1:

Input: 128 1181 19 98 36 91 9 124 15 53 4 45 44 103 7 55 61 106 116 127 45 126 24 44 57 74 38 43 23 67 6 106 12 21 60 95 22 99 67 97 14 91 72 122 25 27 61 85 14 77 20 72 92 98 19 119 14 89 95 128 41 48 32 112 61 121 17 70 41 69 26 62 73 93 12 68 40 123 36 113 32 52 13 64 34 42 10 44 22 71 20 64 20 99 44 50 47 109 9 10 1 100 93 99 17 23 70 103 82 90 17 79 59 89 8 9 123 127 77 116 94 101 46 68 7 28 53 113 111 121 45 119 25 67 16 125 121 128 6 13 85 87 5 36 6 7 87 99 8 101 69 109 69 123 60 112 40 47 7 58 26 44 65 95 44 112 12 24 4 22 14 47 12 46 5 83 15 78 64 102 10 11 11 30 24 59 18 41 65 104 70 107 61 75 9 104 40 120 22 48 33 92 61 109 19 58 22 106 18 22 38 100 45 110 24 123 65 102 47 124 21 23 11 75 26 68 78 111 97 115 20 70 65 87 80 83 22 94 4 70 9 11 46 80 73 103 15 33 17 32 10 50 12 111 62 113…
Output: NO

Example 2:

Input: 166 1638 47 54 87 98 70 79 44 47 51 67 71 112 53 115 30 84 42 121 32 134 24 97 14 114 142 166 132 139 109 137 54 89 18 139 125 143 85 142 123 162 80 157 150 155 73 151 152 159 46 73 30 63 125 154 6 143 127 149 49 83 25 58 124 146 51 105 45 79 117 145 91 127 138 159 11 133 38 105 32 160 75 81 60 133 104 134 36 74 34 37 149 159 82 129 31 49 17 18 71 116 95 108 16 154 37 159 72 103 14 135 26 162 15 61 11 94 98 156 115 139 17 77 45 48 28 44 22 129 11 140 105 140 46 114 98 115 20 80 22 51 44 110 4 21 31 155 46 76 110 119 52 79 112 162 106 130 74 119 61 138 100 136 116 128 72 135 19 44 99 155 12 49 50 131 20 49 87 137 53 128 47 75 93 102 123 164 52 132 10 79 39 82 62 117 43 76 18 102 41 154 12 54 136 148 39 163 9 44 24 37 56 154 126 143 12 115 23 27 33 39 100 158 89 138 111 136 11 23 11 123 22 8…
Output: NO

Example 3:

Input: 105 620 20 42 78 91 57 58 80 85 22 30 44 66 17 56 23 59 36 41 1 67 31 98 71 93 38 98 4 99 3 53 35 99 74 100 32 82 29 51 74 105 68 99 36 54 1 56 8 66 52 76 67 77 42 77 6 9 16 56 50 62 12 101 35 57 12 81 74 104 60 91 33 64 33 46 60 78 43 76 24 45 5 10 63 86 12 54 8 9 39 55 7 88 53 105 87 88 94 103 27 93 68 83 87 91 17 23 64 88 41 93 13 81 40 53 67 68 101 104 10 34 8 48 4 81 30 36 11 93 38 97 47 105 53 73 45 66 46 54 15 25 29 34 17 62 23 56 29 61 93 95 94 96 34 83 58 105 27 86 8 10 30 76 6 59 52 100 20 46 89 104 2 17 62 68 53 102 75 103 65 77 49 98 72 77 15 50 55 87 67 70 59 86 8 37 36 98 5 29 6 100 20 23 22 67 22 46 79 102 69 97 16 78 29 101 83 99 43 103 37 58 30 73 84 105 13 15 51 103 34 47 20 99 3 52 32 59 97 102 8 79 72 73 19 44 18 65 45 56 26 33 44 96 29 39 48 66 16 75 37 77 30 32 15 82 …
Output: NO

Constraints:

1 <= n <= 930; 0 <= m <= 1860; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.