fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sz 200100
  4. #define MOD 1000000007
  5. #define ll long long
  6. int ch[sz];
  7. bool vis[sz];
  8. int dep[sz];
  9. int jump[20][sz];
  10. bool partofcycle[sz];
  11. int lenofcycle[sz];
  12. void dfs(int s)
  13. {
  14. vis[s] = 1;
  15. if (!vis[ch[s]])
  16. dfs(ch[s]);
  17. else if (!dep[ch[s]])
  18. {
  19. int v = s;
  20. int len = 0;
  21. do
  22. {
  23. partofcycle[v] = 1;
  24. v = ch[v];
  25. len++;
  26. }
  27. while (v != s);
  28. do
  29. {
  30. lenofcycle[v] = len;
  31. v = ch[v];
  32. }
  33. while (v != s);
  34. }
  35. dep[s] = dep[ch[s]] + 1;
  36. }
  37. bool anc(int a, int b, int diff)
  38. {
  39. for (int i = 0; i < 20; i++)
  40. {
  41. if (diff & (1 << i))
  42. a = jump[i][a];
  43. }
  44. return (a == b);
  45. }
  46. int main()
  47. {
  48. ios::sync_with_stdio(0);
  49. cin.tie(0);
  50. cout.tie(0);
  51. int n, m;
  52. cin >> n >> m;
  53. for (int i = 1; i <= n; i++)
  54. {
  55. cin >> ch[i];
  56. jump[0][i] = ch[i];
  57. }
  58. for (int i = 1; i <= n; i++)
  59. {
  60. if (!vis[i])
  61. dfs(i);
  62. }
  63. for (int i = 1; i < 20; i++)
  64. {
  65. for (int j = 1; j <= n; j++)
  66. jump[i][j] = jump[i - 1][jump[i - 1][j]];
  67. }
  68. while (m--)
  69. {
  70. int a, b;
  71. cin >> a >> b;
  72. int u = a; int v = b;
  73. if (a == b)
  74. {
  75. cout << "0\n";
  76. continue;
  77. }
  78. int diff = dep[a] - dep[b];
  79. if (diff > 0 && anc(a, b, diff))
  80. {
  81. cout << diff << "\n";
  82. continue;
  83. }
  84. if (partofcycle[b])
  85. {
  86. diff = dep[a] - dep[b] + lenofcycle[b];
  87. if (diff > 0 && anc(a, b, diff))
  88. {
  89. cout << diff << "\n";
  90. continue;
  91. }
  92. }
  93. cout << "-1\n";
  94. }
  95. return 0;
  96. }
Success #stdin #stdout 0s 4520KB
stdin
10 1
2 3 4 5 6 7 8 9 10 1
3 1
stdout
8