서로소 그래프와 쿼리

$N$개의 정점으로 구성된 무향 그래프를 생각하자. 각 정점은 $1$번부터 $N$번까지 정수 번호가 부여되어 있으며, 어느 두 정점도 번호를 공유하지 않는다.

이때 $1$ 이상 $N$ 이하의 서로 다른 두 양의 정수 $A$와 $B$에 대하여 다음 조건을 만족하는 그래프를 서로소 그래프라 한다.

• $A$와 $B$가 서로소라면 $A$번 정점과 $B$번 정점을 연결하는 간선이 단 하나 존재한다.
• $A$와 $B$가 서로소가 아니라면 $A$번 정점과 번 정점을 연결하는 간선은 존재하지 않는다.

서로소 그래프에서 최단 거리를 구하는 $Q$개의 쿼리를 해결해 보자.

첫 줄에 정점의 개수 $N$과 쿼리의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 10^6$, $1\le Q\le {}^{}$)

각 쿼리에 대해, $A$번 정점과의 최단 거리가 최대인 정점의 번호를 $B$라 하자.

$A$번 정점과 $B$번 정점 사이의 최단 거리를 줄바꿈으로 구분하여 출력한다.

단, 임의의 정점 $X$에 대해 $X$와 사이의 최단 거리는 으로 정의한다.