I checked two accepted solution But They are giving different output in same test case.
AC code 1:  https://paste.ubuntu.com/p/RwtFH2s4xK/
AC code 2:  https://paste.ubuntu.com/p/vmrXrdcJN6/

Tese case :
25 28
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
5 19
19 20
20 21
21 22
22 23
23 24
24 25
25 14
15 22
6 22
1 10 21

Output in code 1 : 2
Output in code 2 : 3

Answer should be : 2