fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <sstream>
  4.  
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8. void Henry() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.     cout.tie(nullptr);
  12. }
  13.  
  14.  
  15. void filIO() {
  16. #ifndef ONLINE_JUDGE
  17.     freopen("input.txt", "r", stdin);
  18.     freopen("output.txt", "w", stdout);
  19. #endif
  20. }
  21.  
  22.  
  23. int cnt = 0;
  24.  
  25. void DFS(int i, int p, vector<vector<int>> &adj, vector<int>&vis, vector<vector<int>> &ans) {
  26.     vis[i] = 1;
  27.     if (p) {
  28.         if (cnt) {
  29.             ans[i][p] = 2;
  30.             ans[p][i] = 2;
  31.         }
  32.         else {
  33.             ans[i][p] = 3;
  34.             ans[p][i] = 3;
  35.         }
  36.         cnt = ~cnt;
  37.     }
  38.     for (auto j : adj[i]) {
  39.         if (!vis[j]) {
  40.             DFS(j, i, adj, vis, ans);
  41.         }
  42.     }
  43. }
  44.  
  45.  
  46. void solve() {
  47.     int n;cin >> n;
  48.     vector<vector<int>> adj;
  49.     vector<int>vis;
  50.     vector<vector<int>> ans;
  51.     adj.resize(n + 1, {});
  52.     vis.resize(n + 1, 0);
  53.     ans.resize(n + 1, vector<int>(n + 1, 0));
  54.     vector<pair<int, int>> edges;
  55.     for (int i = 1; i < n; i++) {
  56.         int u, v; cin >> u >> v;
  57.         adj[u].push_back(v);
  58.         adj[v].push_back(u);
  59.         edges.push_back({u, v});
  60.     }
  61.     int st = 0;
  62.     for (int i = 1; i <= n; i++) {
  63.         if (adj[i].size() > 2) {
  64.             cout << "-1\n";
  65.             return;
  66.         }
  67.         if (adj[i].size() == 1) {
  68.             st = i;
  69.         }
  70.     }
  71.     cnt = 0;
  72.     DFS(st, 0, adj, vis, ans);
  73.     for (auto edge : edges) {
  74.         cout << ans[edge.first][edge.second] << ' ';
  75.     }
  76.     cout << '\n';
  77. }
  78.  
  79. signed main() {
  80.     Henry();
  81.     filIO();
  82.     int q = 1;
  83.     cin >> q;
  84.     while (q--) {
  85.         solve();
  86.     }
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/oXxEMI
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
11 days ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!