CT33026

Tarun and the Rustic roads

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the honeycomb cliffs of Beeswick with crates of roads, and Tarun the quartermaster must account for every last one. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 507; 0 <= m <= 1014.

Example 1:

Input: 86 210 1 86 22 37 6 27 7 59 4 12 31 67 10 57 17 49 41 65 41 45 25 34 18 59 4 49 1 3 43 56 61 81 34 81 1 79 4 24 18 80 45 76 5 69 28 39 40 44 50 69 26 63 8 56 31 36 14 53 6 86 15 35 24 44 7 10 25 26 42 84 11 55 2 50 25 55 30 77 25 39 15 31 4 16 8 86 46 48 14 61 15 45 75 77 32 85 26 67 1 65 42 59 37 48 9 75 28 42 4 45 30 44 4 15 22 52 31 44 45 56 23 36 4 61 58 77 28 69 20 51 12 51 50 66 66 69 39 69 12 26 43 55 15 58 48 69 27 81 9 11 5 52 28 73 52 69 8 36 53 56 9 84 29 44 25 42 5 81 4 68 14 18 45 52 15 54 26 50 20 46 33 85 24 74 41 80 44 58 26 85 2 74 65 86 40 47 34 35 45 62 10 25 17 40 22 42 6 85 63 65 47 78 1 68 42 78 27 34 32 56 16 25 57 63 32 37 2 85 63 69 80 85 57 58 40 43 59 82 9 78 45 82 65 74 15 67 34 83 46 68 35 49 18 27 26 56 15 55 33 50 15 17 5 50 49 59 7 13 5 32 15 80 53 62 17 64 …
Output: 2

Example 2:

Input: 220 219 1 220 24 93 21 109 73 125 1 166 53 179 40 183 43 134 58 176 13 140 39 88 123 212 184 188 73 200 102 120 10 197 17 49 98 189 25 161 77 97 15 134 108 132 99 122 116 152 1 140 27 64 1 172 28 182 47 84 17 147 6 70 17 51 54 210 177 210 83 84 45 132 44 196 70 166 36 59 151 183 148 196 110 193 162 187 26 198 104 184 25 98 40 215 110 182 25 76 96 134 1 98 96 216 58 219 99 137 65 96 21 146 22 197 60 182 62 159 72 218 16 110 152 183 19 140 124 192 173 183 7 177 98 115 72 216 31 187 69 98 24 38 1 135 4 203 41 95 149 169 123 160 89 94 42 61 20 130 11 21 85 178 2 38 122 179 137 205 50 96 72 80 124 178 14 83 1 178 44 56 31 213 153 184 75 219 18 141 133 199 69 118 55 181 94 150 149 186 171 178 138 204 81 187 29 198 164 203 83 114 53 66 35 38 53 106 128 131 2 136 101 215 15 119 81 180 24 190 97 18…
Output: 3

Example 3:

Input: 147 356 1 147 48 64 37 134 65 127 42 80 3 124 26 108 4 19 10 68 52 72 38 124 88 94 101 126 34 37 37 61 18 50 18 142 68 93 40 83 2 13 1 91 34 117 9 128 65 122 134 140 43 98 56 104 37 56 27 66 118 134 13 138 85 131 72 137 7 146 136 137 14 17 59 105 6 122 37 117 103 120 54 76 12 138 6 21 32 94 14 142 12 50 15 99 28 92 96 139 2 15 54 93 44 91 41 108 16 84 7 79 48 107 17 74 12 69 9 64 95 109 47 57 71 132 84 95 32 63 92 140 45 48 16 65 9 146 102 135 69 99 2 68 68 107 94 105 73 135 35 86 61 132 74 111 97 132 52 98 39 95 6 134 49 139 61 77 128 130 38 120 117 133 37 143 93 95 67 113 44 92 47 94 105 115 19 73 87 97 39 40 83 113 58 109 80 104 117 140 6 136 42 58 47 117 122 123 26 61 2 71 90 127 107 139 142 145 24 80 126 131 43 131 43 101 48 91 96 127 45 78 30 93 53 137 112 146 49 138 112 128 68 115 1…
Output: 3

Constraints:

1 <= n <= 507; 0 <= m <= 1014.

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