fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. const int N = 1e5 + 5, mod = 998244353;
  6. set<set<int>> edges;
  7. int par[N];
  8. vector<int> adj[N];
  9.  
  10. struct DSU {
  11. vector<int> par, sz;
  12.  
  13. DSU() {
  14. sz.assign(N, 1);
  15. par.resize(N);
  16. iota(par.begin(), par.end(), 0);
  17. }
  18.  
  19. int F(int x) { return par[x] == x ? x : (par[x] = F(par[x])); }
  20.  
  21. void mrg(int u, int v) {
  22. u = F(u), v = F(v);
  23. sz[v] += sz[u];
  24. par[u] = v;
  25. }
  26.  
  27. bool check(int u, int v) {
  28. int f = sz[F(u)], s = sz[F(v)];
  29. return f > s;
  30. }
  31. } dsu;
  32.  
  33. void mrg(int u, int v) {
  34. if (!par[u]) {
  35. par[u] = v;
  36. } else if (!par[v]) {
  37. par[v] = u;
  38. } else {
  39. if (dsu.check(u, v)) swap(u, v);
  40. queue<pair<int, int>> q;
  41. q.push({u, u});
  42. par[u] = v;
  43. while (q.size()) {
  44. auto [nd, p] = q.front();
  45. q.pop();
  46. for (int &x: adj[nd]) {
  47. if (x == p)continue;
  48. par[x] = nd;
  49. q.push({x, nd});
  50. }
  51. }
  52. }
  53. dsu.mrg(u, v);
  54. adj[u].emplace_back(v);
  55. adj[v].emplace_back(u);
  56. edges.insert({u, v});
  57. }
  58.  
  59. int32_t main() {
  60. ios_base::sync_with_stdio(false);
  61. cin.tie(nullptr);
  62. iota(par, par + N, 0);
  63. int n, q;
  64. cin >> n >> q;
  65. int l = 1;
  66. for (int i = 0; i < q; ++i) {
  67. int a, b, c;
  68. cin >> a >> b >> c;
  69. int t = 1 + (a * l % mod % 2);
  70. int u = 1 + (b * l % mod % n);
  71. int v = 1 + (c * l % mod % n);
  72. if (t == 1) {
  73. mrg(u, v);
  74. } else {
  75. int pu = par[u], pv = par[v];
  76. int ans = 0;
  77. if (pu == pv && pv) {
  78. ans = pu;
  79. } else if (pu && edges.count({pu, v})) {
  80. ans = pu;
  81. } else if (pv && edges.count({pv, u})) {
  82. ans = pv;
  83. }
  84. cout << ans << '\n';
  85. l = ans + 1;
  86. }
  87.  
  88. }
  89. }
Runtime error #stdin #stdout 0.04s 7984KB
stdin
Standard input is empty
stdout
Standard output is empty