QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#105973	#2068. Fast as Ryser	Scintilla	AC ✓	1726ms	65984kb	C++14	2.3kb	2023-05-16 09:05:57	2023-05-16 09:06:00

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-16 09:06:00]
评测

测评结果：AC
用时：1726ms
内存：65984kb

查看

[2023-05-16 09:05:57]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int P = 1e9 + 7;
const int i2 = (P + 1) / 2;

const int N = 18;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

#define popc(x) __builtin_popcount(x)
#define minp(x) __lg(x & -x)

int n, m, c, pc[N << 1], lim, f[N << 1][1 << N], g[N << 1][1 << N], h[1 << N], dp[1 << N], ans;
bool e[N << 1][N << 1];

int main() {
  n = read(), m = read(), c = read();
  rep(i, 1, m) {
    int u = read() - 1, v = read() - 1;
    e[u][v] = e[v][u] = true;
  }
  n = (n + 1) >> 1, lim = 1 << n;
  rep(i, 0, (n << 1) - 1) f[i][1 << (i >> 1)] = 1;
  rep(i, 0, n - 1) g[i << 1][1 << i] = 1;
  pc[0] = 1; rep(i, 1, n) pc[i] = mul(pc[i - 1], c);
  rep(s, 1, lim - 1) {
    rep(i, 0, (n << 1) - 1) if ((s >> (i >> 1)) & 1) {
      rep(j, 0, (n << 1) - 1) if (e[i ^ 1][j] && !((s >> (j >> 1) & 1))) {
        f[j][s | (1 << (j >> 1))] = inc(f[j][s | (1 << (j >> 1))], f[i][s]);
      }
      drep(j, (n << 1) - 1, (minp(s) + 1) << 1) if (e[i ^ 1][j] && !((s >> (j >> 1) & 1))) {
        g[j][s | (1 << (j >> 1))] = inc(g[j][s | (1 << (j >> 1))], g[i][s]);
      }
    }
    rep(i, 0, (n << 1) - 1) {
      h[s] = inc(h[s], mul(f[i][s], mul(pc[popc(s) - 1], i2)));
      if (e[i ^ 1][minp(s) << 1]) h[s] = inc(h[s], mul(g[i][s], pc[popc(s)]));
    }
  }
  dp[0] = 1;
  rep(s, 0, (1 << n) - 1) {
    for (int t = s; t; t = s & (t - 1)) {
      if (t & (s & -s)) dp[s] = inc(dp[s], mul(h[t], dp[s ^ t]));
    }
  }
  ans = dp[(1 << n) - 1];
  printf("%d\n", ans);
  return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 9648kb

input:

output:

result:

ok single line: '2171001'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

8 11 818466928
6 7
3 6
6 5
7 3
6 2
8 1
1 7
4 3
5 1
6 1
6 4

output:

425176360

result:

ok single line: '425176360'

Test #3:

score: 0

Accepted

time: 1064ms

memory: 64964kb

input:

36 123 272968155
33 35
17 5
12 1
36 32
1 11
9 28
24 36
13 17
19 17
35 8
7 19
31 24
31 34
27 18
9 17
35 17
6 17
31 12
12 19
25 18
36 16
24 23
26 34
7 23
25 14
18 34
10 23
32 33
12 28
18 14
35 23
19 33
22 27
14 27
14 15
22 6
1 20
31 17
27 31
15 4
35 4
5 33
26 36
27 2
20 23
2 12
36 13
28 13
4 7
21 24
2...

output:

951479337

result:

ok single line: '951479337'

Test #4:

score: 0

Accepted

time: 1679ms

memory: 65540kb

input:

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

output:

139355408

result:

ok single line: '139355408'

Test #5:

score: 0

Accepted

time: 1726ms

memory: 65984kb

input:

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

output:

409886964

result:

ok single line: '409886964'

Test #6:

score: 0

Accepted

time: 1628ms

memory: 65028kb

input:

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

output:

825811598

result:

ok single line: '825811598'

Test #7:

score: 0

Accepted

time: 1375ms

memory: 65060kb

input:

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

output:

466059363

result:

ok single line: '466059363'

Test #8:

score: 0

Accepted

time: 1632ms

memory: 64944kb

input:

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

output:

183842696

result:

ok single line: '183842696'

Test #9:

score: 0

Accepted

time: 1100ms

memory: 64940kb

input:

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

output:

602614473

result:

ok single line: '602614473'

Test #10:

score: 0

Accepted

time: 1691ms

memory: 65420kb

input:

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

output:

534178430

result:

ok single line: '534178430'

Test #11:

score: 0

Accepted

time: 967ms

memory: 58516kb

input:

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

output:

984244248

result:

ok single line: '984244248'

Test #12:

score: 0

Accepted

time: 1574ms

memory: 65472kb

input:

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

output:

334985208

result:

ok single line: '334985208'

Test #13:

score: 0

Accepted

time: 1690ms

memory: 64944kb

input:

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

output:

491766799

result:

ok single line: '491766799'

Test #14:

score: 0

Accepted

time: 1069ms

memory: 62172kb

input:

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

output:

599285973

result:

ok single line: '599285973'

Test #15:

score: 0

Accepted

time: 1686ms

memory: 65528kb

input:

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

output:

195560486

result:

ok single line: '195560486'

Test #16:

score: 0

Accepted

time: 1530ms

memory: 64948kb

input:

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

output:

512893447

result:

ok single line: '512893447'

Test #17:

score: 0

Accepted

time: 1409ms

memory: 65108kb

input:

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

output:

75822342

result:

ok single line: '75822342'

Test #18:

score: 0

Accepted

time: 919ms

memory: 42096kb

input:

36 20 72725288
25 31
34 5
29 15
28 14
4 34
35 12
10 34
18 17
33 6
36 17
24 3
27 24
31 30
19 10
15 26
22 14
34 32
2 28
31 5
1 28

output:

10405385

result:

ok single line: '10405385'

Test #19:

score: 0

Accepted

time: 1723ms

memory: 65448kb

input:

36 375 731733295
36 28
26 30
3 7
16 20
28 2
25 12
20 30
23 6
9 8
24 5
7 29
25 22
25 17
3 22
20 5
13 24
19 9
34 30
31 7
2 34
23 19
23 7
19 34
24 7
26 16
14 34
9 22
30 22
3 8
36 33
36 32
4 15
9 7
13 6
19 13
33 31
17 34
28 25
34 15
4 29
17 35
25 31
13 25
5 28
35 34
36 23
21 20
25 32
21 29
14 12
3 16
9 ...

output:

71633307

result:

ok single line: '71633307'

Test #20:

score: 0

Accepted

time: 1382ms

memory: 65300kb

input:

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

output:

865260163

result:

ok single line: '865260163'

Test #21:

score: 0

Accepted

time: 1002ms

memory: 64256kb

input:

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

output:

750998004

result:

ok single line: '750998004'

Test #22:

score: 0

Accepted

time: 1686ms

memory: 65264kb

input:

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

output:

682561439

result:

ok single line: '682561439'

Test #23:

score: 0

Accepted

time: 844ms

memory: 15952kb

input:

36 0 73190723

output:

result:

ok single line: '1'

Test #24:

score: 0

Accepted

time: 1444ms

memory: 65076kb

input:

36 630 67695848
6 13
35 30
14 31
8 29
30 26
26 1
11 33
13 30
20 7
35 20
18 34
27 30
14 23
1 27
21 27
26 14
13 14
25 4
11 3
17 28
20 33
2 5
31 28
18 10
21 29
31 26
29 28
19 31
17 33
28 33
3 23
28 20
10 8
25 9
8 7
26 5
7 33
17 36
34 13
12 35
6 19
9 19
6 2
15 1
24 4
4 1
36 15
3 17
21 17
18 9
18 27
11 2...

output:

396183330

result:

ok single line: '396183330'

Test #25:

score: 0

Accepted

time: 895ms

memory: 38496kb

input:

36 15 361262017
3 10
30 33
11 3
15 12
12 17
36 20
15 20
23 22
36 35
20 5
17 26
34 27
1 34
27 9
21 5

output:

622932610

result:

ok single line: '622932610'

Test #26:

score: 0

Accepted

time: 1607ms

memory: 64948kb

input:

35 269 282064549
6 4
25 31
30 26
9 14
31 26
14 31
17 24
3 34
1 11
14 34
30 3
27 3
11 3
23 25
32 4
12 8
18 29
33 28
3 21
27 33
30 13
32 18
1 28
31 20
9 8
7 23
13 6
35 6
17 31
14 33
10 16
18 17
34 10
30 4
9 21
12 33
24 20
20 23
26 10
11 30
11 27
11 8
14 1
25 16
2 3
25 3
24 3
20 2
4 27
1 27
32 2
15 25
...

output:

251519103

result:

ok single line: '251519103'

Test #27:

score: 0

Accepted

time: 1256ms

memory: 64936kb

input:

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

output:

645624710

result:

ok single line: '645624710'

Test #28:

score: 0

Accepted

time: 1683ms

memory: 64980kb

input:

35 322 83215822
23 5
13 5
18 23
20 8
5 32
16 6
23 26
5 33
28 15
28 24
28 34
34 4
21 23
17 1
1 16
16 7
27 28
6 30
1 5
2 24
15 21
21 35
29 8
20 4
24 21
6 13
34 35
27 8
22 20
9 6
29 26
4 7
11 15
33 27
32 20
21 34
11 12
32 8
5 29
30 17
23 35
34 30
12 16
4 26
20 15
22 6
32 6
21 29
33 1
10 1
3 11
14 17
29...

output:

568055158

result:

ok single line: '568055158'

Test #29:

score: 0

Accepted

time: 1641ms

memory: 65324kb

input:

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

output:

713518423

result:

ok single line: '713518423'

Test #30:

score: 0

Accepted

time: 1653ms

memory: 65008kb

input:

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

output:

526316962

result:

ok single line: '526316962'

Test #31:

score: 0

Accepted

time: 978ms

memory: 63908kb

input:

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

output:

253768058

result:

ok single line: '253768058'

Test #32:

score: 0

Accepted

time: 945ms

memory: 60648kb

input:

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

output:

372934214

result:

ok single line: '372934214'

Test #33:

score: 0

Accepted

time: 1014ms

memory: 64340kb

input:

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

output:

842468939

result:

ok single line: '842468939'

Test #34:

score: 0

Accepted

time: 1573ms

memory: 64420kb

input:

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

output:

258844910

result:

ok single line: '258844910'

Test #35:

score: 0

Accepted

time: 1229ms

memory: 64568kb

input:

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

output:

919806627

result:

ok single line: '919806627'

Test #36:

score: 0

Accepted

time: 1220ms

memory: 64980kb

input:

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

output:

426225410

result:

ok single line: '426225410'

Test #37:

score: 0

Accepted

time: 1003ms

memory: 64800kb

input:

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

output:

331767880

result:

ok single line: '331767880'

Test #38:

score: 0

Accepted

time: 1567ms

memory: 64932kb

input:

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

output:

46207147

result:

ok single line: '46207147'

Test #39:

score: 0

Accepted

time: 1502ms

memory: 65156kb

input:

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

output:

469807921

result:

ok single line: '469807921'

Test #40:

score: 0

Accepted

time: 1179ms

memory: 64896kb

input:

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

output:

919339893

result:

ok single line: '919339893'

Test #41:

score: 0

Accepted

time: 1316ms

memory: 64772kb

input:

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

output:

795926433

result:

ok single line: '795926433'

Test #42:

score: 0

Accepted

time: 1688ms

memory: 64092kb

input:

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

output:

637398048

result:

ok single line: '637398048'

Test #43:

score: 0

Accepted

time: 1655ms

memory: 65332kb

input:

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

output:

69874215

result:

ok single line: '69874215'

Test #44:

score: 0

Accepted

time: 1140ms

memory: 63892kb

input:

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

output:

707600894

result:

ok single line: '707600894'

Test #45:

score: 0

Accepted

time: 1469ms

memory: 65052kb

input:

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

output:

948550415

result:

ok single line: '948550415'

Test #46:

score: 0

Accepted

time: 845ms

memory: 18020kb

input:

35 0 387237811

output:

result:

ok single line: '1'

Test #47:

score: 0

Accepted

time: 1414ms

memory: 64944kb

input:

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

output:

381017452

result:

ok single line: '381017452'

Test #48:

score: 0

Accepted

time: 886ms

memory: 45540kb

input:

35 18 520325436
33 25
26 31
25 14
21 14
12 10
29 17
32 8
10 2
19 3
4 23
9 14
26 10
27 11
11 16
16 6
22 35
27 25
29 21

output:

866869480

result:

ok single line: '866869480'

Test #49:

score: 0

Accepted

time: 3ms

memory: 9648kb

input:

1 0 240889969

output:

result:

ok single line: '1'

Test #50:

score: 0

Accepted

time: 2ms

memory: 7572kb

input:

2 0 734305586

output:

result:

ok single line: '1'

Test #51:

score: 0

Accepted

time: 2ms

memory: 3604kb

input:

2 1 907431552
2 1

output:

907431553

result:

ok single line: '907431553'