Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/detail/standard_policies.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC optimize("O3")
- #define F first
- #define S second
- #define pb push_back
- #define llong long long
- //#define int llong
- #define ld long double
- #define pii pair <int, int>
- #define endl '\n'
- #ifdef LOCAL
- #else
- #define cerr if(0) cerr
- #endif // LOCAL
- using namespace std;
- using namespace __gnu_pbds;
- mt19937 gen(time(0));
- const int N = 1e5 + 10;
- const int M = 500 + 7;
- const int B = 1100;
- //const llong p = 2048;
- const int add1 = 39;
- //const llong per = 1e10;
- //const llong INF = 2e18;
- const int MOD1 = 1e18 + 7;
- const int MOD = 1e9 + 7;
- const int rx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
- const int ry[8] = {2, -2, 2, -2, 1, -1, 1, -1};
- const char rr[12]= {31, 28, 31, 30, 31, 31, 30, 31, 30, 31, 30, 31};
- 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;
- template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
- vector < vector <int> > G;
- vector < set <int> > g;
- int from[N];
- int used[N];
- int was[N];
- int has[N];
- int sz = 0, best = -1, OK = 1;
- void check(int v){
- has[v] = 1;
- for(int to : G[v]){
- if (has[to]) continue;
- check(to);
- }
- }
- void dfs(int v, int k){
- used[v] = k;
- sz++;
- if (best < 0) best = v;
- if (g[best].size() < g[v].size()){
- best = v;
- }
- for(int to : g[v]){
- if (used[to] == k || was[to]) continue;
- dfs(to, k);
- }
- }
- void solve(int v, int k = 1, int pr = -1){
- sz = 0;
- best = -1;
- dfs(v, k);
- if (best < 0) OK = 0;
- if (best < 0) return;
- if (g[best].size() != sz - 1) OK = 0;
- if (g[best].size() != sz - 1) return;
- from[best] = pr;
- was[best] = 1;
- int REAL = best;
- // cerr << best + 1 << ' ' << pr + 1 << endl;
- // cerr << "go: ";
- for(int to : g[best]){
- g[to].erase(best);
- // cerr << to + 1 << ' ';
- }
- // cerr << endl;
- for(int to : g[REAL]){
- if (!OK) return;
- // if (!was[to]) cerr << "i'm go on " << to + 1 << ' ' << REAL + 1 << endl;
- if (!was[to]) solve(to, k + 1, REAL);
- // cerr << "return " << endl;
- }
- }
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- // srand(time(0));
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output1.txt", "w", stdout);
- #else
- // freopen("wormsort.in", "r", stdin);
- // freopen("wormsort.out", "w", stdout);
- #endif
- int t;
- cin >> t;
- while(t--){
- int n, m;
- cin >> n >> m;
- g.clear();
- g.resize(n);
- G.clear();
- G.resize(n);
- for(int i = 0; i < n; i++){
- was[i] = 0;
- used[i] = 0;
- from[i] = -2;
- has[i] = 0;
- }
- OK = 1;
- for(int i = 0; i < m; i++){
- int x, y;
- cin >> x >> y;
- x--;
- y--;
- g[x].insert(y);
- g[y].insert(x);
- }
- solve(0);
- if (!OK){
- cout << "No" << endl;
- continue;
- }
- for(int i = 0; i < n; i++){
- if (from[i] >= 0){
- G[i].pb(from[i]);
- G[from[i]].pb(i);
- }
- if (from[i] == -2) {
- OK = 0;
- break;
- }
- }
- check(0);
- bool ok = 1;
- for(int i = 0; i < n; i++){
- if (!has[i]) {
- ok = 0;
- break;
- }
- }
- if (!ok || !OK){
- cout << "No" << endl;
- continue;
- }
- cout << "Yes" << endl;
- for(int i = 0; i < n; i++){
- cout << from[i] + 1 << ' ';
- }
- cout << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement