SHARE
TWEET

Untitled

a guest Jan 27th, 2020 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #include <ext/pb_ds/detail/standard_policies.hpp>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. //#pragma comment(linker, "/stack:200000000")
  8. //#pragma GCC optimize("Ofast")
  9. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  10. //#pragma GCC optimize("unroll-loops")
  11. //#pragma GCC optimize("O3")
  12.  
  13. #define F first
  14. #define S second
  15. #define pb push_back
  16. #define llong   long long
  17. //#define int  llong
  18. #define ld long double
  19. #define pii pair <int, int>
  20. #define endl '\n'
  21.  
  22. #ifdef LOCAL
  23. #else
  24. #define cerr if(0) cerr
  25. #endif // LOCAL
  26.  
  27.  
  28.  
  29. using namespace std;
  30. using namespace __gnu_pbds;
  31.  
  32.  
  33. mt19937 gen(time(0));
  34.  
  35.  
  36. const int N = 1e5 + 10;
  37. const int M = 500 + 7;
  38. const int B = 1100;
  39. //const llong p = 2048;
  40. const int add1 = 39;
  41. //const llong per = 1e10;
  42. //const llong INF = 2e18;
  43. const int MOD1 = 1e18 + 7;
  44. const int MOD = 1e9 + 7;
  45. const int rx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
  46. const int ry[8] = {2, -2, 2, -2, 1, -1, 1, -1};
  47. const char rr[12]= {31, 28, 31, 30, 31, 31, 30, 31, 30, 31, 30, 31};
  48. typedef cc_hash_table< int, int, hash<int>, equal_to<int>, direct_mask_range_hashing<int>, hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true >> ht;
  49.  
  50. template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
  51.  
  52. vector < vector <int> > G;
  53. vector < set <int> > g;
  54. int from[N];
  55. int used[N];
  56. int was[N];
  57. int has[N];
  58. int sz = 0, best = -1, OK = 1;
  59.  
  60. void check(int v){
  61.     has[v] = 1;
  62.     for(int to : G[v]){
  63.         if (has[to]) continue;
  64.         check(to);
  65.     }
  66. }
  67.  
  68. void dfs(int v, int k){
  69.     used[v] = k;
  70.     sz++;
  71.     if (best < 0) best = v;
  72.     if (g[best].size() < g[v].size()){
  73.         best = v;
  74.     }
  75.     for(int to : g[v]){
  76.         if (used[to] == k || was[to]) continue;
  77.         dfs(to, k);
  78.     }
  79. }
  80.  
  81. void solve(int v, int k = 1, int pr = -1){
  82.     sz = 0;
  83.     best = -1;
  84.     dfs(v, k);
  85.     if (best < 0) OK = 0;
  86.     if (best < 0) return;
  87.     if (g[best].size() != sz - 1) OK = 0;
  88.     if (g[best].size() != sz - 1) return;
  89.     from[best] = pr;
  90.     was[best] = 1;
  91.     int REAL = best;
  92. //    cerr << best + 1 <<  ' ' << pr + 1 <<   endl;
  93. //    cerr << "go: ";
  94.     for(int to : g[best]){
  95.         g[to].erase(best);
  96. //        cerr << to + 1 << ' ';
  97.     }
  98. //    cerr << endl;
  99.      for(int to : g[REAL]){
  100.         if (!OK) return;
  101. //       if (!was[to]) cerr << "i'm go on " << to + 1 << ' ' << REAL + 1 << endl;
  102.        if (!was[to]) solve(to, k + 1, REAL);
  103. //        cerr << "return " << endl;
  104.     }
  105. }
  106.  
  107.  
  108.  
  109. main() {
  110.     ios_base::sync_with_stdio(0);
  111.     cin.tie(0);
  112.     cout.tie(0);
  113. //    srand(time(0));
  114. #ifdef LOCAL
  115.     freopen("input.txt", "r", stdin);
  116.     freopen("output1.txt", "w", stdout);
  117. #else
  118. //    freopen("wormsort.in", "r", stdin);
  119. //    freopen("wormsort.out", "w", stdout);
  120. #endif
  121.  
  122.  
  123.     int t;
  124.     cin >> t;
  125.     while(t--){
  126.         int n, m;
  127.         cin >> n >> m;
  128.         g.clear();
  129.         g.resize(n);
  130.  
  131.         G.clear();
  132.         G.resize(n);
  133.         for(int i = 0; i < n; i++){
  134.             was[i] = 0;
  135.             used[i] = 0;
  136.             from[i] = -2;
  137.             has[i] = 0;
  138.         }
  139.         OK = 1;
  140.         for(int i = 0; i < m; i++){
  141.             int x, y;
  142.             cin >> x >> y;
  143.             x--;
  144.             y--;
  145.             g[x].insert(y);
  146.             g[y].insert(x);
  147.         }
  148.  
  149.  
  150.         solve(0);
  151.         if (!OK){
  152.             cout << "No" << endl;
  153.             continue;
  154.         }
  155.         for(int i = 0; i < n; i++){
  156.             if (from[i] >= 0){
  157.                 G[i].pb(from[i]);
  158.                 G[from[i]].pb(i);
  159.             }
  160.             if (from[i] == -2) {
  161.                     OK = 0;
  162.                     break;
  163.             }
  164.         }
  165.  
  166.         check(0);
  167.         bool ok = 1;
  168.  
  169.         for(int i = 0; i < n; i++){
  170.             if (!has[i]) {
  171.                     ok = 0;
  172.                     break;
  173.             }
  174.  
  175.         }
  176.  
  177.         if (!ok || !OK){
  178.             cout << "No" << endl;
  179.             continue;
  180.         }
  181.  
  182.         cout << "Yes" << endl;
  183.         for(int i = 0; i < n; i++){
  184.             cout << from[i]  + 1 << ' ';
  185.         }
  186.         cout << endl;
  187.  
  188.  
  189.  
  190.  
  191.     }
  192.  
  193.  
  194. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top