from collections import deque
import sys
def  func():
    n, m = map(int, input().split())
    adj = [[] for i in range(5001)]
    count=0
    s=""
    for i in range(m):
        #u, v = map(int, input().split()) # 输入不一定两个数 有孤立点
        # 尝试读取一行，处理可能的EOF
        line = sys.stdin.readline()
        if not line:  # 已经到达输入末尾  输入的函数可能不是m 行
            break
        count+=1
        #s=s+str(count)+"--"+line
        edge=line.strip().split()
        if len(edge)!=2:
            continue
        u=int(edge[0])
        v=int(edge[1])
        if 1 <= u <= 5000 and 1 <= v <= 5000:  # 题目中范围
            #print(u,v)
            adj[u].append(v)
            adj[v].append(u)
    #print("数据行:",s)
    #print(adj)
    # 距离数组  -1 表示未访问
    #   distance = [-1] * (n + 1)  # 输入的点编号可能超出n 
    distance=[-1]*(5001)
    distance[1] = 0  # 起始位置
    # 设置队列当前节点的周围节点
    q = deque()
    q.append(1)
    # 遍历邻接表
    while q:
        u = q.popleft()
        temp=adj[u]
        #print(temp,distance)
        for v in adj[u]:
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                q.append(v)
                if v==n:
                    q=deque() # 清空队列
                    break
    #print(distance)
    print(distance[n])
 
func()   


"""
首先读取输入的节点数 n 和边数 m，如果 n 为 1（起点和终点相同），直接输出 0。
构建邻接表表示图，对于每条边 (u,v)，在邻接表中双向添加，因为这是无向图。
使用 BFS 算法寻找最短路径：
维护一个距离数组，记录每个节点到 1 号点的距离，初始值为 - 1 表示未访问
1 号点的距离初始化为 0
使用队列存储待访问的节点
对于每个节点，访问其所有未访问的邻居，更新距离并加入队列
当访问到 n 号节点时，立即输出其距离并结束程序。
如果 BFS 完成后仍未访问到 n 号节点，说明 1 号点无法到达 n 号点，输出 - 1。
该算法的时间复杂度为 O (n+m)，空间复杂度为 O (n+m)，能够高效处理题目中给出的规模限制（n≤5000，m≤50000）。



注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.
测试用例 
输入 m=815   实际只有269 行 

469 815   
449 499     # 499 超过469 所有abj 邻接表的大小为 
68 205
168 326
201 390
248 440
482 198
273 450
180 475
373 115
371 441
93 36
174 359
19 497
20 387
266 178
339 62
215 161
22 60
461 102
230 208
79 13
95 30
111 229
119 218
360 240
7 332
289 81
283 445
111 292
165 225
317 483
258 142
244 389
63 65
153 296
225 8
41 276
404 47
111 209
170 174
211 497
191 182
450 415
408 50
72 402
226 191
92 265
239 336
294 38
88 23
87 254
416 404
103 383
454 208
466 70
259 120
308 489
398 417
159 248
435 308
42 61
358 240
179 333
257 339
379 394
110 100
384 323
161 500
247 74
488 489
34 293
213 12
142 219
478 171
253 122
78 220
195 101
204 71
350 290
293 269
73 159
189 84
251 35
219 341
477 86
214 434
193 303
180 81
5 237
252 121
116 166
328 106
455 477
158 75
446 372
144 233
429 203
24 293
328 66
168 344
5 39
350 160
123 161
271 70
64 236
373 171
492 193
142 325
78 434
38 375
202 497
299 406
288 50
487 81
398 249
487 321
239 276
312 53
16 330
402 248
414 324
244 428
62 385
149 177
431 301
343 398
57 40
141 235
432 353
71 108
322 257
146 100
173 52
324 265
168 146
124 386
124 396
478 153
436 66
495 190
36 7
223 235
396 237
51 190
133 9
387 406
231 114
72 243
260 125
88 166
240 147
456 334
439 398
223 171
492 13
388 55
183 464
319 179
498 370
373 447
351 69
181 151
24 192
129 86
31 203
340 239
324 260
223 206
136 450
435 445
331 249
286 94
355 313
46 430
201 189
89 441
489 267
402 271
316 303
492 14
203 292
500 320
327 104
69 1
73 413
203 241
438 152
251 472
276 26
500 210
310 364
134 102
296 422
444 101
283 432
143 361
152 423
500 204
467 33
467 472
439 74
29 252
266 388
146 21
482 31
242 153
287 28
455 134
480 451
279 161
312 333
92 309
402 376
262 89
150 71
310 453
89 122
274 363
201 492
251 68
352 68
486 6
42 348
241 143
243 48
251 463
307 457
115 273
171 82
27 282
65 402
465 333
207 394
436 171
266 491
345 463
248 300
464 247
381 137
8 447
333 151
88 255
41 149
315 474
403 318
306 211
449 66
250 52
442 317
366 51
426 401
394 370
295 144
362 256
138 232
103 452
213 16
225 106
251 166
398 324
467 337
240 284
344 290
1    图中可能存在孤立点

程序异常退出, 请检查代码"是否有数组越界等异常"或者"是否有语法错误"
Traceback (most recent call last):
File "/tmp/a.py3", line 48, in
main()
File "/tmp/a.py3", line 18, in main
adj[v].append(u) # 无向图，双向添加
IndexError: list index out of range
"""