题目大意 以如下方式给出一张带权无向图：点集为
{ 1 , 2 , … , n } \{1,2,\dots,n\} { 1 , 2 , … , n } ，边有两种：
∀ 1 ≤ i < n \forall 1\leq i<n ∀1 ≤ i < n ，
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 之间有边权为
0 0 0 的边；
∀ 1 ≤ i < j ≤ n \forall 1\leq i<j\leq n ∀1 ≤ i < j ≤ n 且
gcd ( i , j ) = 1 , j − i > 1 \gcd(i,j)=1,j-i>1 g cd( i , j ) = 1 , j − i > 1 ，
( i , j ) (i,j) ( i , j ) 之间有边权为
1 1 1 的边。
现在给定起点
a a a 和终点
b b b （保证
a ≠ b a\neq b a = b ），构造一条从
a a a 开始，以
b b b 结束的权值和最小的哈密顿路径（即经过每个点恰好一次），或报告无解。
2 ≤ n ≤ 2 × 10 5 2\leq n\leq 2\times10^5 2 ≤ n ≤ 2 × 1 0 5 ，
1 ≤ a , b ≤ n 1\leq a,b\leq n 1 ≤ a , b ≤ n 。
解题过程 不妨设
a < b a<b a < b ，否则交换
a , b a,b a , b 并将路径首尾翻转即可。
观察到边权为
1 1 1 的边实际上是很多的，所有可以猜想路径权值和较小。注意到路径权值和实际上就是有多少条
( i , i + 1 ) (i,i+1) ( i , i + 1 ) 的边没有经过，称这种边为"断边"。由于
a , b a,b a , b 为路径端点，所以
( a , a + 1 ) (a,a+1) ( a , a + 1 ) 和
( a − 1 , a ) (a-1,a) ( a − 1 , a ) 中至少一条断边，
( b , b + 1 ) (b,b+1) ( b , b + 1 ) 和
( b − 1 , b ) (b-1,b) ( b − 1 , b ) 中至少一条断边，即当
1 < a < b < n 1<a<b<n 1 < a < b < n 且
b − a > 1 b-a>1 b − a > 1 时答案至少为
2 2 2 ，故可以分类讨论所有答案不超过
2 2 2 的情况。
（下文中
a → b a\to b a → b 表示边权为
0 0 0 的边，要求
∣ a − b ∣ = 1 |a-b|=1 ∣ a − b ∣ = 1 ；
a ⇒ b a\Rightarrow b a ⇒ b 表示边权为
1 1 1 的边，要求
gcd ( a , b ) = 1 \gcd(a,b)=1 g cd( a , b ) = 1 ；
a ⇝ b a\leadsto b a ⇝ b 表示通过
0 0 0 的边从
a a a 到
b b b 的路径，即
a < b a<b a < b 时为
a → a + 1 → ⋯ → b a\to a+1\to\dots\to b a → a + 1 → ⋯ → b ，
a > b a>b a > b 时为
a → a − 1 → ⋯ → b a\to a-1\to\dots\to b a → a − 1 → ⋯ → b ，
a = b a=b a = b 时即表示单点
a a a ）：
只有 a ⇝ b a\leadsto b a ⇝ b a = 1 , b = n a=1,b=n a = 1 , b = n
a ⇝ 1 ⇒ n ⇝ b a\leadsto 1\Rightarrow n\leadsto b a ⇝ 1 ⇒ n ⇝ b ，此时要求
a + 1 = b a+1=b a + 1 = b ；
a ⇝ 1 ⇒ a + 1 ⇝ b a\leadsto 1\Rightarrow a+1\leadsto b a ⇝ 1 ⇒ a + 1 ⇝ b ，此时要求
b = n b=n b = n ；
a ⇝ b − 1 ⇒ n ⇝ b a\leadsto b-1\Rightarrow n\leadsto b a ⇝ b − 1 ⇒ n ⇝ b ，此时要求
a = 1 a=1 a = 1 且
gcd ( n , b − 1 ) = 1 \gcd(n,b-1)=1 g cd( n , b − 1 ) = 1 。
a ⇝ 1 ⇒ b − 1 ⇝ a + 1 ⇒ n ⇝ b a\leadsto 1\Rightarrow b-1\leadsto a+1\Rightarrow n\leadsto b a ⇝ 1 ⇒ b − 1 ⇝ a + 1 ⇒ n ⇝ b ，要求
gcd ( a + 1 , n ) = 1 \gcd(a+1,n)=1 g cd( a + 1 , n ) = 1 ；
a ⇝ 1 ⇒ a + 1 ⇝ b − 1 ⇒ n ⇝ b a\leadsto 1\Rightarrow a+1\leadsto b-1\Rightarrow n\leadsto b a ⇝ 1 ⇒ a + 1 ⇝ b − 1 ⇒ n ⇝ b ，要求
gcd ( b − 1 , n ) = 1 \gcd(b-1,n)=1 g cd( b − 1 , n ) = 1 ；
a ⇝ b − 1 ⇒ 1 ⇝ a − 1 ⇒ n ⇝ b a\leadsto b-1\Rightarrow 1\leadsto a-1\Rightarrow n\leadsto b a ⇝ b − 1 ⇒ 1 ⇝ a − 1 ⇒ n ⇝ b ，要求
gcd ( a − 1 , n ) = 1 \gcd(a-1,n)=1 g cd( a − 1 , n ) = 1 ；
a ⇝ b − 1 ⇒ a − 1 ⇝ 1 ⇒ n ⇝ b a\leadsto b-1\Rightarrow a-1\leadsto 1\Rightarrow n\leadsto b a ⇝ b − 1 ⇒ a − 1 ⇝ 1 ⇒ n ⇝ b ，要求
gcd ( a − 1 , b − 1 ) = 1 \gcd(a-1,b-1)=1 g cd( a − 1 , b − 1 ) = 1 ；
a ⇝ 1 ⇒ b + 1 ⇝ n ⇒ a + 1 ⇝ b a\leadsto 1\Rightarrow b+1\leadsto n\Rightarrow a+1\leadsto b a ⇝ 1 ⇒ b + 1 ⇝ n ⇒ a + 1 ⇝ b ，要求
gcd ( a + 1 , n ) = 1 \gcd(a+1,n)=1 g cd( a + 1 , n ) = 1 （这实际上和 1 解决的是同一种情况）；
a ⇝ 1 ⇒ n ⇝ b + 1 ⇒ a + 1 ⇝ b a\leadsto 1\Rightarrow n\leadsto b+1\Rightarrow a+1\leadsto b a ⇝ 1 ⇒ n ⇝ b + 1 ⇒ a + 1 ⇝ b ，要求
gcd ( a + 1 , b + 1 ) = 1 \gcd(a+1,b+1)=1 g cd( a + 1 , b + 1 ) = 1 。
考虑剩余情况，即上面的互质条件都不满足，最简单的例子就是
n n n 为偶数，
a , b a,b a , b 均为奇数。
简单举例尝试一下，可以发现这种情况似乎不存在构造。事实上，这就是本题的无解情况，证明如下：采用上面的“断边”来刻画哈密顿路径，那么每条断边的端点一定是一奇一偶，又因为
1 1 1 为奇数，
n n n 为偶数，所以设断点将
[ 1 , n ] [1,n] [ 1 , n ] 分成了
c c c 段（这意味着如果存在路径，边权和为
c − 1 c-1 c − 1 ），那么所有段的左右端点加起来共有
c c c 个奇数
c c c 个偶数。又因为起点
a a a 终点
b b b 均为奇数，所以剩余的
c − 2 c-2 c − 2 个奇数
c c c 个偶数分成
c − 1 c-1 c − 1 对（每对代表一条段之间的连边），必然有一对偶数，那么此时就不可能互质，这两个点之间不可能存在边。
上面的证明也提示了考虑奇偶性，所以对于剩余的情况考虑将
( 1 , 2 ) (1,2) ( 1 , 2 ) 设为断边，这样
2 2 2 和所有奇数之间都有权值为
1 1 1 的边：
对于
a = 1 a=1 a = 1 （这就是上面没讨论的权值和为
2 2 2 的情况）：
n n n 为奇数：
1 ⇒ b − 1 ⇝ 2 ⇒ n ⇝ b 1\Rightarrow b-1\leadsto 2\Rightarrow n\leadsto b 1 ⇒ b − 1 ⇝ 2 ⇒ n ⇝ b ；
b b b 为偶数：
1 ⇒ n ⇝ b + 1 ⇒ 2 ⇝ b 1\Rightarrow n\leadsto b+1\Rightarrow 2\leadsto b 1 ⇒ n ⇝ b + 1 ⇒ 2 ⇝ b 。
n n n 为奇数：
a ⇝ 2 ⇒ n ⇝ b + 1 ⇒ 1 ⇒ a + 1 ⇝ b a\leadsto2\Rightarrow n\leadsto b+1\Rightarrow 1\Rightarrow a+1\leadsto b a ⇝ 2 ⇒ n ⇝ b + 1 ⇒ 1 ⇒ a + 1 ⇝ b ；
b b b 为偶数：
a ⇝ 2 ⇒ b + 1 ⇝ n ⇒ 1 ⇒ a + 1 ⇝ b a\leadsto2\Rightarrow b+1\leadsto n\Rightarrow 1\Rightarrow a+1\leadsto b a ⇝ 2 ⇒ b + 1 ⇝ n ⇒ 1 ⇒ a + 1 ⇝ b ；
a a a 为偶数：
a ⇝ 2 ⇒ a + 1 ⇝ b − 1 ⇒ 1 ⇒ n ⇝ b a\leadsto2\Rightarrow a+1\leadsto b-1\Rightarrow 1\Rightarrow n\leadsto b a ⇝ 2 ⇒ a + 1 ⇝ b − 1 ⇒ 1 ⇒ n ⇝ b ；
除了分类讨论外，另一种可能的思路是暴力枚举断边（上面用到的断边只有五种可能）并枚举每段之间的顺序、每段内的方向并检验，可以避免讨论。