Advertisement
Guest User

Untitled

a guest
Nov 22nd, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.79 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int ms = 5e5+5;
  5.  
  6. int arr[ms];
  7. vector<pair<int, int>> edges;
  8.  
  9. main() {
  10. int n;
  11. cin >> n;
  12. for(int i = 0; i < n; i++) {
  13. int u, v;
  14. cin >> u >> v;
  15. if(v != n) {
  16. cout << "NO\n";
  17. return 0;
  18. }
  19. arr[u]++;
  20. }
  21. sort(arr, arr+n);
  22. queue<int> q;
  23. for(int i = 1; i < n; i++) {
  24. if(arr[i] == 0) q.push(i);
  25. else {
  26. int cur = n;
  27. for(int j = 1; j < arr[i]; j++) {
  28. if(q.empty()) {
  29. cout << "NO\n";
  30. return 0;
  31. }
  32. int u = q.front();
  33. q.pop();
  34. edges.emplace_back(cur, u);
  35. }
  36. edges.emplace_back(cur, i);
  37. }
  38. }
  39. cout << "YES\n";
  40. for(auto e : edges) {
  41. cout << e.first << ' ' << e.second << '\n';
  42. }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement