All submissions for this problem are available.We have a graph with $N$ nodes (numbered $1$ through $N$). For each valid $u$ and $v$, there is an undirected edge between nodes $u$ and $v$ if $v$ is a prime divisor of $u$ or $u$ is a prime divisor of $v$. You should answer $Q$ queries. In each query, you should find the length of the shortest path between two given nodes $a$ and $b$ or determine that there is no path between them. **Note**: Because of large I/O, please use fast I/O methods. ### Input - The first line of the input contains a single integer $N$. - The second line contains a single integer $Q$. - Each of the next $Q$ lines contains two space-separated integers $a$ and $b$ describing a query. ### Output For each query, print a single line containing one integer - the distance between the nodes or $-1$ if the nodes are not connected. ### Constraints - $1 \le N, Q \le 10^6$ - $2 \le a, b \le N$ ### Example Input ``` 20 3 2 3 2 6 2 9 ``` ### Example Output ``` 2 1 3 ``` ### Explanation For $a = 2$ and $b = 9$, one possible shortest path is $2 \rightarrow 6 \rightarrow 3 \rightarrow 9$.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.