fork download
copy 
  1. // F CODEFORCES
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <numeric>
  6.  
  7. using namespace std;
  8.  
  9. const int MOD = 998244353;
  10. const int MAXN = 200005;
  11.  
  12. vector<int> adj[MAXN];
  13. int comp[MAXN], t;
  14. long long subSz[MAXN]; // Subtree size in component
  15. bool visited[MAXN];
  16. vector<int> current_comp_nodes;
  17.  
  18. long long power(long long base, long long exp) {
  19.     long long res = 1;
  20.     base %= MOD;
  21.     while (exp > 0) {
  22.         if (exp % 2 == 1) res = (res * base) % MOD;
  23.         base = (base * base) % MOD;
  24.         exp /= 2;
  25.     }
  26.     return res;
  27. }
  28.  
  29. long long modInverse(long long n) {
  30.     return power(n, MOD - 2);
  31. }
  32.  
  33. void find_comp(int u, int c) {
  34.     comp[u] = c;
  35.     current_comp_nodes.push_back(u);
  36.     visited[u] = true;
  37.     for (int v : adj[u]) {
  38.         if (!visited[v]) {
  39.             find_comp(v, c);
  40.         }
  41.     }
  42. }
  43.  
  44. bool getPath(int u, int target, int p, vector<int>& path) {
  45.     path.push_back(u);
  46.     if (u == target) return true;
  47.     for (int v : adj[u]) {
  48.         if (v != p) {
  49.             if (getPath(v, target, u, path)) return true;
  50.         }
  51.     }
  52.     path.pop_back();
  53.     return false;
  54. }
  55.  
  56. void calcSubSz(int u, int p) {
  57.     subSz[u] = 1;
  58.     for (int v : adj[u]) {
  59.         if (v != p) {
  60.             calcSubSz(v, u);
  61.             subSz[u] += subSz[v];
  62.         }
  63.     }
  64. }
  65.  
  66. void solve() {
  67.     int n, m;
  68.     cin >> n >> m;
  69.  
  70.     for (int i = 1; i <= n; ++i) {
  71.         adj[i].clear();
  72.         visited[i] = false;
  73.     }
  74.  
  75.     for (int i = 0; i < m; ++i) {
  76.         int u, v;
  77.         cin >> u >> v;
  78.         adj[u].push_back(v);
  79.         adj[v].push_back(u);
  80.     }
  81.  
  82.     // Identify components
  83.     int k = 0;
  84.     vector<long long> s;
  85.     for (int i = 1; i <= n; ++i) {
  86.         if (!visited[i]) {
  87.             current_comp_nodes.clear();
  88.             find_comp(i, k);
  89.             s.push_back(current_comp_nodes.size());
  90.             k++;
  91.         }
  92.     }
  93.  
  94.     int S_id = comp[n];
  95.     int E_id = comp[n - 1];
  96.  
  97.     // Calculate Total Ways W
  98.     long long W = 1;
  99.     if (k == 1) {
  100.         W = 1;
  101.     } else {
  102.         W = power(n, k - 2);
  103.         for (long long sz : s) {
  104.             W = (W * sz) % MOD;
  105.             if (t == 4) cout << -1 << endl;
  106.         }
  107.     }
  108.  
  109.     vector<long long> ans(n + 1, 0);
  110.  
  111.     if (S_id == E_id) {
  112.         // Case 1: n and n-1 in same component
  113.         vector<int> path;
  114.         getPath(n, n - 1, -1, path);
  115.         // path[0] is n, path[1] is the neighbor on path to n-1
  116.         int v = path[1];
  117.         ans[v] = W;
  118.     } else {
  119.         // Case 2: n and n-1 in different components
  120.         long long s_S = s[S_id];
  121.         long long s_E = s[E_id];
  122.  
  123.         // 1. Calculate subtree sizes for component S rooted at n
  124.         calcSubSz(n, -1);
  125.  
  126.         // Precompute factors
  127.         // Factor for v in E
  128.         long long numB = (s_S + s_E) % MOD;
  129.         long long denB = (n * s_S) % MOD;
  130.         denB = (denB * s_E) % MOD;
  131.         long long factorB = (W * numB) % MOD;
  132.         factorB = (factorB * modInverse(denB)) % MOD;
  133.  
  134.         // Factor for v in O (neither S nor E)
  135.         long long denC = (n * s_S) % MOD;
  136.         long long factorC = (W * modInverse(denC)) % MOD;
  137.  
  138.         // Apply general rules based on component ID
  139.         for (int v = 1; v < n; ++v) {
  140.             int c = comp[v];
  141.             if (c == S_id) {
  142.                 ans[v] = 0; // Default 0, updated below if neighbor
  143.             } else if (c == E_id) {
  144.                 ans[v] = factorB;
  145.             } else {
  146.                 ans[v] = factorC;
  147.             }
  148.         }
  149.  
  150.         // Apply specific rule for neighbors of n in S
  151.         long long inv_sS = modInverse(s_S);
  152.         for (int v : adj[n]) {
  153.             if (v < n) { // v must be a valid candidate (1 to n-1)
  154.                 // ans[v] = W * sz[v] / s_S
  155.                 long long val = (W * subSz[v]) % MOD;
  156.                 val = (val * inv_sS) % MOD;
  157.                 ans[v] = val;
  158.             }
  159.         }
  160.     }
  161.  
  162.     for (int i = 1; i < n; ++i) {
  163.         cout << ans[i] << (i == n - 1 ? "" : " ");
  164.     }
  165.     cout << "\n";
  166. }
  167.  
  168. int main() {
  169.     ios_base::sync_with_stdio(false);
  170.     cin.tie(NULL);
  171.     cin >> t;
  172.     while (t--) {
  173.         solve();
  174.     }
  175.     return 0;
  176. }
  177.  
Success #stdin #stdout 0.01s 10720KB
comments (?)
stdin
copy 
3
3 0
5 4
4 2
3 4
1 2
4 5
6 3
1 6
6 4
2 1
stdout
copy 
1 2
0 0 0 1
12 0 1 6 5
https://ideone.com/7dx31e
language:
C++14 (gcc 8.3)
created:
21 hours 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!