QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#565016#5705. GraphElegia100 ✓89ms26600kbC++232.6kb2024-09-15 19:50:482024-10-09 15:15:26

Judging History

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

  • [2024-10-09 15:15:26]
  • 评测
  • 测评结果:100
  • 用时:89ms
  • 内存:26600kb
  • [2024-09-15 19:50:48]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  while (m--) {
    int u, v, w;
    cin >> u >> v >> w;
    --u; --v;
    w *= 2;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  vector<int> color(n), cons(n), ans(n);

  bool fl = false;
  int det = 0;
  vector<int> cur;
  function<void(int, int, int)> dfs = [&](int u, int col, int con) {
    if (!color[u]) {
      cur.push_back(u);
      color[u] = col;
      cons[u] = con;
      for (auto [v, w] : g[u])
        dfs(v, -col, w - con);
    } else {
      if (color[u] == col) {
        if (con != cons[u]) {
          cout << "NO\n";
          exit(0);
        }
      } else {
        int sol = (cons[u] - con) / (col - color[u]);
        if (!fl) {
          det = sol;
          fl = true;
        } else if (det != sol) {
          cout << "NO\n";
          exit(0);
        }
      }
    }
  };
  for (int i = 0; i < n; ++i) {
    if (color[i]) continue;
    fl = false;
    cur.clear();
    dfs(i, 1, 0);
    if (!fl) {
      vector<int> median;
      for (int u : cur)
        median.push_back(-cons[u] * color[u]);
      nth_element(median.begin(), median.begin() + (median.size() >> 1), median.end());
      det = median[median.size() >> 1];
    }
    for (int u : cur)
      ans[u] = color[u] * det + cons[u];
  }

  vector<double> otp(n);
  for (int i = 0; i < n; ++i) otp[i] = ans[i] * .5;
  cout << "YES\n" << otp << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

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

output:

YES
0.5 0.5 1.5 -0.5

result:

ok answer = YES

Test #2:

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

input:

2 1
1 2 1

output:

YES
1 0

result:

ok answer = YES

Test #3:

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

input:

3 2
1 2 2
2 3 2

output:

YES
0 2 0

result:

ok answer = YES

Test #4:

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

input:

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

output:

NO

result:

ok answer = NO

Test #5:

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

input:

5 2
1 2 1
5 3 2

output:

YES
1 0 2 0 0

result:

ok answer = YES

Test #6:

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

input:

3 2
2 1 2
3 2 1

output:

YES
1 1 0

result:

ok answer = YES

Test #7:

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

input:

3 3
1 2 1
1 3 1
3 2 1

output:

YES
0.5 0.5 0.5

result:

ok answer = YES

Test #8:

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

input:

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

output:

YES
2 0 1 0

result:

ok answer = YES

Test #9:

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

input:

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

output:

NO

result:

ok answer = NO

Test #10:

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

input:

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

output:

YES
1.5 0.5 0.5 0.5

result:

ok answer = YES

Test #11:

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

input:

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

output:

YES
1.5 0.5 0.5 0.5

result:

ok answer = YES

Test #12:

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

input:

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

output:

NO

result:

ok answer = NO

Test #13:

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

input:

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

output:

YES
0.5 0.5 0.5 0.5 1.5

result:

ok answer = YES

Test #14:

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

input:

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

output:

YES
1 0 0 1 1

result:

ok answer = YES

Test #15:

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

input:

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

output:

YES
1 0 0 1 1

result:

ok answer = YES

Test #16:

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

input:

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

output:

YES
1.5 0.5 0.5 0.5 1.5

result:

ok answer = YES

Test #17:

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

input:

1 0

output:

YES
0

result:

ok answer = YES

Test #18:

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

input:

1 1
1 1 1

output:

YES
0.5

result:

ok answer = YES

Test #19:

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

input:

3 14
1 1 2
1 1 2
2 2 1
2 3 2
3 2 2
1 1 2
2 2 1
2 3 2
3 2 2
3 2 2
1 1 2
1 1 2
2 2 1
2 3 2

output:

YES
1 0.5 1.5

result:

ok answer = YES

Test #20:

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

input:

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

output:

YES
1.5 0.5 0.5

result:

ok answer = YES

Test #21:

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

input:

2 2
1 2 2
2 1 2

output:

YES
2 0

result:

ok answer = YES

Test #22:

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

input:

2 2
1 2 2
2 1 1

output:

NO

result:

ok answer = NO

Test #23:

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

input:

3 14
1 1 2
1 1 2
2 2 1
2 3 1
3 2 2
1 1 2
2 2 1
2 3 1
3 2 2
3 2 2
1 1 2
1 1 2
2 2 1
2 3 1

output:

NO

result:

ok answer = NO

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #24:

score: 12
Accepted
time: 0ms
memory: 3756kb

input:

100 99
10 91 1
10 86 2
86 81 2
10 62 1
62 70 1
70 63 1
81 83 2
81 76 1
83 45 1
83 67 2
10 96 1
96 7 1
67 9 1
10 98 2
81 8 1
45 94 1
70 50 2
62 66 1
8 82 2
66 80 1
83 3 2
9 54 2
8 19 2
7 25 1
63 59 2
25 49 1
8 35 1
83 56 1
25 87 2
63 64 2
50 55 2
45 93 1
54 27 2
76 51 1
70 68 1
76 14 1
19 11 1
35 100...

output:

YES
0 2 1 1 2 0 1 0 0 1 -1 -1 1 1 2 2 2 0 2 2 1 1 2 1 0 -1 0 1 0 1 0 1 -1 3 1 2 0 2 3 2 0 1 0 1 0 0 0 2 1 1 1 3 2 2 1 0 1 0 2 3 0 0 0 2 0 1 1 0 1 1 1 0 0 1 -1 0 -1 -1 1 0 1 2 1 2 1 1 2 1 0 2 0 2 1 1 1 0 0 1 1 1

result:

ok answer = YES

Test #25:

score: 12
Accepted
time: 0ms
memory: 4052kb

input:

50 49
31 8 2
31 7 2
31 34 1
7 49 1
34 16 2
8 24 1
8 33 1
8 21 1
21 15 2
34 4 2
49 46 1
34 18 2
21 28 2
33 23 1
31 43 2
4 17 2
23 10 2
16 30 2
30 37 2
34 25 2
17 19 1
34 40 1
31 29 2
46 32 2
33 48 2
31 14 1
14 44 1
14 9 2
4 5 1
43 2 2
49 1 2
17 26 2
4 36 2
44 11 2
21 12 2
15 3 1
17 6 2
15 13 1
13 42 ...

output:

YES
2 1 -1 2 -1 2 1 1 2 1 1 2 -1 0 2 2 0 2 1 1 0 0 1 0 2 2 2 2 1 0 1 1 0 0 0 0 2 0 3 1 0 2 1 1 1 1 1 2 0 1

result:

ok answer = YES

Test #26:

score: 12
Accepted
time: 0ms
memory: 3808kb

input:

88 87
16 28 1
28 32 2
32 34 1
32 3 2
16 81 1
34 9 2
28 77 1
77 60 1
3 43 1
3 56 2
56 51 2
3 33 1
34 63 2
60 62 1
63 30 1
51 47 2
16 78 2
63 18 1
18 71 2
78 29 1
28 52 1
33 40 1
9 11 2
29 48 1
51 72 2
71 41 2
43 5 1
63 13 2
18 10 1
62 22 1
60 27 1
56 76 1
62 19 2
40 7 2
3 42 2
60 57 2
22 14 1
27 23 2...

output:

YES
3 1 1 -2 1 1 1 0 2 2 0 2 0 0 1 0 0 -1 2 1 1 1 2 1 2 0 0 1 -1 -1 2 1 0 0 -2 -1 0 1 1 1 -1 1 0 2 -1 1 1 2 -1 0 1 0 1 1 0 1 1 1 1 1 3 0 2 0 3 2 -1 1 1 0 3 1 -1 2 1 0 0 2 1 3 1 0 3 0 -2 2 -1 1

result:

ok answer = YES

Test #27:

score: 12
Accepted
time: 0ms
memory: 3828kb

input:

88 88
16 28 1
28 32 2
32 34 1
32 3 2
16 81 1
34 9 2
28 77 1
77 60 1
3 43 1
3 56 2
56 51 2
3 33 1
34 63 2
60 62 1
63 30 1
51 47 2
16 78 2
63 18 1
18 71 2
78 29 1
28 52 1
33 40 1
9 11 2
29 48 1
51 72 2
71 41 2
43 5 1
63 13 2
18 10 1
62 22 1
60 27 1
16 29 1
56 76 1
62 19 2
40 7 2
3 42 2
60 57 2
22 14 1...

output:

YES
2 2 0 -3 0 2 2 1 3 3 -1 3 -1 1 2 1 1 -2 1 2 2 0 1 0 3 1 1 0 0 -2 1 2 1 -1 -1 -2 -1 0 0 0 -2 2 1 1 0 2 2 1 -2 -1 0 1 0 0 -1 2 2 2 2 0 4 1 3 -1 2 3 -2 0 0 1 4 2 -2 3 0 -1 1 1 0 4 0 1 2 1 -3 3 -2 2

result:

ok answer = YES

Test #28:

score: 12
Accepted
time: 0ms
memory: 3756kb

input:

100 100
17 44 1
30 17 2
18 30 1
88 18 2
75 88 1
14 75 1
44 14 2
57 44 2
92 57 2
37 92 1
70 37 2
9 70 2
55 9 2
25 55 2
35 25 1
84 35 2
62 84 2
74 62 2
67 74 1
16 67 2
83 17 1
50 83 1
2 50 1
65 2 2
89 65 1
49 89 1
76 49 1
97 76 2
56 97 2
47 56 1
42 47 1
32 42 2
82 32 1
19 82 1
95 30 1
4 95 2
81 4 1
61...

output:

YES
2 0 0 2 0 0 2 1 1 3 0 2 -1 2 3 3 1 0 3 0 2 2 -1 2 1 0 1 0 2 1 3 3 -1 2 0 -1 1 1 3 2 -1 -1 2 0 -1 -2 2 0 2 1 0 2 -1 -1 1 -1 2 2 0 2 2 0 -2 2 2 2 -1 -1 3 1 -1 3 -1 2 -1 -1 3 2 -1 -1 -1 -2 0 2 0 2 1 2 -1 0 0 0 -1 -1 0 1 3 2 1 3

result:

ok answer = YES

Test #29:

score: 12
Accepted
time: 0ms
memory: 3820kb

input:

100 100
17 57 1
30 17 1
18 30 1
88 18 1
75 88 1
14 75 1
44 14 1
57 44 1
92 57 2
37 92 1
70 37 2
9 70 2
55 9 2
25 55 2
35 25 1
84 35 2
62 84 2
74 62 2
67 74 1
16 67 2
83 17 1
50 83 1
2 50 1
65 2 2
89 65 1
49 89 1
76 49 1
97 76 2
56 97 2
47 56 1
42 47 1
32 42 2
82 32 1
19 82 1
95 30 1
4 95 2
81 4 1
61...

output:

YES
3 1 0 2 1 1 2 0 0 2 1 2 0 1 2 2 0 0 2 1 2 2 0 2 0 0 2 -1 2 1 2 2 -1 1 1 0 0 0 2 1 -1 0 2 0 -1 -1 1 1 1 0 0 1 -1 -2 2 0 1 2 0 2 2 1 -1 3 1 2 0 -1 3 2 -1 4 -1 1 0 0 2 1 0 -1 -1 -1 1 1 0 2 0 1 0 0 -1 1 0 -1 0 1 2 2 2 2

result:

ok answer = YES

Test #30:

score: 12
Accepted
time: 0ms
memory: 3620kb

input:

100 100
17 57 1
30 17 2
18 30 1
88 18 2
75 88 1
14 75 1
44 14 2
57 44 2
92 57 2
37 92 1
70 37 2
9 70 2
55 9 2
25 55 2
35 25 1
84 35 2
62 84 2
74 62 2
67 74 1
16 67 2
83 17 1
50 83 1
2 50 1
65 2 2
89 65 1
49 89 1
76 49 1
97 76 2
56 97 2
47 56 1
42 47 1
32 42 2
82 32 1
19 82 1
95 30 1
4 95 2
81 4 1
61...

output:

NO

result:

ok answer = NO

Test #31:

score: 12
Accepted
time: 0ms
memory: 3816kb

input:

77 77
33 31 2
68 66 1
10 8 2
24 22 2
66 64 2
8 6 2
38 36 2
77 75 2
50 48 2
7 5 1
74 72 2
2 76 2
1 77 2
20 18 1
39 37 1
28 26 1
64 62 2
37 35 1
9 7 2
61 59 1
43 41 2
16 14 1
62 60 2
36 34 1
25 23 2
19 17 2
70 68 1
35 33 2
53 51 1
21 19 2
32 30 2
3 1 2
11 9 2
45 43 2
30 28 1
34 32 2
29 27 2
27 25 2
47...

output:

YES
1.5 2 0.5 0 1.5 1 -0.5 1 2.5 1 -0.5 0 1.5 1 0.5 0 0.5 1 1.5 0 0.5 1 0.5 1 1.5 0 0.5 1 1.5 0 0.5 2 1.5 0 0.5 1 0.5 1 0.5 1 1.5 1 0.5 1 1.5 1 -0.5 0 1.5 2 -0.5 -1 1.5 2 -0.5 0 1.5 1 0.5 1 0.5 1 1.5 1 -0.5 1 1.5 0 -0.5 1 1.5 1 0.5 1 1.5 0 0.5

result:

ok answer = YES

Test #32:

score: 12
Accepted
time: 0ms
memory: 3824kb

input:

77 77
77 77 1
76 76 1
75 75 1
74 2 2
73 76 2
72 72 1
71 72 1
70 35 1
69 5 2
68 68 2
67 67 1
66 8 1
65 65 1
64 37 2
63 23 1
62 36 2
61 61 1
60 60 2
59 67 2
58 58 2
57 13 1
56 56 2
55 60 1
54 54 2
53 21 2
52 48 1
51 75 1
50 7 2
49 42 2
48 48 2
47 15 2
46 46 2
45 45 2
44 44 2
43 16 1
42 42 2
41 58 1
40...

output:

YES
0.5 0.5 1 1.5 1 1 0.5 0.5 1.5 1 0 1 1 1 1 1 0.5 1 0.5 0.5 0.5 1.5 0.5 1 1.5 0.5 1 1 1 0.5 1 1 1 0.5 0.5 0.5 1 1.5 1 0 0 1 0 1 1 1 1 1 1 1.5 0.5 0 1.5 1 0 1 0 1 1.5 1 0.5 1.5 0.5 1 0.5 0.5 0.5 1 1 0.5 0.5 0.5 1.5 1.5 0.5 0.5 0.5

result:

ok answer = YES

Test #33:

score: 12
Accepted
time: 0ms
memory: 4040kb

input:

76 38
2 1 1
65 4 1
67 6 2
66 8 1
37 9 1
3 11 2
48 12 2
23 18 2
46 22 1
10 24 1
36 25 2
42 26 2
34 29 2
45 30 1
75 31 1
21 32 1
20 39 2
14 40 2
5 41 1
61 43 2
27 47 2
44 49 1
38 50 2
13 51 2
72 52 1
35 53 1
58 55 2
56 57 2
15 59 2
16 62 1
17 63 2
28 64 1
33 68 2
76 69 1
19 70 1
60 71 1
54 73 1
7 74 2

output:

YES
1 0 2 1 1 2 2 1 1 1 0 2 2 2 2 1 2 2 1 2 1 1 0 0 2 2 2 1 2 1 1 0 2 0 1 0 0 2 0 0 0 0 2 1 0 0 0 0 0 0 0 1 0 1 2 2 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

result:

ok answer = YES

Test #34:

score: 12
Accepted
time: 0ms
memory: 4044kb

input:

100 113
82 73 1
65 22 1
58 24 1
4 52 1
68 60 1
85 10 1
76 43 1
34 47 1
14 65 1
84 90 1
35 74 1
32 15 1
74 35 1
75 46 1
52 97 1
85 56 1
56 95 1
66 54 1
11 52 1
31 15 1
57 78 1
62 49 1
12 59 1
7 71 1
23 81 1
68 4 1
30 70 1
80 67 1
94 99 1
42 71 1
71 60 1
85 75 1
99 72 1
65 83 1
18 51 1
97 43 1
78 95 1...

output:

YES
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0.5 0.5 1 0.5 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0.5 0.5 0 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 1 0 1 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0.5 0.5 1 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0 0.5 0.5 ...

result:

ok answer = YES

Test #35:

score: 12
Accepted
time: 0ms
memory: 3872kb

input:

77 77
33 31 2
68 66 1
10 8 2
24 22 1
66 64 1
8 6 1
38 36 1
77 75 1
50 48 1
7 5 1
74 72 1
2 2 2
1 1 1
20 18 1
39 37 1
28 26 1
64 62 2
37 35 2
9 7 1
61 59 2
43 41 2
16 14 2
62 60 1
36 34 1
25 23 2
19 17 1
70 68 1
35 33 2
53 51 1
21 19 2
32 30 1
3 1 2
11 9 1
45 43 1
30 28 1
34 32 1
29 27 1
27 25 2
47 4...

output:

YES
0.5 1 1.5 1 0.5 1 0.5 0 0.5 2 0.5 0 1.5 2 -0.5 0 1.5 2 -0.5 -1 2.5 3 -1.5 -2 3.5 3 -1.5 -2 2.5 3 -0.5 -2 2.5 3 -0.5 -2 2.5 3 -1.5 -2 2.5 3 -0.5 -1 1.5 2 -0.5 -1 1.5 2 -0.5 -1 1.5 3 0.5 -2 1.5 4 0.5 -2 1.5 3 0.5 -1 1.5 2 -0.5 -1 2.5 2 -1.5 0 2.5 1 -1.5 0 2.5

result:

ok answer = YES

Test #36:

score: 12
Accepted
time: 0ms
memory: 3816kb

input:

77 78
33 31 2
68 66 1
10 8 2
24 22 1
66 64 1
8 6 1
38 36 1
77 75 1
50 48 1
7 5 1
74 72 1
2 2 1
1 1 2
20 18 1
39 37 1
28 26 1
64 62 2
37 35 2
9 7 1
61 59 2
43 41 2
16 14 2
62 60 1
36 34 1
25 23 2
19 17 1
70 68 1
35 33 2
53 51 1
21 19 2
32 30 1
3 1 2
11 9 1
45 43 1
30 28 1
34 32 1
29 27 1
27 25 2
47 4...

output:

YES
1 0.5 1 1.5 1 0.5 0 0.5 1 1.5 0 0.5 2 1.5 -1 0.5 2 1.5 -1 -0.5 3 2.5 -2 -1.5 4 2.5 -2 -1.5 3 2.5 -1 -1.5 3 2.5 -1 -1.5 3 2.5 -2 -1.5 3 2.5 -1 -0.5 2 1.5 -1 -0.5 2 1.5 -1 -0.5 2 2.5 0 -1.5 2 3.5 0 -1.5 2 2.5 0 -0.5 2 1.5 -1 -0.5 3 1.5 -2 0.5 3 0.5 -2 0.5 3

result:

ok answer = YES

Subtask #3:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #37:

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

input:

211 210
129 163 1
129 193 1
129 65 1
163 142 2
129 93 2
93 126 2
163 73 1
163 6 2
6 44 1
93 203 1
126 174 2
73 168 1
142 64 1
193 173 1
193 86 1
142 130 2
86 143 1
6 22 2
142 60 2
64 89 1
142 105 1
129 48 1
174 125 2
22 12 1
129 38 2
130 170 1
65 8 2
22 114 1
126 108 2
130 172 2
168 90 2
48 123 2
12...

output:

YES
0 0 -1 1 -1 1 1 1 1 1 1 0 1 2 1 1 -1 1 1 1 2 1 0 0 0 0 0 2 1 1 1 0 2 2 1 2 1 2 1 -1 0 0 0 0 2 1 1 1 0 1 1 0 1 1 0 2 0 1 0 1 -1 -1 1 0 1 1 1 -1 2 1 2 0 0 -1 2 1 4 0 2 0 -1 0 1 2 2 0 1 1 1 1 0 0 2 0 1 0 -1 0 1 1 1 1 2 0 0 -2 1 2 0 1 0 2 2 0 2 1 -1 -2 1 0 0 0 1 2 0 0 2 3 0 1 1 -1 1 1 -1 0 1 1 2 2 0...

result:

ok answer = YES

Test #38:

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

input:

211 211
129 163 1
129 193 1
129 65 1
163 142 2
129 93 2
93 126 2
163 73 1
163 6 2
6 44 1
93 203 1
126 174 2
73 168 1
142 64 1
193 173 1
193 86 1
142 130 2
86 143 1
6 22 2
142 60 2
64 89 1
142 105 1
129 48 1
174 125 2
22 12 1
129 38 2
130 170 1
65 8 2
22 114 1
126 108 2
130 172 2
168 90 2
48 123 2
12...

output:

YES
-0.5 0.5 -0.5 0.5 -0.5 1.5 0.5 1.5 0.5 1.5 0.5 0.5 0.5 1.5 0.5 1.5 -0.5 1.5 1.5 0.5 2.5 0.5 0.5 0.5 0.5 -0.5 -0.5 1.5 0.5 0.5 0.5 0.5 2.5 1.5 0.5 1.5 0.5 1.5 0.5 -1.5 -0.5 0.5 0.5 -0.5 1.5 0.5 0.5 0.5 0.5 0.5 1.5 -0.5 0.5 1.5 0.5 1.5 0.5 1.5 0.5 0.5 -0.5 -0.5 1.5 -0.5 0.5 0.5 0.5 -1.5 1.5 1.5 1....

result:

ok answer = YES

Test #39:

score: 17
Accepted
time: 1ms
memory: 3992kb

input:

547 546
15 139 2
139 397 1
15 327 1
15 510 1
510 74 1
74 91 1
91 303 1
74 515 2
139 462 2
91 514 1
515 355 1
515 135 1
510 503 1
397 310 2
74 499 1
462 23 2
23 478 2
310 53 1
74 64 2
15 261 2
499 541 1
303 407 1
64 505 1
139 289 2
505 4 2
15 404 1
74 188 2
289 402 2
407 332 2
510 210 1
23 547 1
402 ...

output:

YES
1 0 -1 2 1 1 1 0 2 0 1 1 2 1 1 1 1 1 1 0 0 0 1 1 2 0 3 0 0 0 0 0 2 2 1 0 1 1 1 2 0 2 0 0 1 1 2 0 0 2 0 1 -1 0 3 -1 0 0 0 2 2 3 1 1 2 0 2 2 1 3 2 0 1 1 0 1 0 1 -1 1 1 0 1 1 1 1 2 3 0 0 0 0 2 1 1 2 1 1 2 0 1 3 2 2 2 1 1 1 -1 0 0 0 0 1 0 1 1 0 3 2 -1 -1 1 1 1 1 1 2 1 0 0 1 -1 1 0 3 -1 1 1 2 0 2 1 2...

result:

ok answer = YES

Test #40:

score: 17
Accepted
time: 1ms
memory: 4056kb

input:

935 935
923 195 1
388 923 1
439 388 2
101 439 1
180 101 2
880 180 1
636 880 2
225 636 1
152 225 1
155 152 2
549 155 2
74 549 2
614 74 2
130 614 2
330 130 2
658 330 2
585 658 1
293 585 1
112 293 2
789 112 1
822 789 2
478 822 2
268 478 2
249 268 2
699 249 2
230 699 2
298 230 1
254 298 2
404 254 1
615 ...

output:

YES
6 3 -1 -1 3 -2 -1 -4 1 2 -6 -6 -5 2 -10 -5 1 7 -3 4 -1 8 3 1 -1 -6 -1 -4 2 9 -3 0 3 -6 7 12 -1 -2 -2 0 5 0 -1 -2 5 -5 3 3 3 3 -2 2 -5 7 3 9 1 2 -6 -1 6 1 -1 -4 0 0 2 -3 7 6 4 1 -1 -2 -1 -2 -2 -2 1 -5 5 -11 0 2 -3 7 -2 0 -5 1 3 -7 1 6 3 -10 -1 -5 2 2 -1 0 -1 -5 -5 -4 3 -3 -8 3 -4 4 8 1 9 2 6 -4 6...

result:

ok answer = YES

Test #41:

score: 17
Accepted
time: 1ms
memory: 3916kb

input:

935 935
621 758 2
758 394 1
24 758 1
543 24 1
762 543 1
794 762 2
489 794 1
195 489 1
923 195 2
388 923 2
439 388 2
101 439 1
180 101 2
880 180 2
636 880 1
225 636 2
152 225 1
155 152 2
549 155 2
74 549 2
614 74 2
130 614 2
330 130 2
658 330 1
585 658 2
293 585 1
112 293 2
789 112 2
822 789 1
478 82...

output:

NO

result:

ok answer = NO

Test #42:

score: 17
Accepted
time: 1ms
memory: 4052kb

input:

935 935
923 195 1
388 923 1
439 388 2
101 439 1
180 101 2
880 180 2
636 880 1
225 636 1
152 225 2
155 152 2
549 155 2
74 549 2
614 74 1
130 614 1
330 130 1
658 330 2
585 658 1
293 585 1
112 293 2
789 112 2
822 789 1
478 822 2
268 478 2
249 268 2
699 249 2
230 699 1
298 230 1
254 298 2
404 254 2
615 ...

output:

YES
4 1 -4 3 6 -3 4 9 0 -2 -2 4 -3 0 -7 5 5 -7 -6 4 10 -2 -1 -2 5 -4 0 3 3 4 2 4 4 -3 4 8 4 4 2 4 -11 3 -2 -5 6 9 3 3 5 -4 -2 5 10 -1 6 4 -2 2 -2 -3 6 3 0 9 2 5 -2 12 -8 2 5 9 5 2 5 1 -4 -5 -1 3 -1 -1 -2 -4 -2 -6 0 4 11 -2 -8 -4 1 -1 -4 -3 -4 9 -2 -2 2 0 -5 8 -4 -6 1 -1 -6 5 -3 -1 4 -4 5 2 6 3 6 6 2...

result:

ok answer = YES

Test #43:

score: 17
Accepted
time: 1ms
memory: 3908kb

input:

999 996
10 58 2
101 80 2
101 812 1
106 178 1
11 494 2
11 518 2
110 320 2
111 210 2
111 228 2
111 609 2
112 682 2
112 733 2
113 191 2
115 133 1
115 406 1
115 697 2
116 563 1
117 552 1
12 756 2
120 30 1
122 884 2
123 282 1
123 594 1
127 238 2
127 553 1
13 145 2
130 10 2
130 121 1
131 251 2
131 263 1
1...

output:

YES
1 2 1 1 2 2 -2 1 1 3 0 2 1 -1 0 -1 1 0 -1 -1 0 -1 -1 1 1 1 1 0 0 0 0 2 1 -2 1 2 3 1 0 -2 1 4 0 0 0 2 0 3 0 1 1 -2 1 2 2 0 -2 -1 2 -1 1 1 1 0 1 1 -1 2 2 -1 3 2 0 -1 0 1 0 2 0 1 1 0 2 1 3 0 0 -1 1 0 2 1 3 -1 2 2 3 1 1 -1 1 1 -1 -1 1 3 2 -1 0 2 0 2 1 1 3 1 1 1 -1 1 2 -2 0 -1 2 1 -1 1 1 -1 1 2 -2 0 ...

result:

ok answer = YES

Test #44:

score: 17
Accepted
time: 1ms
memory: 3908kb

input:

994 987
769 256 2
906 812 1
453 603 1
556 451 2
847 862 1
945 793 1
223 551 2
256 590 1
812 980 1
603 545 1
451 914 2
862 554 1
793 798 2
551 645 2
590 309 1
980 672 1
545 138 1
914 233 2
554 546 1
798 927 2
645 639 1
309 711 2
672 116 1
138 153 1
233 594 2
546 307 1
927 957 2
639 682 1
711 313 1
11...

output:

YES
2 2 -4 3 -1 -4 0 -1 0 -1 -2 -1 -2 5 0 2 -1 1 5 0 -1 4 4 3 -3 -1 6 -2 2 -2 -2 -2 2 -2 0 -1 1 1 0 1 4 -3 1 0 0 -1 0 -3 -1 3 -2 -2 -2 -2 -3 0 0 -2 4 2 -1 3 -2 1 3 2 -3 -1 3 -2 4 1 4 -2 2 0 -1 5 -1 3 1 -2 3 2 1 1 -1 -3 4 3 -4 4 2 3 -3 1 0 -2 1 4 -4 -2 1 3 5 -2 0 -2 3 -5 3 3 5 3 2 -3 2 2 -3 -1 -2 -1 ...

result:

ok answer = YES

Test #45:

score: 17
Accepted
time: 1ms
memory: 4004kb

input:

994 994
769 256 2
906 812 1
453 603 1
556 451 2
847 862 1
945 793 1
223 551 2
256 590 1
812 980 1
603 545 1
451 914 2
862 554 1
793 798 2
551 645 2
590 309 1
980 672 1
545 138 1
914 233 2
554 546 1
798 927 2
645 639 1
309 711 2
672 116 1
138 153 1
233 594 2
546 307 1
927 957 2
639 682 1
711 313 1
11...

output:

YES
3.5 4.5 -3.5 0.5 -3 -6.5 -11 -3.5 -2.5 1.5 -3.5 1 -4 3.5 -11 0 -1.5 -1 4.5 -0.5 -3.5 2 -7 14 -5.5 -1.5 3.5 -4.5 4.5 -4 -4.5 -4.5 4.5 -13 -2.5 -3.5 0.5 1.5 0.5 -1 1.5 -5.5 3 -2 -2.5 1.5 -11 -2.5 -3.5 -8 0 -2.5 -0.5 0.5 -0.5 -2.5 -2.5 0.5 2.5 4.5 -2.5 -8 -4.5 -1.5 0.5 2.5 -0.5 1.5 1 -4.5 1.5 2.5 5...

result:

ok answer = YES

Test #46:

score: 17
Accepted
time: 1ms
memory: 3892kb

input:

500 491
87 78 2
78 434 1
434 26 1
26 98 1
98 50 2
50 59 2
50 485 2
434 8 2
50 418 2
98 466 1
26 426 1
26 244 1
59 276 2
466 116 1
426 259 2
418 420 1
259 123 2
276 390 1
78 242 1
87 174 2
50 464 2
390 25 1
244 465 2
485 448 2
390 105 2
390 133 1
426 132 2
242 315 2
448 23 2
133 216 1
420 293 2
453 1...

output:

YES
2 0 0 1 0 -1 0 1 0 0 0 0 0 1 2 0 2 1 2 1 2 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 -1 0 2 -2 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 2 1 -1 0 1 1 1 1 0 -2 0 1 1 0 0 0 0 0 0 2 0 1 1 1 1 1 2 1 1 0 2 0 1 2 0 1 0 1 1 0 2 1 1 3 2 0 0 1 2 1 2 -1 1 0 0 1 0 1 0 1 0 2 1 2 0 -1 1 0 1 1 1 1 1 2 1 0 1 1 0 0 0 1 1 0 1...

result:

ok answer = YES

Test #47:

score: 17
Accepted
time: 1ms
memory: 3976kb

input:

994 994
769 256 2
906 812 1
453 603 1
556 451 2
847 862 1
945 793 1
223 551 2
256 590 1
812 980 1
603 545 1
451 914 2
862 554 1
793 798 2
551 645 2
590 309 1
980 672 1
545 138 1
914 233 2
554 546 1
798 927 2
645 639 1
309 711 2
672 116 1
138 153 1
233 594 2
546 307 1
927 957 2
639 682 1
711 313 1
11...

output:

YES
1.5 4.5 -3.5 0.5 -2.5 -6.5 -7.5 -3.5 -2.5 1.5 -1.5 0.5 -3.5 5.5 -7.5 0.5 -1.5 -0.5 4.5 -0.5 -3.5 2.5 -3.5 10.5 -5.5 -1.5 3.5 -4.5 4.5 -3.5 -4.5 -4.5 4.5 -9.5 -2.5 -3.5 0.5 1.5 0.5 -0.5 1.5 -5.5 2.5 -1.5 -2.5 1.5 -7.5 -2.5 -3.5 -4.5 -0.5 -2.5 -2.5 0.5 -0.5 -2.5 -2.5 0.5 4.5 4.5 -0.5 -4.5 -4.5 -1....

result:

ok answer = YES

Test #48:

score: 17
Accepted
time: 1ms
memory: 4092kb

input:

994 994
769 256 2
906 812 1
453 603 1
556 451 2
847 862 1
945 793 1
223 551 2
256 590 1
812 980 1
603 545 1
451 914 2
862 554 1
793 798 2
551 645 2
590 309 1
980 672 1
545 138 1
914 233 2
554 546 1
798 927 2
645 639 1
309 711 2
672 116 1
138 153 1
233 594 2
546 307 1
927 957 2
639 682 1
711 313 1
11...

output:

YES
-3.5 -0.5 -8.5 5.5 2.5 -1.5 -2.5 1.5 2.5 -3.5 3.5 -4.5 1.5 10.5 -2.5 5.5 3.5 4.5 9.5 4.5 1.5 7.5 1.5 5.5 -0.5 3.5 8.5 0.5 -0.5 1.5 0.5 0.5 -0.5 -4.5 2.5 1.5 5.5 -3.5 -4.5 4.5 6.5 -0.5 -2.5 3.5 2.5 -3.5 -2.5 -7.5 1.5 0.5 -5.5 2.5 -7.5 -4.5 -5.5 2.5 2.5 -4.5 9.5 -0.5 4.5 0.5 0.5 3.5 5.5 -2.5 -5.5 ...

result:

ok answer = YES

Subtask #4:

score: 24
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #49:

score: 24
Accepted
time: 0ms
memory: 4428kb

input:

10000 9999
5747 266 1
266 9872 1
5747 8144 1
9872 2774 2
5747 7634 2
9872 1928 1
2774 832 2
832 1722 1
8144 6572 1
1722 2037 2
266 9295 2
1928 7512 2
9872 2290 1
8144 7191 2
7634 1399 2
1399 7651 2
7634 8450 2
1928 6152 1
8450 1114 2
7634 1656 2
8144 210 1
5747 7076 1
266 8302 1
7512 5384 2
5747 842...

output:

YES
0 -1 1 0 1 1 3 0 2 3 3 3 -3 3 0 2 1 2 0 0 1 1 1 1 3 -2 2 2 2 4 1 -1 5 2 0 1 1 2 3 0 1 0 0 1 -1 2 1 0 -2 1 -2 1 1 -2 -1 0 -1 1 1 2 1 1 4 1 4 -1 -3 0 2 4 2 1 1 2 3 0 1 -1 2 4 -1 1 3 -3 0 0 -2 1 4 1 1 -1 4 1 0 2 0 0 4 2 4 0 -2 0 1 1 0 2 1 1 4 -1 0 -1 0 0 4 2 2 2 -2 0 3 0 0 0 0 2 -1 3 -1 1 0 -1 -1 4...

result:

ok answer = YES

Test #50:

score: 24
Accepted
time: 2ms
memory: 5064kb

input:

9973 9973
1477 3608 1
8395 1477 2
5665 8395 1
2668 5665 2
7601 2668 2
2873 7601 2
852 2873 2
977 852 1
3382 977 2
2550 3382 2
8679 2550 2
3337 8679 2
935 3337 1
3454 935 1
1420 3454 2
6414 1420 1
6027 6414 2
4967 6027 2
6092 4967 1
9257 6092 2
6754 9257 1
7991 6754 1
1639 7991 1
2323 1639 2
5656 232...

output:

YES
8.5 22.5 -7.5 24.5 0.5 -8.5 -6.5 10.5 26.5 16.5 -8.5 -21.5 -4.5 -5.5 8.5 -7.5 -4.5 -1.5 -3.5 -19.5 16.5 -6.5 4.5 12.5 -8.5 -12.5 -4.5 14.5 -10.5 -24.5 17.5 -12.5 4.5 4.5 10.5 -32.5 1.5 16.5 12.5 25.5 -2.5 -12.5 -20.5 -20.5 0.5 6.5 13.5 1.5 9.5 16.5 14.5 4.5 -12.5 -1.5 6.5 1.5 7.5 -5.5 5.5 6.5 -4...

result:

ok answer = YES

Test #51:

score: 24
Accepted
time: 5ms
memory: 5224kb

input:

9973 9973
8395 1477 2
5665 8395 1
2668 5665 2
7601 2668 2
2873 7601 1
852 2873 2
977 852 1
3382 977 1
2550 3382 2
8679 2550 1
3337 8679 1
935 3337 2
3454 935 2
1420 3454 1
6414 1420 1
6027 6414 2
4967 6027 2
6092 4967 2
9257 6092 2
6754 9257 1
7991 6754 2
1639 7991 1
2323 1639 2
5656 2323 1
5228 565...

output:

YES
5 7 1 9 8 9 16 1 16 -8 -13 -5 21 -15 5 0 -3 -7 -8 21 -16 -14 4 6 -5 4 16 -1 1 -11 -19 4 16 3 -16 2 9 0 -20 13 -4 5 -10 -6 -7 7 1 10 -17 -2 0 1 17 -4 15 12 13 -14 -3 0 -6 0 -6 17 8 4 -12 -10 10 2 16 7 11 -9 11 5 1 12 10 -6 -11 7 21 -4 -8 7 -5 5 -6 4 9 2 11 8 -2 -7 5 9 1 -5 7 7 7 7 -6 -5 -17 -12 1...

result:

ok answer = YES

Test #52:

score: 24
Accepted
time: 2ms
memory: 4344kb

input:

9973 9973
3608 4715 2
4715 2860 1
803 3645 1
3645 1477 2
1477 3608 2
8395 1477 1
5665 8395 2
2668 5665 2
7601 2668 2
2873 7601 1
852 2873 2
977 852 2
3382 977 1
2550 3382 1
8679 2550 2
3337 8679 1
935 3337 2
3454 935 1
1420 3454 2
6414 1420 1
6027 6414 2
4967 6027 2
6092 4967 2
9257 6092 1
6754 9257...

output:

NO

result:

ok answer = NO

Test #53:

score: 24
Accepted
time: 1ms
memory: 3904kb

input:

1023 1022
872 171 1
171 588 2
588 510 2
171 189 1
510 689 2
872 545 2
588 921 2
588 928 1
872 737 1
189 97 1
737 546 1
545 1004 2
588 524 1
928 608 2
689 934 1
872 489 1
872 43 1
737 141 2
97 331 1
588 657 2
928 960 1
510 526 2
510 684 2
171 240 1
545 745 1
684 880 1
745 42 2
608 722 1
97 694 2
684 ...

output:

YES
0 2 1 0 2 0 1 2 -1 2 1 0 -1 3 3 3 1 -1 0 2 1 0 0 0 0 0 2 1 -2 1 1 0 0 -2 0 0 2 -1 1 1 1 3 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 2 0 1 0 0 -1 1 4 0 1 1 2 0 1 0 2 2 1 0 1 0 3 1 0 1 1 3 0 1 1 0 2 1 1 1 1 2 1 0 1 1 0 2 0 0 1 0 -1 3 0 1 1 0 -1 2 1 1 0 0 2 1 0 1 -2 2 2 1 1 2 1 3 1 1 -1 -1 2 1 2 -2 2 3 1 1...

result:

ok answer = YES

Test #54:

score: 24
Accepted
time: 1ms
memory: 4032kb

input:

2371 2370
1991 1896 1
1991 655 2
1991 722 1
655 130 2
1991 2134 1
2134 2221 1
722 1370 1
2221 497 2
2221 2271 2
722 1261 2
2134 1274 1
2271 1311 1
1896 1686 2
655 526 1
2271 127 1
1274 580 1
1274 639 1
1896 2000 2
722 2115 2
2221 1323 2
1370 220 1
655 331 2
1274 2293 2
1370 2200 1
526 377 2
130 1756...

output:

YES
5 0 1 3 -1 1 4 0 1 0 2 4 3 0 -3 1 1 -1 0 0 0 0 3 0 0 1 2 2 0 1 0 1 0 -1 0 0 0 1 0 3 1 2 0 0 0 3 3 1 0 2 0 -1 0 -1 0 2 -1 1 0 2 1 -2 -1 3 0 0 -2 1 2 2 0 0 3 1 1 1 1 0 2 1 3 2 3 0 0 3 2 2 -1 1 1 2 0 0 2 2 3 2 1 0 0 2 0 1 2 3 1 0 1 1 2 0 2 0 2 0 2 0 2 1 0 -1 2 2 1 -1 -1 2 1 0 -1 1 -1 2 1 3 -1 0 0 1...

result:

ok answer = YES

Test #55:

score: 24
Accepted
time: 0ms
memory: 4512kb

input:

4997 4996
4963 352 2
4963 1455 2
1455 2819 1
4963 4962 2
4963 4682 1
4962 790 2
4682 2915 2
4963 1111 2
1111 2166 2
4963 4903 1
352 3693 2
4962 374 2
1455 3866 1
2819 1683 1
352 1651 1
4963 1330 2
374 1891 2
1891 3382 2
1111 2322 2
2819 4041 1
1111 4154 1
3382 4754 1
352 2045 2
1683 4293 1
1330 2192...

output:

YES
2 2 2 2 0 2 1 1 -1 0 1 2 1 0 -1 2 2 1 2 1 0 1 0 -2 1 3 1 0 0 1 1 0 3 0 -1 2 2 1 0 -1 1 -1 2 2 0 0 -1 1 2 -1 0 2 1 1 0 2 1 0 1 0 1 0 2 1 2 1 1 3 0 -1 1 2 1 3 1 -1 2 -2 0 -1 -2 1 -2 1 1 0 0 1 0 2 1 1 0 -1 0 0 3 0 0 -1 1 -1 -1 0 0 0 0 0 3 3 -1 1 1 -2 1 2 1 1 1 1 1 1 0 0 0 0 -1 -1 0 3 0 0 1 2 1 2 3 ...

result:

ok answer = YES

Test #56:

score: 24
Accepted
time: 4ms
memory: 4408kb

input:

9778 9777
4271 8223 1
8223 7058 1
8223 7079 1
4271 3842 1
4271 6263 1
4271 6292 2
6263 3911 2
4271 9564 1
6292 1474 2
4271 260 1
7058 5457 1
3911 9621 2
3842 5607 1
6263 8867 2
6292 5383 2
7058 8749 1
8749 6297 1
4271 494 1
1474 7785 2
6263 7765 1
4271 2446 2
6297 5308 1
260 9553 2
5607 1473 2
6263 ...

output:

YES
-1 1 -1 1 1 2 3 0 1 1 -1 1 -1 -1 -1 1 -3 1 0 1 1 -2 2 -1 0 -2 0 1 2 1 3 1 1 1 0 2 1 -1 0 -2 0 1 0 1 2 1 1 -1 2 1 0 1 2 0 0 -1 -1 1 -1 0 -2 0 0 1 1 0 -2 0 2 -1 2 3 1 0 0 3 -1 1 2 2 -1 3 0 1 4 0 -1 2 1 3 -1 1 0 -2 1 -1 -1 0 2 2 0 -2 3 1 2 0 -2 0 -1 0 0 2 0 0 1 3 1 1 3 -1 -1 1 0 0 0 0 -1 2 0 2 -1 2...

result:

ok answer = YES

Test #57:

score: 24
Accepted
time: 4ms
memory: 4424kb

input:

9997 9225
5985 4701 2
4701 2238 2
2238 8981 2
4701 639 1
2238 5287 1
5287 3138 2
5322 4023 2
5322 6785 2
6785 5274 1
5322 2454 2
3138 4270 1
905 5536 1
5985 678 1
5287 5529 2
5322 5835 1
2454 5008 1
4701 8128 2
6785 6394 1
8128 7206 1
5274 2639 1
905 9176 2
2454 1398 1
639 700 2
5529 6052 1
6394 216...

output:

YES
3 2 0 1 0 2 0 1 3 2 -1 0 -1 1 2 1 1 1 1 0 0 0 2 -1 1 1 2 1 0 1 -1 2 1 1 2 0 1 2 0 0 -1 2 4 -2 0 1 2 0 2 1 1 1 1 1 2 1 0 1 1 2 1 1 1 -1 0 -2 3 0 1 2 0 2 -1 0 0 1 1 2 3 1 2 1 1 1 -1 3 0 0 1 1 0 1 2 1 1 2 1 3 1 0 1 -1 0 2 1 0 1 0 0 1 2 2 2 1 2 1 2 0 -2 0 1 1 1 1 1 -1 3 0 0 0 1 1 0 0 1 -1 2 0 2 1 3 ...

result:

ok answer = YES

Test #58:

score: 24
Accepted
time: 0ms
memory: 4380kb

input:

9000 8997
23 909 1
909 297 2
297 125 2
125 856 2
297 788 2
297 699 2
909 240 2
788 372 1
297 253 1
372 169 1
372 583 2
169 333 1
297 35 2
333 218 1
856 264 1
699 345 2
909 113 2
125 689 2
372 551 2
113 156 1
583 809 1
699 789 1
23 431 2
35 773 1
297 308 1
35 412 2
789 842 1
372 446 1
372 647 1
297 2...

output:

YES
2 1 2 0 0 1 2 0 -1 1 2 -1 1 -1 2 0 3 2 -1 1 1 -1 0 2 2 1 1 2 2 0 -1 3 -1 2 1 2 3 -1 0 3 0 2 2 0 1 2 1 2 3 0 1 1 0 3 2 1 0 0 1 -2 0 0 2 0 0 1 0 2 1 0 0 0 1 0 2 -1 -1 0 3 1 4 0 -1 2 1 1 2 0 0 3 2 0 0 0 1 1 0 -1 1 0 0 -1 3 -2 3 1 0 3 -1 1 2 0 1 1 0 0 2 1 2 0 1 1 -1 0 1 2 -2 1 1 1 2 1 0 1 2 3 0 0 1 ...

result:

ok answer = YES

Test #59:

score: 24
Accepted
time: 2ms
memory: 4508kb

input:

9000 9000
23 909 1
909 297 2
297 125 2
125 856 2
297 788 2
297 699 2
909 240 2
788 372 1
297 253 1
372 169 1
372 583 2
169 333 1
297 35 2
333 218 1
856 264 1
699 345 2
909 113 2
125 689 2
8765 8765 1
372 551 2
113 156 1
583 809 1
699 789 1
23 431 2
35 773 1
297 308 1
35 412 2
789 842 1
372 446 1
372...

output:

YES
3 2 3 1 1 2 3 1 0 0 1 -2 2 -2 3 1 2 3 0 0 2 -2 -1 1 1 0 2 3 3 -1 0 4 -2 1 2 3 4 -2 1 2 1 1 3 -1 0 3 0 3 4 -1 2 0 1 4 3 0 1 -1 2 -1 -1 1 1 1 1 2 -1 3 2 1 -1 1 2 1 3 0 0 -1 4 2 5 1 -2 1 2 0 1 -1 -1 4 1 -1 1 -1 0 2 -1 0 0 -1 1 -2 4 -1 2 2 -1 2 -2 2 3 1 0 0 -1 1 1 2 1 1 2 2 0 -1 2 3 -1 2 2 2 3 0 -1 ...

result:

ok answer = YES

Test #60:

score: 24
Accepted
time: 4ms
memory: 4432kb

input:

10000 9993
5747 266 1
266 9872 1
5747 8144 1
9872 2774 2
9872 1928 1
2774 832 2
832 1722 1
8144 6572 1
1722 2037 2
266 9295 2
1928 7512 2
9872 2290 1
8144 7191 2
7634 1399 2
7634 8450 2
8450 1114 2
7634 1656 2
8144 210 1
5747 7076 1
266 8302 1
7512 5384 2
5747 8424 1
1928 3256 1
1114 3796 2
2774 669...

output:

YES
1 -2 0 1 0 1 2 -1 2 2 3 2 -4 3 -1 1 1 3 0 0 1 2 1 2 4 -1 1 2 1 3 0 -1 6 1 0 1 1 1 2 0 0 1 0 0 -2 2 1 1 -2 1 -1 2 1 -1 0 1 0 0 2 1 2 2 3 2 3 0 -4 0 2 3 1 1 1 2 4 0 2 0 1 4 -2 0 2 -2 0 0 -1 1 3 2 0 0 3 1 -1 2 -1 1 4 1 3 -1 -3 -1 2 1 -1 3 2 2 3 -2 1 0 0 -1 5 1 2 1 -1 -1 4 0 0 1 1 1 0 2 0 2 1 -2 -2 ...

result:

ok answer = YES

Test #61:

score: 24
Accepted
time: 0ms
memory: 4436kb

input:

5000 5000
1537 2983 1
2983 1590 2
1590 1547 1
1547 4457 1
1547 1007 2
1590 3606 1
1590 601 1
601 1756 1
3606 3519 2
1590 1749 2
3606 2919 2
3519 3909 1
3606 1502 2
2983 28 1
601 3149 1
3519 1513 1
601 1811 2
1547 2834 2
1547 4836 1
1547 2118 2
3519 1002 1
28 2431 1
1547 4352 2
3909 2819 1
1811 4232 ...

output:

YES
3 0 -3 5 0 4 0 -1 3 -1 5 2 2 0 1 -4 1 5 4 -1 -3 0 1 -1 2 0 3 -2 2 0 -2 0 3 0 3 0 2 2 2 3 -2 -1 -1 -2 0 -3 1 1 -2 1 0 3 3 1 3 1 0 -1 2 -2 -3 0 2 2 -4 3 3 -1 1 -5 2 -2 1 3 2 0 2 0 -3 1 -2 1 1 -1 -1 3 2 3 2 0 1 4 1 0 2 1 0 -3 2 -1 1 0 -3 3 2 3 2 2 1 2 5 -3 0 -1 3 -1 2 2 3 4 3 -3 3 0 3 -3 3 1 1 0 -1...

result:

ok answer = YES

Test #62:

score: 24
Accepted
time: 31ms
memory: 8596kb

input:

7779 200000
5647 4480 1
3952 7125 2
4078 2641 1
4841 2183 1
5770 5533 2
6599 6593 2
4004 3876 1
3019 2571 2
133 3081 1
3894 6067 1
120 4973 2
6371 5265 1
302 7166 2
502 6467 2
5490 1674 2
4164 7719 1
6390 3076 1
156 6289 1
384 6397 2
5925 2507 2
5719 5489 2
5735 4718 1
1993 7127 2
2951 1924 2
296 80...

output:

NO

result:

ok answer = NO

Test #63:

score: 24
Accepted
time: 37ms
memory: 9604kb

input:

7779 200000
5647 4480 2
3952 7125 2
4078 2641 2
4841 2183 2
5770 5533 2
6599 6593 2
4004 3876 2
3019 2571 2
133 3081 2
3894 6067 2
120 4973 2
6371 5265 2
302 7166 2
502 6467 2
5490 1674 2
4164 7719 2
6390 3076 2
156 6289 2
384 6397 2
5925 2507 2
5719 5489 2
5735 4718 2
1993 7127 2
2951 1924 2
296 80...

output:

YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok answer = YES

Test #64:

score: 24
Accepted
time: 29ms
memory: 9736kb

input:

7783 200000
5647 4480 2
3952 7125 2
4078 2641 2
4841 2183 2
5770 5533 2
6599 6593 2
4004 3876 2
3019 2571 2
133 3081 2
3894 6067 2
120 4973 2
6371 5265 2
302 7166 2
502 6467 2
5490 1674 2
4164 7719 2
6390 3076 2
156 6289 2
384 6397 2
5925 2507 2
5719 5489 2
5735 4718 2
1993 7127 2
2951 1924 2
296 80...

output:

NO

result:

ok answer = NO

Test #65:

score: 24
Accepted
time: 38ms
memory: 9716kb

input:

7783 200000
5647 4480 2
3952 7125 2
4078 2641 2
4841 2183 2
5770 5533 2
6599 6593 2
4004 3876 2
3019 2571 2
133 3081 2
3894 6067 2
120 4973 2
6371 5265 2
302 7166 2
502 6467 2
5490 1674 2
4164 7719 2
6390 3076 2
156 6289 2
384 6397 2
5925 2507 2
5719 5489 2
5735 4718 2
1993 7127 2
2951 1924 2
296 80...

output:

YES
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok answer = YES

Test #66:

score: 24
Accepted
time: 1ms
memory: 4000kb

input:

2000 1998
1673 1643 1
1643 1877 1
1643 1622 2
1643 1533 1
1643 1111 2
1533 1056 2
1533 1394 1
1622 1955 2
1056 1703 2
1394 1295 1
1703 1973 1
1295 1696 2
1696 1496 1
1394 1027 2
1622 1086 1
1973 1714 2
1533 1990 2
1990 1840 2
1622 1833 2
1673 1870 1
1840 1783 1
1295 1500 2
1973 1150 1
1877 1769 2
12...

output:

YES
2 1 1 2 1 2 0 -1 0 -1 1 -1 0 2 2 0 2 1 0 2 0 -1 0 -1 1 0 1 1 0 0 1 1 1 -1 0 1 1 0 0 1 1 1 2 4 0 -1 1 0 0 1 1 1 1 1 0 2 1 -2 0 2 1 0 0 0 -1 2 0 1 1 1 0 1 0 1 3 2 0 0 1 1 0 0 1 1 2 0 0 1 2 1 4 2 3 1 2 0 0 2 0 0 1 1 0 1 1 0 0 -1 0 1 0 2 0 2 1 0 1 1 1 1 0 0 2 0 0 0 0 1 2 0 3 2 0 1 1 0 0 1 1 0 0 2 1 ...

result:

ok answer = YES

Subtask #5:

score: 42
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #67:

score: 42
Accepted
time: 37ms
memory: 23664kb

input:

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

output:

YES
-27 29 -28 30 -28 29 -27 29 -28 30 -29 30 -29 31 -29 31 -29 31 -30 32 -31 33 -32 33 -31 33 -32 34 -32 33 -31 32 -31 33 -32 34 -33 35 -34 36 -34 35 -34 36 -34 36 -34 36 -34 36 -35 37 -36 38 -36 37 -36 37 -35 36 -35 37 -36 38 -36 38 -37 38 -36 38 -36 37 -35 37 -35 36 -35 36 -34 36 -34 35 -33 34 -3...

result:

ok answer = YES

Test #68:

score: 42
Accepted
time: 37ms
memory: 23824kb

input:

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

output:

YES
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...

result:

ok answer = YES

Test #69:

score: 42
Accepted
time: 40ms
memory: 23448kb

input:

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

output:

YES
1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 ...

result:

ok answer = YES

Test #70:

score: 42
Accepted
time: 59ms
memory: 26600kb

input:

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

output:

YES
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 ...

result:

ok answer = YES

Test #71:

score: 42
Accepted
time: 42ms
memory: 23468kb

input:

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

output:

YES
1.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 1.5 0.5 0.5 0.5 1.5 -0.5 ...

result:

ok answer = YES

Test #72:

score: 42
Accepted
time: 51ms
memory: 11828kb

input:

100000 99999
46010 73517 1
46010 71237 1
73517 84882 1
46010 88029 2
71237 24280 2
46010 65570 2
73517 72433 1
46010 89979 2
73517 72865 2
84882 73930 1
71237 8378 1
72865 57310 2
24280 29910 2
65570 12790 1
71237 35140 2
65570 26639 2
35140 63574 1
84882 36791 2
24280 26534 1
57310 88935 1
88029 71...

output:

YES
-4 0 -1 1 -1 -3 1 1 0 0 0 1 2 2 0 3 2 1 1 0 0 2 0 2 1 0 1 0 0 3 1 1 2 3 1 1 2 2 -1 -1 0 3 5 2 -1 -2 1 2 0 1 0 1 2 0 1 1 1 1 0 2 2 -2 4 1 2 -3 -3 0 0 2 -1 -2 1 0 2 1 2 0 2 1 1 1 1 -2 1 1 0 1 3 1 1 0 -1 1 0 1 2 -3 3 3 1 0 1 1 0 -1 0 1 3 2 2 -2 2 1 0 2 -1 1 2 1 -1 0 0 0 -2 2 3 3 2 2 2 2 0 -1 0 0 0 ...

result:

ok answer = YES

Test #73:

score: 42
Accepted
time: 43ms
memory: 11708kb

input:

100000 100000
99997 99996 2
46010 73517 1
46010 71237 1
73517 84882 1
46010 88029 2
71237 24280 2
46010 65570 2
73517 72433 1
46010 89979 2
73517 72865 2
84882 73930 1
71237 8378 1
72865 57310 2
24280 29910 2
65570 12790 1
71237 35140 2
65570 26639 2
35140 63574 1
84882 36791 2
24280 26534 1
57310 8...

output:

YES
-4 0 -1 1 -1 -3 1 1 0 0 0 1 2 2 0 3 2 1 1 0 0 2 0 2 1 0 1 0 0 3 1 1 2 3 1 1 2 2 -1 -1 0 3 5 2 -1 -2 1 2 0 1 0 1 2 0 1 1 1 1 0 2 2 -2 4 1 2 -3 -3 0 0 2 -1 -2 1 0 2 1 2 0 2 1 1 1 1 -2 1 1 0 1 3 1 1 0 -1 1 0 1 2 -3 3 3 1 0 1 1 0 -1 0 1 3 2 2 -2 2 1 0 2 -1 1 2 1 -1 0 0 0 -2 2 3 3 2 2 2 2 0 -1 0 0 0 ...

result:

ok answer = YES

Test #74:

score: 42
Accepted
time: 28ms
memory: 14872kb

input:

65432 65432
53092 42562 2
61422 3056 1
22311 61422 1
48701 22311 1
30946 48701 2
63805 30946 2
24885 63805 2
30129 24885 1
12730 30129 2
52825 12730 1
33919 52825 1
62776 33919 2
42820 62776 1
41997 42820 1
50057 41997 2
31136 50057 2
35935 31136 1
39897 35935 1
11238 39897 1
13207 11238 2
8162 1320...

output:

YES
-43 2 -40 73 83 -68 42 -32 -74 -67 -71 47 -48 43 56 1 21 15 37 -12 -7 -85 65 74 -32 -21 -40 -85 -24 -67 -18 62 -59 -44 15 42 -69 -32 71 -65 67 26 22 78 -71 -66 1 -19 26 75 -62 -51 2 31 44 21 74 -60 -92 88 60 71 -69 42 36 -50 16 -46 55 42 -65 -29 73 -74 46 -75 -41 42 5 59 54 -44 0 21 54 63 -24 -4...

result:

ok answer = YES

Test #75:

score: 42
Accepted
time: 11ms
memory: 11272kb

input:

65432 65432
53092 211 1
27132 53092 2
42562 27132 1
211 42562 2
17771 211 2
3056 17771 2
61422 3056 2
22311 61422 1
48701 22311 2
30946 48701 2
63805 30946 2
24885 63805 1
30129 24885 2
12730 30129 2
52825 12730 1
33919 52825 2
62776 33919 1
42820 62776 2
41997 42820 1
50057 41997 2
31136 50057 2
35...

output:

NO

result:

ok answer = NO

Test #76:

score: 42
Accepted
time: 5ms
memory: 4532kb

input:

12003 12002
9377 4878 2
9377 3429 1
9377 7810 2
7810 5657 1
5657 5042 2
5042 939 1
7810 11128 1
939 2499 2
4878 7761 2
9377 11413 1
2499 2521 1
11128 1993 2
7810 3844 2
5042 5302 2
1993 4247 1
939 10401 2
3429 6319 2
1993 1100 1
2521 3282 1
939 10812 1
1100 2401 2
1993 2995 1
3429 9756 1
4247 10652 ...

output:

YES
-2 0 2 -1 0 0 0 -1 0 3 2 1 0 -1 0 0 0 0 0 -1 1 1 0 1 1 1 0 -2 0 -1 0 0 -1 1 0 -1 -1 0 -2 3 3 0 0 0 -3 0 2 -2 1 -4 1 -2 -1 2 2 -1 1 0 0 -2 2 3 -2 1 0 3 -1 3 3 -1 -1 -1 -2 -1 3 1 -2 2 2 -1 2 2 1 1 0 -1 0 2 3 -1 1 0 -1 1 1 -1 1 0 3 4 2 -2 0 0 2 1 1 2 -1 -1 2 0 2 0 1 0 3 4 4 2 2 0 1 3 -1 -1 3 -4 3 1...

result:

ok answer = YES

Test #77:

score: 42
Accepted
time: 7ms
memory: 5572kb

input:

24578 24577
23603 4344 2
4344 19532 1
23603 3246 1
3246 1886 2
19532 20210 2
4344 21587 1
20210 2078 1
1886 3647 1
2078 17988 1
2078 20740 2
20740 19106 2
21587 13831 2
13831 12196 1
17988 1925 2
13831 21149 2
23603 16767 1
20210 7996 1
23603 20056 2
20740 23098 2
1925 929 1
20740 4712 2
4344 9432 1...

output:

YES
4 2 4 2 -1 0 -2 0 0 0 0 2 -2 1 1 2 0 1 0 2 1 4 1 0 -1 0 2 2 -1 0 2 1 0 1 -1 0 2 1 -2 3 -1 1 1 -2 3 -1 1 0 1 1 1 1 2 2 2 3 2 0 -2 1 1 2 0 3 2 2 0 2 0 -1 -1 -1 1 0 1 -3 -1 4 2 0 2 2 -1 5 1 2 2 3 -1 4 5 2 0 3 -1 3 3 0 2 2 1 3 2 0 1 2 0 -1 2 2 0 -1 0 1 4 -1 2 2 -2 2 1 0 1 2 2 -1 -1 1 0 2 1 4 1 4 -1 ...

result:

ok answer = YES

Test #78:

score: 42
Accepted
time: 20ms
memory: 7016kb

input:

42875 42874
20761 12008 1
20761 1944 1
1944 39972 2
1944 22755 1
12008 20740 1
39972 4604 2
4604 35707 2
4604 4652 2
1944 25001 1
4652 22253 1
4604 21472 1
22253 27279 1
1944 10476 1
4604 39701 2
1944 12021 2
22755 30164 1
4652 39993 1
22755 15109 2
30164 15391 1
27279 227 2
4652 32595 2
4604 20263 ...

output:

YES
-1 2 2 -1 0 2 3 1 3 1 -1 -1 0 0 1 1 4 0 1 3 0 0 1 1 0 1 -1 -1 1 -1 2 1 -1 4 2 0 2 -1 -2 2 1 -1 -1 3 0 -1 2 2 1 -1 2 -2 -1 0 1 -1 -3 2 1 1 0 2 1 0 1 2 1 1 2 2 0 1 2 -1 1 2 -2 0 0 1 -1 2 2 0 -1 2 -1 2 2 0 -2 1 1 1 3 2 2 2 1 2 -1 1 -2 0 2 0 2 -1 0 -2 1 1 1 1 -2 1 3 1 1 0 2 0 1 -1 -1 2 1 2 1 1 2 3 3...

result:

ok answer = YES

Test #79:

score: 42
Accepted
time: 38ms
memory: 10416kb

input:

85112 85111
46719 28242 2
46719 12064 1
46719 41742 2
12064 12832 1
12064 62011 2
46719 34580 1
34580 54175 1
54175 22379 1
28242 70331 2
62011 29977 1
34580 63400 2
34580 60096 2
34580 5803 2
70331 78021 1
12064 58458 2
54175 83087 1
58458 55439 1
12832 84003 1
60096 55624 2
41742 43610 1
12064 113...

output:

YES
3 0 1 0 2 0 2 0 3 1 2 0 1 2 3 2 0 1 2 -1 0 0 0 3 2 1 1 0 2 3 0 0 1 -2 2 2 -1 2 -1 -3 4 2 0 2 3 3 1 0 2 -1 -1 -1 0 -1 1 1 1 4 0 -2 1 1 -1 -3 1 1 4 0 2 0 0 0 -1 2 1 2 1 4 3 3 0 1 4 2 3 4 3 2 -2 0 -1 2 1 -4 4 1 1 -3 -3 3 -1 1 -2 0 -1 3 0 3 1 1 0 4 1 2 2 0 1 0 1 2 0 1 -1 1 2 4 0 0 1 0 4 0 -2 1 1 0 0...

result:

ok answer = YES

Test #80:

score: 42
Accepted
time: 37ms
memory: 15060kb

input:

65432 65432
53092 211 1
27132 53092 1
42562 27132 2
17771 211 2
3056 17771 1
61422 3056 1
22311 61422 2
48701 22311 1
30946 48701 1
63805 30946 2
24885 63805 2
30129 24885 2
12730 30129 2
52825 12730 1
33919 52825 2
62776 33919 1
42820 62776 1
41997 42820 2
50057 41997 2
31136 50057 1
35935 31136 2
...

output:

YES
-5 24 -91 23 -7 2 38 16 -11 -11 -40 12 -13 33 101 -16 30 -14 -3 34 -117 4 20 62 -110 13 -64 -9 -40 -37 -111 9 -51 -89 42 20 -43 -14 24 -30 10 24 28 -3 -24 -40 -17 -37 57 5 -53 -19 15 55 101 -1 62 -87 -1 -4 10 43 -5 49 -1 -90 -8 -103 78 107 -75 -89 92 -7 7 -3 1 13 30 9 64 -16 14 43 103 58 -27 -67...

result:

ok answer = YES

Test #81:

score: 42
Accepted
time: 22ms
memory: 17436kb

input:

100000 100002
56529 57156 2
57156 27549 1
27549 28230 1
28230 7926 1
7926 59289 2
59289 81233 2
81233 27658 1
27658 66317 2
66317 19168 1
19168 90255 1
90255 68781 1
68781 11095 2
11095 33131 2
33131 77761 2
77761 79637 1
79637 56882 1
56882 94204 1
94204 6106 2
6106 94523 1
94523 13040 1
13040 2098...

output:

NO

result:

ok answer = NO

Test #82:

score: 42
Accepted
time: 46ms
memory: 22436kb

input:

100000 100002
56529 57156 1
57156 27549 2
27549 28230 1
28230 7926 1
7926 59289 2
59289 81233 2
81233 27658 1
27658 66317 2
66317 19168 2
19168 90255 2
41925 34710 1
34710 99751 1
99751 15971 2
15971 32697 1
32697 4582 1
4582 99335 2
99335 34376 1
34376 85730 2
85730 18223 1
18223 50289 1
50289 2254...

output:

YES
23.5 74.5 -28.5 18.5 35.5 17.5 0.5 24.5 -26.5 -30.5 62.5 23.5 -18.5 54.5 19.5 19.5 4.5 -5.5 -52.5 47.5 -21.5 12.5 68.5 39.5 -10.5 -28.5 75.5 18.5 -22.5 40.5 51.5 -20.5 -48.5 46.5 38.5 -14.5 -78.5 24.5 -61.5 20.5 35.5 24.5 26.5 -4.5 -18.5 -28.5 49.5 -62.5 -50.5 17.5 40.5 37.5 -12.5 -30.5 13.5 -17...

result:

ok answer = YES

Test #83:

score: 42
Accepted
time: 54ms
memory: 23548kb

input:

99999 99999
80080 1 1
87783 2 2
61570 3 1
63587 4 1
5545 5 1
88849 6 1
82128 7 2
4982 8 2
36645 9 2
96642 10 2
26221 11 2
50868 12 2
1286 13 1
57151 14 2
58364 15 2
9970 16 1
76120 17 1
7154 18 2
27445 19 2
61712 20 2
76980 21 1
36744 22 2
62047 23 1
73412 24 2
55563 25 2
16089 26 1
38539 27 2
16189...

output:

YES
-11 120 -66 -119 82 -99 -112 -117 -94 -81 130 -113 -79 121 51 -99 1 -28 -112 91 -102 -106 49 87 -100 -122 58 72 -87 84 124 116 -33 89 95 95 -55 65 -106 126 54 -119 -117 -7 -111 -103 101 -89 -93 116 55 75 -21 -146 123 114 -88 70 -16 -70 -109 130 -76 -99 -108 20 -118 -113 -76 87 26 -81 101 -7 -11 ...

result:

ok answer = YES

Test #84:

score: 42
Accepted
time: 59ms
memory: 23688kb

input:

100000 100000
80080 1 1
87783 2 2
61570 3 1
63587 4 1
5545 5 1
88849 6 1
82128 7 2
4982 8 2
36645 9 2
96642 10 2
26221 11 2
50868 12 2
1286 13 1
57151 14 2
58364 15 2
9970 16 1
76120 17 1
7154 18 2
27445 19 2
61712 20 2
76980 21 1
36744 22 2
62047 23 1
73412 24 2
55563 25 2
16089 26 1
38539 27 2
161...

output:

YES
82 27 27 -26 -11 -6 -19 -24 -1 12 37 -20 14 28 -42 -6 -92 65 -19 -2 -9 -13 -44 -6 -7 -29 -35 -21 6 -9 31 23 60 -4 2 2 38 -28 -13 33 -39 -26 -24 86 -18 -10 8 4 0 23 -38 -18 72 -53 30 21 5 -23 77 23 -16 37 17 -6 -15 -73 -25 -20 17 -6 -67 12 8 86 82 -27 15 -75 51 61 -16 28 -20 -15 1 -24 -27 -27 -32...

result:

ok answer = YES

Test #85:

score: 42
Accepted
time: 43ms
memory: 23684kb

input:

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

output:

YES
5 -3 4 -2 4 -3 5 -3 4 -2 3 -2 3 -1 3 -1 3 -1 2 0 1 1 0 1 1 1 0 2 0 1 1 0 1 1 0 2 -1 3 -2 4 -2 3 -2 4 -2 4 -2 4 -2 4 -3 5 -4 6 -4 5 -4 5 -3 4 -3 5 -4 6 -4 6 -5 6 -4 6 -4 5 -3 5 -3 4 -3 4 -2 4 -2 3 -1 2 0 1 1 0 2 -1 2 0 1 1 0 1 1 1 1 1 1 1 1 0 1 1 0 2 -1 2 0 1 0 1 1 1 1 1 0 1 0 2 0 1 1 1 0 1 1 1 1...

result:

ok answer = YES

Test #86:

score: 42
Accepted
time: 39ms
memory: 23552kb

input:

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

output:

YES
-8 10 -9 11 -9 10 -8 10 -9 11 -10 11 -10 12 -10 12 -10 12 -11 13 -12 14 -13 14 -12 14 -13 15 -13 14 -12 13 -12 14 -13 15 -14 16 -15 17 -15 16 -15 17 -15 17 -15 17 -15 17 -16 18 -17 19 -17 18 -17 18 -16 17 -16 18 -17 19 -17 19 -18 19 -17 19 -17 18 -16 18 -16 17 -16 17 -15 17 -15 16 -14 15 -13 14 ...

result:

ok answer = YES

Test #87:

score: 42
Accepted
time: 25ms
memory: 14096kb

input:

100000 100000
56529 22247 1
57156 76873 2
27549 74689 2
28230 20136 2
7926 21765 2
59289 44309 1
81233 73800 1
27658 4140 1
66317 96173 2
19168 41912 1
90255 85691 2
68781 92265 1
11095 74329 1
33131 54296 1
77761 12488 2
79637 64790 2
56882 15088 2
94204 70816 1
6106 72365 2
94523 66217 2
13040 687...

output:

NO

result:

ok answer = NO

Test #88:

score: 42
Accepted
time: 61ms
memory: 16168kb

input:

100000 99993
56529 22247 1
57156 76873 2
27549 74689 2
28230 20136 2
7926 21765 2
59289 44309 1
81233 73800 1
27658 4140 1
66317 96173 2
19168 41912 1
90255 85691 2
68781 92265 1
11095 74329 1
33131 54296 1
77761 12488 2
79637 64790 2
56882 15088 2
94204 70816 1
6106 72365 2
94523 66217 2
13040 6874...

output:

YES
63.5 -37.5 -3 -50.5 -28.5 49.5 60.5 59.5 34.5 55.5 61.5 27.5 -54.5 23.5 13.5 65.5 -46.5 7 -34.5 72.5 15.5 -28.5 47.5 97.5 3.5 -3.5 28 48.5 98.5 -7 53.5 29 92.5 58.5 57.5 61.5 53.5 -47.5 -31 9 -51.5 49.5 -62.5 9 54.5 32.5 61.5 33.5 20.5 -55.5 63.5 -36.5 -49.5 42.5 -5.5 -56.5 36.5 -30.5 -53.5 -48....

result:

ok answer = YES

Test #89:

score: 42
Accepted
time: 53ms
memory: 10460kb

input:

99995 99995
78058 31441 1
31441 51023 1
51023 74459 1
74459 23055 2
23055 78058 1
16585 7554 2
7554 24128 1
24128 176 1
176 25997 1
25997 16585 1
77491 21901 1
21901 54642 1
54642 8060 1
8060 16094 2
16094 77491 1
33709 96277 2
96277 57388 1
57388 15904 2
15904 5337 1
5337 33709 2
86568 60740 1
6074...

output:

YES
1.5 0.5 0.5 1 0.5 0.5 1 1.5 -0.5 1.5 0.5 1 0.5 1 1 1.5 0.5 0.5 0.5 1.5 1 0 2 1.5 0.5 0.5 0.5 1 0.5 0 1 0 0 0.5 1 1 1 1 1.5 1.5 1.5 1.5 0.5 0.5 1 0.5 0.5 1 0 1 0 0.5 1.5 1.5 0.5 0 0.5 1.5 0.5 1.5 0.5 0 1 0.5 0.5 1.5 0 1 0.5 1.5 0 0.5 1 0.5 0 0.5 0.5 0.5 1.5 0.5 1.5 1 1.5 0.5 0.5 0 1 1 0 0.5 1 1 0...

result:

ok answer = YES

Test #90:

score: 42
Accepted
time: 46ms
memory: 10532kb

input:

99995 99993
78058 31441 1
31441 51023 1
51023 74459 1
23055 78058 1
16585 7554 1
7554 24128 2
24128 176 2
176 25997 2
25997 16585 2
77491 21901 2
21901 54642 2
54642 8060 1
8060 16094 1
16094 77491 2
33709 96277 1
96277 57388 2
57388 15904 1
15904 5337 1
5337 33709 1
86568 60740 1
60740 48584 2
4858...

output:

YES
1 0 1 0.5 1 0.5 0.5 1 0.5 0.5 2 -0.5 1 0.5 1 2 0.5 2 1.5 1.5 0.5 1.5 1 2 0.5 1.5 1.5 0.5 0 1 1 0.5 0.5 0 0.5 1.5 0.5 1 2 1 1 0.5 1 1 0 1 0.5 0.5 0.5 -0.5 2 0.5 -0.5 1.5 1.5 1.5 1.5 2 -0.5 0 0.5 0 1.5 1 0.5 0.5 1 0.5 1.5 1 1 1.5 1.5 0.5 0.5 1.5 1 0.5 0.5 1 1 0 1.5 0.5 0.5 0.5 1 0 0.5 0.5 -0.5 0.5...

result:

ok answer = YES

Test #91:

score: 42
Accepted
time: 53ms
memory: 10424kb

input:

99995 99991
1 20142 2
2 6002 2
3 82095 1
4 60745 2
5 90105 1
6 64049 2
7 23071 2
8 71332 2
9 70369 1
10 32019 1
11 24290 2
12 11191 2
13 44942 2
14 30995 2
15 97415 2
16 73376 1
17 87011 2
18 29686 2
19 44867 2
20 84255 2
21 98945 2
22 23539 2
23 62458 2
24 43019 1
25 52259 1
26 33469 1
27 74492 2
2...

output:

YES
0.5 1 1.5 1 0 1.5 0.5 1 1 0.5 1.5 1.5 1 0.5 1.5 -0.5 1.5 1.5 2 1.5 1 1.5 2 -0.5 0.5 1 0.5 1 0.5 0 1 0.5 0.5 1.5 1 1 1 1 1.5 0.5 0.5 1.5 0.5 0.5 1 1 0.5 1 1 -0.5 0 1.5 0 1 1 1.5 -0.5 0.5 1.5 -0.5 1 1 0.5 0 0.5 1 0.5 1 1 0 0.5 1.5 0.5 0 1 0.5 0.5 1.5 1 1 0 0.5 1 1 1 1.5 1 1.5 0.5 0.5 1.5 1.5 0.5 0...

result:

ok answer = YES

Test #92:

score: 42
Accepted
time: 25ms
memory: 7520kb

input:

50000 50000
24269 39765 1
24269 22722 2
24269 43371 2
24269 38058 2
22722 32105 1
39765 27584 2
32105 35746 2
35746 17760 2
22722 48085 1
35746 12276 2
39765 24686 2
48085 41335 2
27584 1222 1
12276 24573 1
32105 24867 1
1222 40284 2
39765 15861 1
40284 25984 1
35746 16928 1
32105 18705 2
38058 2007...

output:

YES
-2.5 -0.5 0.5 0.5 2.5 0.5 0.5 0.5 3.5 2.5 -1.5 -2.5 2.5 1.5 1.5 0.5 4.5 -1.5 0.5 1.5 0.5 -2.5 1.5 3.5 2.5 2.5 -0.5 1.5 -1.5 -2.5 2.5 2.5 0.5 4.5 -0.5 1.5 -0.5 3.5 1.5 -0.5 -1.5 0.5 4.5 0.5 4.5 -0.5 -2.5 1.5 3.5 -1.5 2.5 -1.5 -1.5 2.5 1.5 1.5 2.5 2.5 -0.5 0.5 -3.5 0.5 -0.5 -0.5 0.5 -1.5 -1.5 1.5 ...

result:

ok answer = YES

Test #93:

score: 42
Accepted
time: 23ms
memory: 7548kb

input:

50000 50000
12607 45763 2
45763 7230 1
7230 4820 2
12607 46801 2
7230 12296 1
4820 11994 2
4820 11184 1
12296 2577 2
7230 15318 1
2577 41681 2
7230 42625 2
2577 40230 2
45763 22991 1
40230 37009 2
22991 47320 1
11994 5954 2
40230 12091 1
46801 12015 2
15318 15204 2
47320 10758 1
37009 41103 2
15204 ...

output:

YES
1 1 1 2 4 0 2 0 -1 3 3 1 -1 1 2 1 0 -1 1 1 3 1 0 -2 0 -2 0 0 1 1 1 1 1 0 3 -1 -1 2 3 0 2 1 0 -1 0 -1 -2 3 0 1 -2 -1 0 1 0 0 5 1 2 1 2 1 1 1 -1 -3 5 1 0 1 5 3 0 3 0 1 -1 0 2 1 0 4 -2 1 3 2 3 2 2 2 1 2 0 0 1 0 0 1 2 0 0 1 3 1 -1 1 3 0 5 -2 4 -1 2 0 -1 2 4 2 2 0 -3 0 2 1 0 -1 0 2 -2 3 -1 -3 3 0 0 1...

result:

ok answer = YES

Test #94:

score: 42
Accepted
time: 33ms
memory: 23512kb

input:

100000 100000
80080 1 1
87783 2 2
61570 3 1
63587 4 1
5545 5 1
88849 6 1
82128 7 2
4982 8 2
36645 9 2
96642 10 2
26221 11 2
50868 12 2
1286 13 1
57151 14 2
58364 15 2
9970 16 1
76120 17 1
7154 18 2
27445 19 2
61712 20 2
76980 21 1
36744 22 2
62047 23 1
73412 24 2
55563 25 2
16089 26 1
38539 27 2
161...

output:

NO

result:

ok answer = NO

Test #95:

score: 42
Accepted
time: 24ms
memory: 10264kb

input:

99995 99993
1 20142 2
2 6002 2
3 82095 1
4 60745 2
5 90105 1
6 64049 2
7 23071 2
8 71332 2
9 70369 1
10 32019 1
11 24290 2
12 11191 2
13 44942 2
14 30995 2
15 97415 2
16 73376 1
17 87011 2
18 29686 2
19 44867 2
20 84255 2
21 98945 2
22 23539 2
23 62458 2
24 43019 1
25 52259 1
26 33469 1
27 74492 2
2...

output:

NO

result:

ok answer = NO

Test #96:

score: 42
Accepted
time: 89ms
memory: 21676kb

input:

99997 200000
13425 90048 1
81741 46019 1
35193 33756 1
4840 2182 1
13548 28869 1
37714 45487 1
89572 73886 1
3018 64802 1
132 73091 1
97241 68298 1
62351 36088 1
21928 59717 1
8080 61618 1
62733 53140 1
83279 32789 1
97511 38834 1
29726 80865 1
31271 84078 1
15941 45291 1
52598 80296 1
5718 75499 1
...

output:

YES
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 ...

result:

ok answer = YES

Test #97:

score: 42
Accepted
time: 15ms
memory: 23228kb

input:

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

output:

NO

result:

ok answer = NO