codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1656.md (19712B)


      1 Source: https://codeforces.com/blog/entry/101211
      2 
      3 [1656A - Good Pairs](/contest/1656/problem/A)
      4 
      5 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main() {
     19 	int t;
     20 	cin >> t;
     21 	while(t--) {
     22 		int n;
     23 		cin >> n;
     24 		int minv = 1e9+1;
     25 		int maxv = -1;
     26 		int mini;
     27 		int maxi;
     28 		for(int i=0; i < n; ++i) {
     29 			int a;
     30 			cin >> a;
     31 			if(a > maxv) {
     32 				maxi = i+1;
     33 				maxv = a;
     34 			}
     35 			if(a < minv) {
     36 				mini = i+1;
     37 				minv =  a;
     38 			}
     39 		}
     40 		cout << mini << " " << maxi << endl;
     41 	}
     42  
     43 }
     44 ```
     45 
     46 [1656B - Subtract Operation](/contest/1656/problem/B)
     47 
     48 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [xpov1LL](/profile/xpov1LL "Candidate Master xpov1LL")
     49 
     50 **Solution**
     51 
     52 Tutorial is loading...
     53 
     54 **Code**
     55 
     56 ```
     57 #include<iostream>
     58 #include<vector>
     59 #include<algorithm>
     60 using namespace std;
     61  
     62 int main() {
     63     int t;
     64     cin >> t;
     65     while(t--) {
     66         int n, a;
     67     	cin >> n >> a;
     68     	vector<int> v(n);
     69     	for(int& x : v) cin >> x;
     70     	bool ans = false;
     71     	if(n == 1) ans = (v[0] == a);
     72     	else {
     73     		sort(v.begin(), v.end());
     74     		int i = 0;
     75     		int j = 1;
     76     		while(j < n and i < n) {
     77     			if(v[i] + abs(a) == v[j]) {
     78     				ans = true;
     79     				break;
     80     			}
     81     			else if(v[i] + abs(a) < v[j]) ++i;
     82     			else ++j;
     83     		}
     84     	}
     85     	cout << (ans? "YES" : "NO") << '\n';   
     86     }
     87 }
     88 ```
     89 
     90 [1656C - Make Equal With Mod](/contest/1656/problem/C)
     91 
     92 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
     93 
     94 **Solution**
     95 
     96 Tutorial is loading...
     97 
     98 **Code**
     99 
    100 ```
    101 #include<bits/stdc++.h>
    102  
    103 using namespace std;
    104  
    105 typedef vector<int> vi;
    106  
    107  
    108 int main() {
    109 	int t;
    110 	cin >> t;
    111 	while(t--) {
    112 		int n;
    113 		cin >> n;
    114 		vi a(n);
    115 		for(int i=0; i < n; ++i) cin >> a[i];
    116 		sort(a.begin(), a.end());
    117 		bool one = false;
    118 		bool consec = false;
    119 		for(int i=0; i < n; ++i) {
    120 			if(a[i] == 1) one = true;
    121 			if(i < n-1 && a[i]+1 == a[i+1]) consec = true;
    122 		}
    123  
    124 		cout << ((one && consec) ? "NO" : "YES") << endl;
    125 	}
    126  
    127 }
    128 ```
    129 
    130 [1656D - K-good](/contest/1656/problem/D)
    131 
    132 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    133 
    134 **Solution**
    135 
    136 Tutorial is loading...
    137 
    138 **Code**
    139 
    140 ```
    141 #include<bits/stdc++.h>
    142  
    143 using namespace std;
    144  
    145 #define endl '\n'
    146  
    147 typedef long long ll;
    148  
    149 int main() {
    150     ios::sync_with_stdio(false);
    151 	int T;
    152 	cin >> T;
    153 	while(T--) {
    154 		ll n;
    155 		cin >> n;
    156 		ll x = n;
    157 		while(x % 2 == 0) x /= 2;
    158 		if(x == 1) {
    159 			cout << -1 << endl;
    160 		}
    161 		else if(x <= 2e9 && (x*(x+1))/2 <= n) {
    162 			cout << x << endl;
    163 		}
    164 		else {
    165 			cout << 2*(n/x) << endl;
    166 		}
    167 	}
    168 }
    169 ```
    170 
    171 [1656E - Equal Tree Sums](/contest/1656/problem/E)
    172 
    173 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    174 
    175 **Solution**
    176 
    177 Tutorial is loading...
    178 
    179 **Code**
    180 
    181 ```
    182 #include<bits/stdc++.h>
    183  
    184 using namespace std;
    185  
    186 typedef vector<int> vi;
    187 typedef vector<vi> vvi;
    188  
    189 vvi al;
    190 vi ans;
    191  
    192 void dfs(int u, int p, int c) {
    193 	ans[u] = ((int)al[u].size())*c;
    194 	for(int v : al[u]) {
    195 		if(v != p) {
    196 			dfs(v, u, -c);
    197 		}
    198 	}
    199 }
    200  
    201 int main() {
    202 	int T;
    203 	cin >> T;
    204 	while(T--) {
    205 		int n;
    206 		cin >> n;
    207 		al = vvi(n);
    208 		for(int i=0; i < n-1; ++i) {
    209 			int u, v;
    210 			cin >> u >> v;
    211 			u--;
    212 			v--;
    213 			al[u].push_back(v);
    214 			al[v].push_back(u);
    215 		}
    216 		ans = vi(n);
    217 		dfs(0, -1, 1);
    218 		for(int i=0; i < n; ++i) {
    219 			cout << ans[i];
    220 			if(i < n-1) cout << " ";
    221 		}
    222 		cout << endl;
    223 	}
    224 }
    225 ```
    226 
    227 [1656F - Parametric MST](/contest/1656/problem/F)
    228 
    229 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    230 
    231 **Solution**
    232 
    233 Tutorial is loading...
    234 
    235 **Code**
    236 
    237 ```
    238 #include<bits/stdc++.h>
    239 
    240 using namespace std;
    241 
    242 typedef long long ll;
    243 typedef vector<ll> vi;
    244 
    245 int main() {
    246 	int T;
    247 	cin >> T;
    248 	while(T--) {
    249 		ll n;
    250 		cin >> n;
    251 		vi a(n);
    252 		ll tsum = 0;
    253 		for(int i=0; i < n; ++i) {
    254 			cin >> a[i];
    255 			tsum += a[i];
    256 		}
    257 		sort(a.begin(), a.end());
    258 		if(a[n-1]*(n-2) + tsum < 0 || a[0]*(n-2) + tsum > 0) {
    259 			cout << "INF" << endl;
    260 			continue;
    261 		}
    262 
    263 		ll cslope = a[n-1]*(n-2) + tsum;
    264 		ll cvalue = -(n-1)*a[n-1]*a[n-1];
    265 		
    266 
    267 		ll ans = cvalue;
    268 		for(ll i=1; i < n; ++i) {
    269 			ll d = a[n-i]-a[n-i-1];
    270 			cvalue += cslope*d;
    271 			ans = max(cvalue, ans);
    272 
    273 			cslope += a[0]-a[n-1];
    274 
    275 		}
    276 		cout << ans << endl;
    277 	}
    278 }
    279 ```
    280 
    281 [1656G - Cycle Palindrome](/contest/1656/problem/G)
    282 
    283 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    284 
    285 **Solution**
    286 
    287 Tutorial is loading...
    288 
    289 **Code**
    290 
    291 ```
    292 #include<bits/stdc++.h>
    293 
    294 using namespace std;
    295 
    296 typedef vector<int> vi;
    297 typedef vector<vi> vvi;
    298 
    299 vi obtain_p_permutation(const vi& a) {
    300 	int n = a.size();
    301 	vi pp(n, -1);
    302 	vi p(n);
    303 	int cp = 0;
    304 	vi cnt(n);
    305 	for(int i=0; i < n; ++i) {
    306 		cnt[a[i]]++;
    307 	}
    308 	for(int i=0; i < n; ++i) {
    309 		if(pp[a[i]] == -1) {
    310 			if(cnt[a[i]] == 1) {
    311 				p[i] = n/2;
    312 			}
    313 			else {
    314 				p[i] = cp;
    315 				pp[a[i]] = n-cp-1;
    316 				cp++;
    317 				cnt[a[i]]--;
    318 			}
    319 		}
    320 		else {
    321 			p[i] = pp[a[i]];
    322 			pp[a[i]] = -1;
    323 			cnt[a[i]]--;
    324 		}
    325 	}
    326 	return p;
    327 }
    328 
    329 vvi find_cycles(vi p, vi& in_cyc) {
    330 	int n = p.size();
    331 	vi vis = vi(n);
    332 	vvi cycles;
    333 	for(int i=0; i < n; ++i) {
    334 		if(!vis[i]) {
    335 			vi cyc;
    336 			int v = i;
    337 			while(!vis[v]) {
    338 				cyc.push_back(v);
    339 				in_cyc[v] = cycles.size();
    340 				vis[v] = true;
    341 				v = p[v];
    342 			}
    343 			cycles.push_back(cyc);
    344 		}
    345 	}
    346 	return cycles;
    347 }
    348 
    349 int find_set(vi& dsu, int x) {
    350 	if(dsu[x] == x) return x;
    351 	return dsu[x] = find_set(dsu, dsu[x]);
    352 }
    353 
    354 void solve() {
    355 	int n;
    356 	cin >> n;
    357 	vi a(n);
    358 	vi cnt(n);
    359 	for(int i=0; i < n; ++i) {
    360 		cin >> a[i];
    361 		a[i]--;
    362 		cnt[a[i]]++;
    363 	}
    364 	int odd_i = -1;
    365 	for(int i=0; i < n; ++i) {
    366 		if(cnt[i]%2 == 1) {
    367 			if(odd_i == -1) {
    368 				odd_i = i;
    369 			}
    370 			else {
    371 				odd_i = -2;
    372 			}
    373 		}
    374 	}
    375 	if(odd_i == -2) {
    376 		cout << "NO" << endl;
    377 	}
    378 	else if(odd_i != -1 && (cnt[odd_i] == 1 && odd_i == a[n/2])) {
    379 		cout << "NO" << endl;
    380 	}
    381 	else {
    382 
    383 		vi p = obtain_p_permutation(a);
    384 		if(odd_i != -1 && p[n/2] == n/2) {
    385 			for(int i=0; i < n; ++i) {
    386 				if(i != n/2 && a[i] == odd_i) {
    387 					p[n/2] = p[i];
    388 					p[i] = n/2;
    389 					break;
    390 				}
    391 			}
    392 		}
    393 		vi rp(n);
    394 		for(int i=0; i < n; ++i) {
    395 			rp[p[i]] = i;
    396 		}
    397 		vvi cycles;
    398 		vi in_cyc(n);
    399 		cycles = find_cycles(p, in_cyc);
    400 
    401 		vi dsu(n);
    402 		for(int i=0; i < n; ++i) dsu[i] = i;
    403 		for(int i=0; i < n; ++i) {
    404 			if(find_set(dsu, in_cyc[i]) != find_set(dsu, in_cyc[n-i-1])) {
    405 				dsu[find_set(dsu, in_cyc[i])] = find_set(dsu, in_cyc[n-i-1]);
    406 				int j1 = rp[i];
    407 				int j2 = rp[n-i-1];
    408 				p[j2] = i;
    409 				rp[i] = j2;
    410 				p[j1] = n-i-1;
    411 				rp[n-i-1] = j1;  
    412 			}
    413 		}
    414 		cycles = find_cycles(p, in_cyc);
    415 		int nc = cycles.size();
    416 	
    417 
    418 		vi prev_p = vi(p);
    419 		vi prev_rp = vi(rp);
    420 
    421 		for(int i=0; i < nc-1; ++i) {
    422 			int i0 = cycles[i][0];
    423 			int ip1 = cycles[(i+1)][0];
    424 			p[prev_rp[n-i0-1]] = ip1;
    425 			rp[ip1] = prev_rp[n-i0-1]; 
    426 		}
    427 		p[prev_rp[n-cycles[nc-1][0]-1]] = n-cycles[0][0]-1;
    428 		rp[n-cycles[0][0]-1] = prev_rp[n-cycles[nc-1][0]-1];
    429 		for(int i=0; i < nc-1; ++i) {
    430 			int i0 = cycles[i][0];
    431 			int ip1 = cycles[(i+1)][0];
    432 			p[prev_rp[i0]] = n-ip1-1;
    433 			rp[n-ip1-1] = prev_rp[i0];
    434 		}
    435 		p[prev_rp[cycles[nc-1][0]]] = cycles[0][0];
    436 		rp[cycles[0][0]] = prev_rp[cycles[nc-1][0]];
    437 
    438 		cout << "YES" << endl;
    439 		for(int i=0; i < n; ++i) {
    440 			cout << rp[i]+1 << " ";
    441 		}
    442 		cout << endl;
    443 
    444 	}
    445 	
    446 
    447 }
    448 
    449 int main() {
    450 	int T;
    451 	cin >> T;
    452 	while(T--) {
    453 		solve();
    454 	}
    455 }
    456 ```
    457 
    458 [1656H - Equal LCM Subsets](/contest/1656/problem/H)
    459 
    460 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    461 
    462 **Solution**
    463 
    464 Tutorial is loading...
    465 
    466 **Code**
    467 
    468 ```
    469 #include<bits/stdc++.h>
    470  
    471 using namespace std;
    472  
    473 typedef __int128 ll; 
    474 typedef vector<ll> vi;
    475 typedef vector<vi> vvi;
    476  
    477  
    478 ll read_ll() {
    479 	string s;
    480 	cin >> s;
    481 	ll x = 0;
    482 	for(int i=0; i < (int)s.length(); ++i) {
    483 		x *= 10;
    484 		x += ll(s[i]-'0');
    485 	}
    486 	return x;
    487 }
    488  
    489 void print_ll(ll x) {
    490 	vector<int> p;
    491 	while(x > 0) {
    492 		p.push_back((int)(x%10));
    493 		x /= 10;
    494 	}
    495 	reverse(p.begin(), p.end());
    496 	for(int y : p) cout << y;
    497 }
    498  
    499 inline ll ctz(ll x) {
    500 	long long a = x&((ll(1)<<ll(63))-ll(1));
    501 	long long b = x>>ll(63);
    502 	if(a == 0) return ll(63)+__builtin_ctzll(b);
    503 	return __builtin_ctzll(a);  
    504 }
    505  
    506 inline ll abll(ll x) {
    507 	return x >= 0 ? x : -x;
    508 }
    509  
    510 ll gcd(ll a, ll b) {
    511 	if(b == 0) return a;
    512 	if(a == 0) return b;
    513  
    514 	int az = ctz(a);
    515 	int bz = ctz(b);
    516 	int shift = min(az, bz);
    517 	b >>= bz;
    518  
    519 	while(a != 0) {
    520 		a >>= az;
    521 		ll diff = b-a;
    522 		if(diff) az = ctz(diff);
    523 		b = min(a, b);
    524 		a = abll(diff);
    525 	}
    526 	return b << shift;
    527 }
    528  
    529 void init_st(vi& st, const vi& v) {
    530 	int n = v.size();
    531 	for(int i=0; i < n; ++i) {
    532 		st[n+i] = v[i];
    533 	}
    534 	for(int i=n-1; i >= 1; --i) {
    535 		st[i] = gcd(st[2*i], st[2*i+1]);
    536 	}
    537 }
    538 
    539 void update_st(vi& st, int i, ll x) {
    540 	int n = (int)st.size() / 2;
    541 	int pos = n+i;
    542 	st[pos] = x;
    543 	while(pos > 1) {
    544 		pos /= 2;
    545 		st[pos] = gcd(st[2*pos], st[2*pos+1]);
    546 	}
    547 }
    548  
    549 void solve(const vi& a, const vi& b, vector<bool>& ai, vector<bool>& bi) {
    550 	int n = a.size();
    551 	int m = b.size();
    552 	vvi st_a = vvi(n, vi(2*m, 0));
    553 	vvi st_b = vvi(m, vi(2*n, 0));
    554 	for(int i=0; i < n; ++i) {
    555 		vi af(m);
    556 		for(int j=0; j < m; ++j) {
    557 			af[j] = a[i]/gcd(a[i], b[j]);
    558 		}
    559 		init_st(st_a[i], af);
    560 	}
    561 	for(int i=0; i < m; ++i) {
    562 		vi bf(n);
    563 		for(int j=0; j < n; ++j) {
    564 			bf[j] = b[i]/gcd(b[i], a[j]);
    565 		}
    566 		init_st(st_b[i], bf);
    567 	}
    568 	queue<int> dq;
    569 	for(int i=0; i < n; ++i) {
    570 		if(st_a[i][1] > 1) {
    571 		       	dq.push(i);
    572 			ai[i] = false;
    573 		}
    574 	}
    575 	for(int i=0; i < m; ++i) {
    576 		if(st_b[i][1] > 1) {
    577 		       	dq.push(n+i);
    578 			bi[i] = false;
    579 		}
    580 	}
    581 	while(!dq.empty()) {
    582 		int idx = dq.front();
    583 		dq.pop();
    584 		if(idx < n) {
    585 			int i = idx;
    586 			for(int j=0; j < m; ++j) {
    587 				if(bi[j]) {
    588 					update_st(st_b[j], i, b[j]);
    589 					if(st_b[j][1] > 1) {
    590 						dq.push(n+j);
    591 						bi[j] = false;
    592 					}
    593 				}
    594 			}
    595 		}
    596 		else {
    597 			int i = idx-n;
    598 			for(int j=0; j < n; ++j) {
    599 				if(ai[j]) {
    600 					update_st(st_a[j], i, a[j]);
    601 					if(st_a[j][1] > 1) { 
    602 						dq.push(j);
    603 						ai[j] = false;
    604 					}
    605 				}
    606 			}
    607 		}
    608 	}	
    609  
    610 }
    611  
    612  
    613  
    614 int main() {
    615 	int T;
    616 	cin >> T;
    617 	while(T--) {
    618 		int n, m;
    619 		cin >> n >> m;
    620 		vi a(n);
    621 		vi b(m);
    622 		for(int i=0; i < n; ++i) a[i] = read_ll();
    623 		for(int i=0; i < m; ++i) b[i] = read_ll();
    624 		vector<bool> ai(n, true);
    625 		vector<bool> bi(m, true);
    626 		solve(a, b, ai, bi);
    627 		int as = 0;
    628 		int bs = 0;
    629 		for(int i=0; i < n; ++i) {
    630 			if(ai[i]) as++;
    631 		}
    632 		for(int i=0; i < m; ++i) {
    633 			if(bi[i]) bs++;
    634 		}
    635 		if(as == 0 || bs == 0) cout << "NO" << endl;
    636 		else {
    637 			cout << "YES" << endl;
    638 			cout << as << " " << bs << endl;
    639 			for(int i=0; i < n; ++i) {
    640 				if(ai[i]) {
    641 					print_ll(a[i]);
    642 					cout << " ";
    643 				}
    644 			}
    645 			cout << endl;
    646 			for(int i=0; i < m; ++i) {
    647 				if(bi[i]) {
    648 					print_ll(b[i]);
    649 					cout << " ";
    650 				}
    651 			}
    652 			cout << endl;
    653 			
    654  
    655 		}
    656 	}
    657 }
    658 ```
    659 
    660 [1656I - Neighbour Ordering](/contest/1656/problem/I)
    661 
    662 Author: [FelixMP](/profile/FelixMP "Master FelixMP") Preparator: [FelixMP](/profile/FelixMP "Master FelixMP")
    663 
    664 **Solution**
    665 
    666 Tutorial is loading...
    667 
    668 **Code**
    669 
    670 ```
    671 #include<bits/stdc++.h>
    672 
    673 using namespace std;
    674 
    675 typedef vector<int> vi;
    676 typedef vector<vi> vvi;
    677 typedef pair<int, int> ii;
    678 typedef vector<ii> vii;
    679 typedef vector<vii> vvii;
    680 
    681 struct graph {
    682 	int n;
    683 	int m;
    684 
    685 	vvi al;
    686 	vi morphism;
    687 
    688 	vvi dfs_children;
    689 	vi dfs_parent;
    690 	vi dfs_num;
    691 	vi dfs_low;
    692 	int dfs_count;
    693 
    694 	bool is_root_ac = false;
    695 
    696 	bool bad_biccon = false;
    697 	vii repr_edge;
    698 
    699 	void dt_dfs(int v, int par) {
    700 		dfs_parent[v] = par;
    701 		dfs_num[v] = dfs_low[v] = dfs_count++;
    702 		for(int u : al[v]) {
    703 			if(u == par) {
    704 				//Nothing
    705 			}
    706 			else if(dfs_num[u] == -1) {
    707 				dfs_children[v].push_back(u);
    708 				dt_dfs(u, v);
    709 				dfs_low[v] = min(dfs_low[v], dfs_low[u]);
    710 			}
    711 			else {
    712 				dfs_low[v] = min(dfs_low[v], dfs_num[u]);
    713 			}
    714 		}
    715 	}
    716 
    717 	ii min_repr_edge(ii a, ii b) {
    718 		if(a.first == -1) return b;
    719 		if(b.first == -1) return a;
    720 		if(dfs_num[a.second] < dfs_num[b.second]) return a;
    721 		if(dfs_num[a.second] > dfs_num[b.second]) return b;
    722 		if(dfs_num[a.first] > dfs_num[b.first]) return a;
    723 		if(dfs_num[a.first] < dfs_num[b.first]) return b;
    724 		return a;
    725 	}
    726 
    727 	void dt_dfs_hamil(int v) {
    728 		repr_edge[v] = ii(-1, -1);
    729 
    730 		for(int u : dfs_children[v]) {
    731 			dt_dfs_hamil(u);
    732 			repr_edge[v] = min_repr_edge(repr_edge[v], repr_edge[u]);
    733 		}
    734 
    735 		for(int u : al[v]) {
    736 			if(u == dfs_parent[v]) {
    737 				//Nothing
    738 			}
    739 			else if(dfs_num[u] < dfs_num[v]) {
    740 				repr_edge[v] = min_repr_edge(repr_edge[v], ii(v, u));
    741 			}
    742 
    743 		}
    744 
    745 		if(dfs_parent[v] == -1) {
    746 			//Root case
    747 			
    748 			//Nothing more to check, repr_edge will always be set correctly.
    749 		}
    750 		else {
    751 			if(dfs_children[v].size() == 0) {
    752 				//Nothing to check
    753 			}
    754 			else if(dfs_children[v].size() == 1) {
    755 				//Lemma 4
    756 				if(dfs_low[dfs_children[v][0]] != dfs_low[v] && dfs_low[dfs_children[v][0]] != dfs_num[dfs_parent[v]]) {
    757 					bad_biccon = true;
    758 				}
    759 			}
    760 			else if(dfs_children[v].size() == 2) {
    761 				//Lemma 3
    762 				if(dfs_parent[dfs_parent[v]] != -1) {
    763 					if(!((dfs_low[dfs_children[v][0]] == dfs_num[dfs_parent[v]]) ^ (dfs_low[dfs_children[v][1]] == dfs_num[dfs_parent[v]]))) {
    764 						bad_biccon = true;
    765 					}
    766 				}
    767 				if(dfs_low[v] < min(dfs_low[dfs_children[v][0]], dfs_low[dfs_children[v][1]])) {
    768 					bad_biccon = true;
    769 				}
    770 			}
    771 			else {
    772 				bad_biccon = true;
    773 			}
    774 		}
    775 	}
    776 
    777 	void dt_dfs_cedges(vvii& cedges, vii& edge_stack, int v, int par) {
    778 		dfs_parent[v] = par;
    779 		dfs_num[v] = dfs_low[v] = dfs_count++;
    780 		for(int u : al[v]) {
    781 			if(u == par) {
    782 				//Nothing
    783 			}
    784 			else if(dfs_num[u] == -1) {
    785 				dfs_children[v].push_back(u);
    786 				edge_stack.emplace_back(v, u);
    787 				dt_dfs_cedges(cedges, edge_stack, u, v);
    788 				dfs_low[v] = min(dfs_low[v], dfs_low[u]);
    789 
    790 				if((par == -1 && is_root_ac) || (par != -1 && dfs_low[u] >= dfs_num[v])) {
    791 					vii comp;
    792 					while(edge_stack.back().first != v || edge_stack.back().second != u) {
    793 						comp.push_back(edge_stack.back());
    794 						edge_stack.pop_back();
    795 					}
    796 					comp.push_back(edge_stack.back());
    797 					edge_stack.pop_back();
    798 					cedges.push_back(comp);
    799 				}
    800 			}
    801 			else {
    802 				dfs_low[v] = min(dfs_low[v], dfs_num[u]);
    803 				if(dfs_num[u] < dfs_num[v]) {
    804 					edge_stack.emplace_back(v, u);
    805 				}
    806 			}
    807 		}
    808 	}
    809 
    810 	void generate_dfs_tree(int root) {
    811 		dfs_children = vvi(n, vi());
    812 		dfs_parent = vi(n);
    813 		dfs_count = 0;
    814 		dfs_num = vi(n, -1);
    815 		dfs_low = vi(n, -1);
    816 		dt_dfs(root, -1);
    817 	}
    818 
    819 	void generate_edge_partition(vvii& cedges, vii& edge_stack, int root) {
    820 		generate_dfs_tree(root);
    821 		is_root_ac = (dfs_children[root].size() > 1);
    822 
    823 		dfs_children = vvi(n, vi());
    824 		dfs_parent = vi(n);
    825 		dfs_count = 0;
    826 		dfs_num = vi(n, -1);
    827 		dfs_low = vi(n, -1);
    828 		dt_dfs_cedges(cedges, edge_stack, root, -1);
    829 		if(!edge_stack.empty()) cedges.push_back(edge_stack);
    830 	}
    831 
    832 	void generate_hamil_dfs_tree(int root) {
    833 		generate_dfs_tree(root);
    834 		repr_edge = vii(n, ii());
    835 		dt_dfs_hamil(root);
    836 	}
    837 };
    838 
    839 vector<graph> partition_biconnected(graph& g) {
    840 	vvii cedges;
    841 	vii edge_stack;
    842 	g.generate_edge_partition(cedges, edge_stack, 0);
    843 	vector<graph> comp;
    844 	for(vii& vec : cedges) {
    845 		graph h;
    846 		h.n = 0;
    847 		h.m = vec.size();
    848 		unordered_map<int, int> rmorph;
    849 		for(ii e : vec) {
    850 			if(rmorph.find(e.first) == rmorph.end()) {
    851 				rmorph[e.first] = h.n++;
    852 			}
    853 			if(rmorph.find(e.second) == rmorph.end()) {
    854 				rmorph[e.second] = h.n++;
    855 			}
    856 		}
    857 		h.morphism = vi(h.n);
    858 		h.al = vvi(h.n);
    859 		for(ii e : vec) {
    860 			int u = rmorph[e.first];
    861 			int v = rmorph[e.second];
    862 			h.morphism[u] = g.morphism[e.first];
    863 			h.morphism[v] = g.morphism[e.second];
    864 			h.al[u].push_back(v);
    865 			h.al[v].push_back(u);
    866 		}
    867 		comp.push_back(h);
    868 	}
    869 	return comp;
    870 }
    871 
    872 void upwards_path(graph& g, vi& hc, int v, int tar);
    873 
    874 void downwards_path(graph& g, vi& hc, int v, int tar);
    875 
    876 void upwards_path(graph& g, vi& hc, int v, int tar) {
    877 	if(g.dfs_children[v].size() == 2) {
    878 		int u1 = g.dfs_children[v][0];
    879 		int u2 = g.dfs_children[v][1];
    880 		if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
    881 		hc.push_back(v);
    882 		downwards_path(g, hc, u1, g.repr_edge[u1].first);
    883 		if(v != tar) { 
    884 			upwards_path(g, hc, g.dfs_parent[v], tar);
    885 		}
    886 	}
    887 	else if(g.dfs_children[v].size() == 1) {
    888 		int u = g.dfs_children[v][0];
    889 		hc.push_back(v);
    890 		if(g.repr_edge[u] != g.repr_edge[v]) {
    891 			downwards_path(g, hc, u, g.repr_edge[u].first);
    892 		}
    893 		if(v != tar) {
    894 			upwards_path(g, hc, g.dfs_parent[v], tar);
    895 		}
    896 	}
    897 	else {
    898 		hc.push_back(v);
    899 		if(v != tar) {
    900 			upwards_path(g, hc, g.dfs_parent[v], tar);
    901 		}
    902 	}
    903 }
    904 
    905 void downwards_path(graph& g, vi& hc, int v, int tar) {
    906 	if(g.dfs_children[v].size() == 2) {
    907 		int u1 = g.dfs_children[v][0];
    908 		int u2 = g.dfs_children[v][1];
    909 		if(g.repr_edge[u1] == g.repr_edge[v]) swap(u1, u2);
    910 		upwards_path(g, hc, g.repr_edge[u1].first, u1);
    911 		hc.push_back(v);
    912 		downwards_path(g, hc, u2, tar);
    913 	}
    914 	else if(g.dfs_children[v].size() == 1) {
    915 		int u = g.dfs_children[v][0];
    916 		if(v == tar) {
    917 			upwards_path(g, hc, g.repr_edge[u].first, u);
    918 			hc.push_back(v);
    919 		}
    920 		else {
    921 			hc.push_back(v);
    922 			downwards_path(g, hc, u, tar);
    923 		}
    924 	}
    925 	else {
    926 		hc.push_back(v);
    927 	}
    928 }
    929 
    930 vi hamiltonian_cycle(graph& g) {
    931 	g.generate_hamil_dfs_tree(0);
    932 	if(g.bad_biccon) return vi();
    933 	vi hc;
    934 	downwards_path(g, hc, 0, g.repr_edge[0].first);
    935 	assert((int)hc.size() == g.n);
    936 	return hc;
    937 }
    938 
    939 int comp_index;
    940 bool cyclic_comparator(int a, int b) {
    941 	if(a < comp_index) a += 1e7;
    942 	if(b < comp_index) b += 1e7;
    943 	return a < b;
    944 }
    945 
    946 graph sort_graph(const graph& g, const vi& hc) {
    947 	graph h;
    948 	h.n = g.n;
    949 	h.m = g.m;
    950 	h.morphism = vi(g.n);
    951 	h.al = vvi(g.n);
    952 	vi rhc(g.n);
    953 	for(int i=0; i < g.n; ++i) {
    954 		h.morphism[i] = g.morphism[hc[i]];
    955 		rhc[hc[i]] = i;
    956 	}
    957 	for(int i=0; i < g.n; ++i) {
    958 		for(int j : g.al[hc[i]]) {
    959 			h.al[i].push_back(rhc[j]);
    960 		}
    961 		comp_index = i;
    962 		//This is m log m, can be improved
    963 		sort(h.al[i].begin(), h.al[i].end(), cyclic_comparator);
    964 	}
    965 	return h;
    966 }
    967 
    968 bool has_crossing(const graph& g) {
    969 	vii bad_stack;
    970 	for(int i=0; i < g.n; ++i) {
    971 		comp_index = i;
    972 		while(!bad_stack.empty() && i == bad_stack.back().first) bad_stack.pop_back();
    973 		for(int j=(int)g.al[i].size()-2; j > 0; --j) {
    974 			int u = g.al[i][j];
    975 			if(!bad_stack.empty() && cyclic_comparator(bad_stack.back().first, u) && cyclic_comparator(u, bad_stack.back().second)) {
    976 				return true;
    977 			}
    978 			if(u > i && (bad_stack.empty() || u != bad_stack.back().first)) {
    979 				bad_stack.emplace_back(u, i);
    980 			}
    981 		}
    982 	}
    983 	return false;
    984 }
    985 
    986 void merge_ans(const graph& g, vvi& ans) {
    987 	for(int i=0; i < g.n; ++i) {
    988 		for(int j : g.al[i]) {
    989 			ans[g.morphism[i]].push_back(g.morphism[j]);
    990 		}
    991 	}
    992 }
    993 
    994 void merge_single_edge_ans(const graph& g, vvi& ans) {
    995 	int u = g.morphism[0];
    996 	int v = g.morphism[1];
    997 	ans[u].push_back(v);
    998 	ans[v].push_back(u);
    999 }
   1000 
   1001 vvi solve(graph& input_graph) {
   1002 	vvi ans(input_graph.n);
   1003 	vector<graph> components = partition_biconnected(input_graph);
   1004 	for(graph g : components) {
   1005 		if(g.n == 1) {
   1006 			//Nothing
   1007 		}
   1008 		else if(g.n == 2) {
   1009 			merge_single_edge_ans(g, ans);
   1010 		}
   1011 		else {
   1012 			vi hc = hamiltonian_cycle(g);
   1013 			if(hc.empty()) {
   1014 				return vvi();
   1015 			}
   1016 			graph g2 = sort_graph(g, hc);
   1017 			if(has_crossing(g2))  return vvi();
   1018 			merge_ans(g2, ans);
   1019 		}
   1020 	}	
   1021 	return ans;
   1022 }
   1023 
   1024 graph read_graph() {
   1025 	graph g;
   1026 	int n, m;
   1027 	cin >> n >> m;
   1028 	g.n = n;
   1029 	g.m = m;
   1030 	g.al = vvi(n, vi());
   1031 	g.morphism = vi(n, 0);
   1032 	for(int i=0; i < n; ++i) {
   1033 		g.morphism[i] = i;
   1034 	}
   1035 	for(int i=0; i < m; ++i) {
   1036 		int u, v;
   1037 		cin >> u >> v;
   1038 		g.al[u].push_back(v);
   1039 		g.al[v].push_back(u);
   1040 	}
   1041 	return g;
   1042 }
   1043 
   1044 void print_ans(const vvi& ans) {
   1045 	int n = ans.size();
   1046 	if(n == 0) {
   1047 		cout << "NO" << endl;
   1048 	}
   1049 	else {
   1050 		cout << "YES" << endl;
   1051 		for(int i=0; i < n; ++i) {
   1052 			for(int x : ans[i]) {
   1053 				cout << x << " ";
   1054 			}
   1055 			cout << endl;
   1056 		}
   1057 	}
   1058 }
   1059 
   1060 int main() {
   1061 	int T;
   1062 	cin >> T;
   1063 	while(T--) {
   1064 		graph input_graph = read_graph();
   1065 		vvi ans = solve(input_graph);
   1066 		print_ans(ans);
   1067 	}
   1068 }
   1069 ```