QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#217613#7177. Many Many CyclesLainWA 174ms4424kbC++202.8kb2023-10-17 02:37:332023-10-17 02:37:34

Judging History

你现在查看的是最新测评结果

  • [2023-10-17 02:37:34]
  • 评测
  • 测评结果:WA
  • 用时:174ms
  • 内存:4424kb
  • [2023-10-17 02:37:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<class T>
struct RMQ {
	vector<vector<T>> jmp;
	RMQ(const vector<T>& V) : jmp(1, V) {
		for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
			jmp.emplace_back(sz(V) - pw * 2 + 1);
			rep(j,0,sz(jmp[k]))
				jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
		}
	}
	T query(int a, int b) {
		assert(a < b); // or return inf if a == b
		int dep = 31 - __builtin_clz(b - a);
		return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  struct edge {
    int u, v, w, is_span;
    int to(int x) {
      return u^v^x;
    }
  };

  int n, m;
  cin >> n >> m;
  vector<edge> edges;
  edges.reserve(m);
  vector<vi> g(n);
  rep(i, 0, m) {
    int u, v, w;
    cin >> u >> v >> w;
    u--,v--;
    g[u].push_back(sz(edges));
    g[v].push_back(sz(edges));
    edges.push_back({u,v,w,0});
  }


  int comp_num = 0, T = 0;
  vi vis(n), comp(n), dep(n), time(n), path, ret;
  vector<ll> dist(n);
  auto dfs = [&](auto& self, int s)->void {
    time[s] = T++;
    vis[s] = 1;
    comp[s] = comp_num;
    for (auto& e : g[s]) {
      int u = edges[e].to(s);
      if (vis[u]) continue;
      path.push_back(s);
      ret.push_back(time[s]);
      edges[e].is_span = 1;
      dist[u] = dist[s] + edges[e].w;
      dep[u] = dep[s]+1;
      self(self, u);
    }
  };
  rep(i, 0, n)  {
    if (!vis[i]) {
      dfs(dfs, i);
      comp_num++;
    }
  }

  RMQ rmq(ret);
  auto lca = [&](int x, int y)->int {
    assert(comp[x] == comp[y]);
    if (x == y) return x;
    tie(x, y) = minmax(time[x], time[y]);
    return path[rmq.query(x, y)];
  };

  vi not_span;
  rep(i, 0, m) if (!edges[i].is_span) not_span.push_back(i);

  ll ans = 0;
  rep(_i, 0, sz(not_span)) {
    int i = not_span[_i];
    auto& [u,v, w, _] = edges[i];

    if (dep[u] > dep[v]) swap(u, v); // u above v
    
    // Simple cycle
    ans = __gcd(ans, dist[v] - dist[u] + w);

    // xored
    rep(_j, _i+1, sz(not_span)) {
      int j = not_span[_j];
      auto& [a, b, w1, _] = edges[j];
      if (comp[a] != comp[u]) continue; // not in the same component, ignore
      if (dep[a] > dep[b]) swap(a, b); // a above b
      if (dep[b] <= dep[u]) continue; // no intersection, b above u
      int upper = dep[a] < dep[u] ? a : u;
      int lower = dep[a] > dep[u] ? a : u;
      if (lca(upper, lower) != upper) continue; // no shared edges
      int l = lca(v, b);
      if (dep[l] <= dep[lower]) continue;
      ans = __gcd(ans, 2*(dist[l] - dist[lower]));
    }
  }
  cout << ans << '\n';
}


詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3492kb

input:

4 4
1 2 1
2 3 1
3 4 1
4 1 1

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1

output:

4

result:

ok answer is '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

20 50
1 2 8
1 3 1
3 4 5
3 5 9
3 6 5
6 7 6
7 8 8
2 9 2
8 10 3
8 11 7
8 12 5
3 13 4
7 14 3
6 15 7
9 16 6
8 17 7
16 18 9
16 19 3
18 20 10
11 3 2
17 1 1
16 2 2
15 1 1
10 3 2
9 1 2
19 2 1
6 1 2
7 3 1
17 3 2
15 3 2
8 6 2
5 1 2
8 1 2
12 1 1
12 7 1
4 1 2
18 2 1
11 7 1
14 1 1
18 1 1
18 9 1
10 6 1
14 3 2
20 2...

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3448kb

input:

20 50
1 2 18468
1 3 26501
3 4 15725
3 5 29359
3 6 24465
6 7 28146
7 8 16828
2 9 492
8 10 11943
8 11 5437
8 12 14605
3 13 154
7 14 12383
6 15 18717
9 16 19896
8 17 21727
16 18 11539
16 19 19913
18 20 26300
11 3 2
17 1 1
16 2 2
15 1 1
10 3 2
9 1 2
19 2 1
6 1 2
7 3 1
17 3 2
15 3 2
8 6 2
5 1 2
8 1 2
12 ...

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

100 150
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

3

result:

ok answer is '3'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

100 130
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

7

result:

ok answer is '7'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

100 200
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

4

result:

ok answer is '4'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

2

result:

ok answer is '2'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

3

result:

ok answer is '3'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3680kb

input:

1000 1600
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

100 190
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
11...

output:

4

result:

ok answer is '4'

Test #13:

score: 0
Accepted
time: 34ms
memory: 3764kb

input:

1000 3000
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

2

result:

ok answer is '2'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3632kb

input:

1000 1400
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

2

result:

ok answer is '2'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3672kb

input:

1000 1500
1 2 184676335
1 3 191705725
1 4 293606963
1 5 57078146
2 6 168279962
6 7 29961943
5 8 54392392
5 9 39020154
5 10 123837422
7 11 197199896
3 12 217274772
7 13 18709913
6 14 263007036
11 15 287053812
3 16 303347674
9 17 151417712
17 18 68705548
15 19 326652758
12 20 128598724
2 21 275290779
...

output:

8

result:

ok answer is '8'

Test #17:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

12

result:

ok answer is '12'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

13

result:

ok answer is '13'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #21:

score: 0
Accepted
time: 7ms
memory: 3768kb

input:

2000 3000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

3

result:

ok answer is '3'

Test #22:

score: 0
Accepted
time: 7ms
memory: 3804kb

input:

2000 3000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

2000 2500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #24:

score: 0
Accepted
time: 17ms
memory: 3836kb

input:

2000 3500
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #25:

score: 0
Accepted
time: 25ms
memory: 3844kb

input:

2000 4000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

4

result:

ok answer is '4'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

2000 2300
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #27:

score: 0
Accepted
time: 25ms
memory: 3900kb

input:

3000 5000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #28:

score: 0
Accepted
time: 5ms
memory: 3956kb

input:

3000 3700
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

13

result:

ok answer is '13'

Test #29:

score: 0
Accepted
time: 4ms
memory: 3928kb

input:

3000 3700
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #30:

score: 0
Accepted
time: 56ms
memory: 4424kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

3

result:

ok answer is '3'

Test #31:

score: 0
Accepted
time: 56ms
memory: 4420kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #32:

score: 0
Accepted
time: 30ms
memory: 4256kb

input:

5000 7200
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

5

result:

ok answer is '5'

Test #33:

score: 0
Accepted
time: 26ms
memory: 4280kb

input:

5000 7200
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

1

result:

ok answer is '1'

Test #34:

score: 0
Accepted
time: 56ms
memory: 4292kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

6

result:

ok answer is '6'

Test #35:

score: 0
Accepted
time: 51ms
memory: 4252kb

input:

5000 8000
1 2 22794613
1 3 23670271
1 4 36254735
1 5 7068116
2 6 20774480
6 7 3707773
5 8 6740416
5 9 4815222
5 10 15296810
7 11 24351908
3 12 26824656
7 13 2326259
6 14 32470002
11 15 35443314
3 16 37448596
9 17 18691706
17 18 8500660
15 19 40337666
12 20 15876730
2 21 33971565
11 22 3767381
17 23 ...

output:

2

result:

ok answer is '2'

Test #36:

score: 0
Accepted
time: 173ms
memory: 4212kb

input:

5000 10000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 205804...

output:

4

result:

ok answer is '4'

Test #37:

score: 0
Accepted
time: 174ms
memory: 4280kb

input:

5000 10000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 205804...

output:

2

result:

ok answer is '2'

Test #38:

score: 0
Accepted
time: 7ms
memory: 4232kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

7

result:

ok answer is '7'

Test #39:

score: 0
Accepted
time: 8ms
memory: 4236kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #40:

score: 0
Accepted
time: 9ms
memory: 4268kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

2

result:

ok answer is '2'

Test #41:

score: 0
Accepted
time: 2ms
memory: 4288kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

9

result:

ok answer is '9'

Test #42:

score: 0
Accepted
time: 17ms
memory: 4296kb

input:

5000 6666
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

9

result:

ok answer is '9'

Test #43:

score: 0
Accepted
time: 17ms
memory: 4264kb

input:

5000 6666
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #44:

score: 0
Accepted
time: 7ms
memory: 4236kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

12345

result:

ok answer is '12345'

Test #45:

score: 0
Accepted
time: 7ms
memory: 4268kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

997

result:

ok answer is '997'

Test #46:

score: 0
Accepted
time: 7ms
memory: 4232kb

input:

5000 6000
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

1

result:

ok answer is '1'

Test #47:

score: 0
Accepted
time: 2ms
memory: 4192kb

input:

5000 4999
1 2 4216811
1 3 4386257
1 4 6720587
1 5 1328886
2 6 3846518
6 7 694803
5 8 1271800
5 9 889810
5 10 2840518
7 11 4515600
3 12 4968300
7 13 446045
6 14 6013208
11 15 6568096
3 16 6933598
9 17 3459860
17 18 1591452
15 19 7479694
12 20 2940576
2 21 6277391
11 22 714171
17 23 95771
2 24 2058041...

output:

0

result:

ok answer is '0'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3480kb

input:

6 6
1 2 999999999
2 3 999999999
3 4 999999999
4 5 999999999
5 6 999999999
6 1 999999999

output:

5999999994

result:

ok answer is '5999999994'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

6 6
1 2 6
2 3 6
3 1 6
4 5 15
5 6 7
6 4 8

output:

6

result:

ok answer is '6'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

1 0

output:

0

result:

ok answer is '0'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

4 5
1 2 1
3 4 1
2 3 1
1 4 1
1 3 1

output:

1

result:

ok answer is '1'

Test #52:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

6 6
1 2 1
1 3 1
3 4 1
1 4 1
2 3 1
5 1 1

output:

1

result:

ok answer is '1'

Test #53:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

9 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
1 8 1
4 9 1
6 9 1

output:

4

result:

ok answer is '4'

Test #54:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

6 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 6 1
3 6 1

output:

2

result:

ok answer is '2'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

33 36
2 22 1
12 18 1
27 28 1
9 19 1
26 27 1
6 21 1
15 16 1
2 3 1
7 24 1
3 12 1
4 23 1
28 29 1
5 14 1
29 30 1
1 10 1
11 13 1
6 13 1
16 25 1
14 21 1
4 16 1
10 19 1
10 11 1
5 15 1
1 8 1
3 20 1
7 13 1
25 26 1
29 31 1
17 23 1
8 18 1
12 24 1
25 30 1
31 32 1
17 20 1
15 22 1
9 18 1

output:

3

result:

ok answer is '3'

Test #56:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

33 35
10 13 1
6 13 1
9 19 1
5 15 1
29 31 1
2 3 1
4 16 1
3 20 1
7 13 1
31 32 1
12 24 1
2 22 1
17 23 1
26 27 1
17 20 1
16 25 1
3 12 1
28 29 1
1 8 1
12 18 1
27 28 1
14 21 1
10 19 1
25 26 1
5 14 1
15 16 1
9 18 1
4 23 1
25 30 1
1 10 1
8 18 1
7 24 1
29 30 1
6 21 1
15 22 1

output:

1

result:

ok answer is '1'

Test #57:

score: 0
Accepted
time: 1ms
memory: 3876kb

input:

2000 2000
1036 1254 1
1453 1496 1
342 1815 1
186 346 1
840 1555 1
138 1503 1
416 1376 1
660 1253 1
1279 1799 1
209 1554 1
624 1278 1
792 884 1
333 1703 1
393 894 1
551 1192 1
1705 1805 1
302 930 1
115 1384 1
151 1156 1
71 209 1
82 1637 1
858 1854 1
19 1798 1
348 703 1
1692 1744 1
261 1029 1
143 1631...

output:

2000

result:

ok answer is '2000'

Test #58:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

1820 1872
677 1254 1
114 163 1
1751 1815 1
532 1640 1
290 380 1
253 1429 1
174 1163 1
1005 1431 1
521 1324 1
37 1553 1
369 1764 1
658 1170 1
1456 1574 1
224 663 1
752 1460 1
128 441 1
831 1013 1
730 1583 1
500 983 1
374 1274 1
1394 1478 1
422 1223 1
1310 1632 1
1133 1508 1
914 1258 1
151 907 1
221 2...

output:

18

result:

ok answer is '18'

Test #59:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

1521 1584
1138 1283 1
95 542 1
137 1042 1
1043 1390 1
147 1396 1
382 709 1
651 828 1
909 1124 1
286 1485 1
31 171 1
925 1254 1
360 501 1
900 1229 1
69 1358 1
166 199 1
633 1178 1
310 1390 1
679 1482 1
844 1333 1
761 1208 1
38 1512 1
449 875 1
13 1467 1
77 217 1
622 736 1
45 1163 1
365 1346 1
106 108...

output:

12

result:

ok answer is '12'

Test #60:

score: 0
Accepted
time: 1ms
memory: 3644kb

input:

1433 1467
43 1268 1
90 1143 1
237 271 1
444 1375 1
232 1407 1
1026 1139 1
861 943 1
981 1003 1
77 1229 1
416 966 1
606 1370 1
351 438 1
687 1379 1
1030 1186 1
1373 1428 1
715 762 1
553 1426 1
238 1012 1
120 618 1
345 857 1
827 1118 1
548 1085 1
245 333 1
82 910 1
202 570 1
80 781 1
666 797 1
122 102...

output:

9

result:

ok answer is '9'

Test #61:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

1569 1625
1043 1553 1
57 369 1
481 1231 1
99 227 1
113 262 1
239 354 1
175 887 1
819 1230 1
27 115 1
76 820 1
1086 1498 1
482 1193 1
1299 1447 1
570 604 1
121 508 1
100 208 1
77 572 1
52 1296 1
198 639 1
103 945 1
256 381 1
745 1173 1
1033 1350 1
13 1414 1
233 1399 1
402 1417 1
1394 1441 1
206 623 1...

output:

5

result:

ok answer is '5'

Test #62:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

1035 1072
448 654 1
201 211 1
139 650 1
224 255 1
430 883 1
494 517 1
199 999 1
717 763 1
661 813 1
145 574 1
68 908 1
626 990 1
7 805 1
54 875 1
600 968 1
279 462 1
335 543 1
266 665 1
598 676 1
177 447 1
790 1034 1
273 909 1
475 814 1
464 973 1
210 560 1
290 905 1
650 708 1
288 994 1
10 183 1
261 ...

output:

8

result:

ok answer is '8'

Test #63:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

162 198
41 83 1
15 121 1
29 76 1
62 75 1
78 114 1
58 80 1
5 75 1
85 119 1
45 137 1
3 56 1
149 156 1
46 63 1
79 107 1
125 150 1
33 78 1
43 149 1
27 87 1
20 33 1
13 136 1
60 90 1
60 110 1
30 97 1
102 152 1
25 31 1
6 79 1
24 67 1
16 78 1
68 115 1
77 78 1
103 124 1
117 161 1
117 139 1
55 67 1
19 146 1
4...

output:

3

result:

ok answer is '3'

Test #64:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

1894 1932
384 1664 1
1204 1508 1
733 1583 1
818 1515 1
879 1799 1
197 1165 1
657 919 1
559 1893 1
241 1104 1
347 1283 1
516 916 1
179 1041 1
305 477 1
1116 1135 1
1254 1561 1
280 742 1
269 975 1
34 862 1
1033 1659 1
74 382 1
307 1600 1
99 1553 1
1298 1565 1
955 1579 1
308 478 1
947 1595 1
1686 1793 ...

output:

7

result:

ok answer is '7'

Test #65:

score: 0
Accepted
time: 30ms
memory: 3548kb

input:

63 1953
24 25 1
30 53 1
16 28 1
20 36 1
34 51 1
33 52 1
3 11 1
9 35 1
28 52 1
52 54 1
22 51 1
33 46 1
2 45 1
35 43 1
4 48 1
4 35 1
2 7 1
26 59 1
21 35 1
21 43 1
9 58 1
37 63 1
7 26 1
17 32 1
7 11 1
34 56 1
6 54 1
18 62 1
33 44 1
15 52 1
50 53 1
17 46 1
12 42 1
9 31 1
9 11 1
35 47 1
1 13 1
21 42 1
26...

output:

1

result:

ok answer is '1'

Test #66:

score: 0
Accepted
time: 28ms
memory: 3640kb

input:

89 1939
29 62 1
14 25 1
5 60 1
24 26 1
1 8 1
3 68 1
47 85 1
41 81 1
47 55 1
22 75 1
20 37 1
42 87 1
46 53 1
48 55 1
54 72 1
61 66 1
7 43 1
70 74 1
63 89 1
29 51 1
21 56 1
18 49 1
20 31 1
14 34 1
22 85 1
75 86 1
52 68 1
12 32 1
44 55 1
41 42 1
37 82 1
36 82 1
5 67 1
52 74 1
5 18 1
35 40 1
14 60 1
11 ...

output:

1

result:

ok answer is '1'

Test #67:

score: 0
Accepted
time: 20ms
memory: 3560kb

input:

409 1944
69 134 1
162 172 1
50 327 1
3 17 1
152 256 1
19 302 1
246 371 1
289 394 1
228 376 1
210 270 1
318 336 1
352 405 1
171 324 1
21 398 1
70 236 1
68 349 1
316 344 1
84 386 1
223 344 1
125 223 1
293 327 1
88 253 1
39 165 1
151 395 1
201 322 1
68 403 1
336 383 1
215 256 1
73 138 1
5 399 1
260 268...

output:

1

result:

ok answer is '1'

Test #68:

score: 0
Accepted
time: 15ms
memory: 3700kb

input:

509 1828
245 248 1
384 386 1
127 261 1
260 480 1
437 466 1
127 382 1
158 476 1
482 498 1
241 375 1
159 216 1
232 408 1
74 270 1
32 293 1
126 249 1
59 445 1
146 291 1
129 234 1
81 164 1
243 437 1
258 262 1
229 320 1
126 185 1
118 423 1
221 488 1
185 204 1
220 227 1
96 472 1
112 149 1
106 432 1
46 100...

output:

2

result:

ok answer is '2'

Test #69:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

2000 1999
1552 1932 1
553 1152 1
1006 1967 1
606 1381 1
1549 1775 1
1283 1992 1
994 1000 1
367 1864 1
1047 1989 1
475 1284 1
1033 1688 1
827 1786 1
746 1018 1
651 756 1
73 1178 1
307 539 1
114 1924 1
653 667 1
693 1087 1
222 1656 1
241 1841 1
165 1725 1
433 476 1
66 1099 1
169 1490 1
609 1257 1
506 ...

output:

1440

result:

ok answer is '1440'

Test #70:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

1302 1302
893 1045 1
149 798 1
202 1034 1
252 789 1
269 920 1
915 989 1
96 496 1
1142 1302 1
647 868 1
54 1127 1
161 704 1
128 1294 1
51 718 1
325 825 1
423 798 1
344 809 1
504 1070 1
548 756 1
276 1116 1
8 41 1
782 1294 1
602 685 1
137 976 1
315 1028 1
75 562 1
36 1208 1
20 302 1
383 1080 1
62 392 ...

output:

42

result:

ok answer is '42'

Test #71:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

1932 1989
390 911 1
1384 1761 1
679 791 1
931 1855 1
315 1346 1
201 331 1
167 1560 1
72 1206 1
255 1838 1
1777 1854 1
693 1869 1
1225 1343 1
588 825 1
904 1120 1
413 773 1
853 1521 1
884 924 1
628 638 1
370 1080 1
1004 1821 1
342 817 1
1315 1448 1
289 352 1
1389 1730 1
921 1602 1
880 1307 1
164 263 ...

output:

17

result:

ok answer is '17'

Test #72:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

561 572
290 330 1
81 158 1
158 166 1
501 548 1
387 482 1
54 121 1
521 535 1
106 397 1
263 466 1
230 520 1
332 400 1
55 374 1
182 209 1
138 219 1
154 506 1
494 510 1
45 346 1
190 421 1
290 383 1
56 361 1
123 157 1
380 538 1
345 525 1
225 318 1
82 356 1
40 340 1
245 451 1
420 520 1
470 556 1
279 347 1...

output:

13

result:

ok answer is '13'

Test #73:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

573 585
96 357 1
358 495 1
136 375 1
200 538 1
1 112 1
170 524 1
125 273 1
189 572 1
525 562 1
24 443 1
152 173 1
224 250 1
470 572 1
76 299 1
289 371 1
161 561 1
269 435 1
114 122 1
225 442 1
65 175 1
207 319 1
73 469 1
6 327 1
144 357 1
389 557 1
256 534 1
398 413 1
87 413 1
519 567 1
312 353 1
40...

output:

1

result:

ok answer is '1'

Test #74:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

230 246
13 198 1
31 100 1
54 181 1
10 211 1
210 218 1
151 178 1
175 228 1
66 164 1
15 81 1
156 214 1
36 200 1
154 228 1
73 84 1
57 210 1
127 144 1
81 167 1
131 154 1
40 143 1
86 157 1
48 58 1
208 230 1
164 230 1
4 132 1
22 159 1
67 138 1
63 78 1
171 184 1
69 121 1
51 209 1
9 38 1
111 167 1
65 75 1
1...

output:

6

result:

ok answer is '6'

Test #75:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

436 468
328 330 1
46 78 1
219 400 1
165 329 1
278 391 1
45 387 1
166 402 1
66 213 1
102 358 1
185 368 1
91 136 1
33 378 1
73 102 1
111 150 1
95 405 1
150 402 1
6 223 1
119 351 1
110 381 1
178 407 1
175 212 1
379 416 1
153 310 1
198 241 1
259 319 1
114 177 1
66 341 1
26 354 1
302 364 1
232 385 1
175 ...

output:

9

result:

ok answer is '9'

Test #76:

score: -100
Wrong Answer
time: 1ms
memory: 3612kb

input:

2000 714
13 198 1
31 100 1
54 181 1
10 211 1
210 218 1
151 178 1
175 228 1
66 164 1
15 81 1
156 214 1
36 200 1
154 228 1
73 84 1
57 210 1
127 144 1
81 167 1
131 154 1
40 143 1
86 157 1
48 58 1
208 230 1
164 230 1
4 132 1
22 159 1
67 138 1
63 78 1
171 184 1
69 121 1
51 209 1
9 38 1
111 167 1
65 75 1
...

output:

1

result:

wrong answer expected '3', found '1'