Guest User

Untitled

a guest
Sep 10th, 2015
897
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <sstream>
  3. #include <fstream>
  4.  
  5. #include <algorithm>
  6. #include <numeric>
  7.  
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <bitset>
  12. #include <deque>
  13.  
  14. #include <ctime>
  15. #include <cmath>
  16. #include <cstdlib>
  17. #include <cstdio>
  18. #include <cassert>
  19.  
  20. #define pb push_back
  21. #define pbk pop_back
  22. #define mp make_pair
  23. #define fs first
  24. #define sc second
  25. #define all(x) (x).begin(), (x).end()
  26. #define len(a) ((int) (a).size())
  27. #define endl '\n'
  28.  
  29. #ifdef CUTEBMAING
  30. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  31. #else
  32. #define eprintf(...) ({})
  33. #endif
  34.  
  35. using namespace std;
  36.  
  37. typedef long long int64;
  38. typedef long double ld;
  39. typedef unsigned long long lint;
  40.  
  41. const int inf = (1 << 30) - 1;
  42. const int64 linf = (1ll << 62) - 1;
  43. const int N = 1e6;
  44.  
  45. int n;
  46. int p[N];
  47.  
  48. int division[2][N];
  49. int dln[2];
  50. bool u[N];
  51.  
  52. int main(){
  53.     cin >> n;
  54.     for (int i = 0; i < n; i++){
  55.         scanf("%d", &p[i]);
  56.         p[i]--;
  57.     }
  58.     int index1 = -1, index2 = -1;
  59.     for (int i = 0; i < n; i++){
  60.         if (p[i] == i)
  61.             index1 = i;
  62.         if (p[p[i]] == i)
  63.             index2 = i;
  64.     }
  65.     if (index1 != -1){
  66.         puts("YES");
  67.         for (int i = 0; i < n; i++)
  68.             if (index1 != i)
  69.                 printf("%d %d\n", index1 + 1, i + 1);
  70.         return 0;
  71.     }
  72.     if (index2 != -1){
  73.         bool flag = true;
  74.         dln[0] = dln[1] = 0;
  75.         fill_n(u, n, 0);
  76.         u[index2] = u[p[index2]] = 1;
  77.         for (int i = 0; i < n; i++)
  78.             if (!u[i]){
  79.                 u[i] = 1;
  80.                 division[0][dln[0]++] = i;
  81.                 int curI = p[i], step = 1;
  82.                 while (curI != i){
  83.                     u[curI] = 1;
  84.                     division[step][dln[step]++] = curI;
  85.                     step ^= 1;
  86.                     curI = p[curI];
  87.                 }
  88.                 if (step == 1){
  89.                     flag = false;
  90.                     break;
  91.                 }
  92.             }
  93.         if (!flag){
  94.             puts("NO");
  95.             return 0;
  96.         }
  97.         puts("YES");
  98.         printf("%d %d\n", index2 + 1, p[index2] + 1);
  99.         for (int i = 0; i < dln[0]; i++)
  100.             printf("%d %d\n", index2 + 1, division[0][i] + 1);
  101.         for (int i = 0; i < dln[1]; i++)
  102.             printf("%d %d\n", p[index2] + 1, division[1][i] + 1);
  103.         return 0;
  104.     }
  105.     puts("NO");
  106.     return 0;
  107. }
RAW Paste Data