QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#523377#5705. Graphbachbeo2007100 ✓88ms27564kbC++231.8kb2024-08-18 09:48:322024-08-18 09:48:32

Judging History

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

  • [2024-08-18 09:48:32]
  • 评测
  • 测评结果:100
  • 用时:88ms
  • 内存:27564kb
  • [2024-08-18 09:48:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

int n,m,a[maxn],b[maxn];
vector<pii> edge[maxn];
bool vis[maxn];
vector<int> cc;
double res[maxn];

void dfs(int u){
    vis[u]=true;
    cc.push_back(u);
    for(auto [v,w]:edge[u]){
        if(vis[v]) continue;
        a[v]=-a[u],b[v]=w-b[u];
        dfs(v);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int u,v,w;cin >> u >> v >> w;
        edge[u].push_back({v,w});
        edge[v].push_back({u,w});
    }
    bool check=true;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cc.clear();
            a[i]=1;dfs(i);

            bool ok=false;
            int cA=-1,cB=-1;
            for(int u:cc) for(auto [v,w]:edge[u]){
                int A=a[u]+a[v],B=b[u]+b[v];
                if(A==0){
                    if(B!=w) check=false;
                }
                else{
                    B=w-B;
                    if(!ok) cA=A,cB=B,ok=true;
                    else if(cA*B!=cB*A) check=false;
                }
            }
            if(!check){
                cout << "NO\n";
                return 0;
            }
            double x;
            if(ok) x=(double)cB/cA;
            else{
                vector<int> val;
                for(int u:cc) val.push_back(-a[u]*b[u]);
                sort(val.begin(),val.end());
                x=val[(int)val.size()/2];
            }
            for(int u:cc) res[u]=a[u]*x+b[u];
        }
    }
    cout << "YES\n";
    for(int i=1;i<=n;i++) cout << setprecision(6) << fixed << res[i] << ' ';
    cout << '\n';
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 5996kb

input:

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

output:

YES
0.500000 0.500000 1.500000 -0.500000 

result:

ok answer = YES

Test #2:

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

input:

2 1
1 2 1

output:

YES
1.000000 0.000000 

result:

ok answer = YES

Test #3:

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

input:

3 2
1 2 2
2 3 2

output:

YES
0.000000 2.000000 0.000000 

result:

ok answer = YES

Test #4:

score: 5
Accepted
time: 1ms
memory: 5936kb

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: 1ms
memory: 5904kb

input:

5 2
1 2 1
5 3 2

output:

YES
1.000000 0.000000 2.000000 0.000000 0.000000 

result:

ok answer = YES

Test #6:

score: 5
Accepted
time: 1ms
memory: 3860kb

input:

3 2
2 1 2
3 2 1

output:

YES
1.000000 1.000000 0.000000 

result:

ok answer = YES

Test #7:

score: 5
Accepted
time: 1ms
memory: 3856kb

input:

3 3
1 2 1
1 3 1
3 2 1

output:

YES
0.500000 0.500000 0.500000 

result:

ok answer = YES

Test #8:

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

input:

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

output:

YES
2.000000 0.000000 1.000000 0.000000 

result:

ok answer = YES

Test #9:

score: 5
Accepted
time: 1ms
memory: 3896kb

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: 1ms
memory: 5916kb

input:

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

output:

YES
1.500000 0.500000 0.500000 0.500000 

result:

ok answer = YES

Test #11:

score: 5
Accepted
time: 1ms
memory: 3860kb

input:

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

output:

YES
1.500000 0.500000 0.500000 0.500000 

result:

ok answer = YES

Test #12:

score: 5
Accepted
time: 1ms
memory: 5708kb

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: 1ms
memory: 5896kb

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.500000 0.500000 0.500000 0.500000 1.500000 

result:

ok answer = YES

Test #14:

score: 5
Accepted
time: 1ms
memory: 4084kb

input:

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

output:

YES
1.000000 0.000000 0.000000 1.000000 1.000000 

result:

ok answer = YES

Test #15:

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

input:

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

output:

YES
1.000000 0.000000 0.000000 1.000000 1.000000 

result:

ok answer = YES

Test #16:

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

input:

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

output:

YES
1.500000 0.500000 0.500000 0.500000 1.500000 

result:

ok answer = YES

Test #17:

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

input:

1 0

output:

YES
0.000000 

result:

ok answer = YES

Test #18:

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

input:

1 1
1 1 1

output:

YES
0.500000 

result:

ok answer = YES

Test #19:

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

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.000000 0.500000 1.500000 

result:

ok answer = YES

Test #20:

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

input:

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

output:

YES
1.500000 0.500000 0.500000 

result:

ok answer = YES

Test #21:

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

input:

2 2
1 2 2
2 1 2

output:

YES
2.000000 0.000000 

result:

ok answer = YES

Test #22:

score: 5
Accepted
time: 1ms
memory: 5648kb

input:

2 2
1 2 2
2 1 1

output:

NO

result:

ok answer = NO

Test #23:

score: 5
Accepted
time: 1ms
memory: 3636kb

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: 5960kb

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.000000 2.000000 1.000000 1.000000 2.000000 0.000000 1.000000 0.000000 0.000000 1.000000 -1.000000 -1.000000 1.000000 1.000000 2.000000 2.000000 2.000000 0.000000 2.000000 2.000000 1.000000 1.000000 2.000000 1.000000 0.000000 -1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 -1.00...

result:

ok answer = YES

Test #25:

score: 12
Accepted
time: 1ms
memory: 5924kb

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.000000 1.000000 -1.000000 2.000000 -1.000000 2.000000 1.000000 1.000000 2.000000 1.000000 1.000000 2.000000 -1.000000 0.000000 2.000000 2.000000 0.000000 2.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000 2.000000 2.000000 2.000000 2.000000 1.000000 0.000000 1.000000 1.000000 0.000...

result:

ok answer = YES

Test #26:

score: 12
Accepted
time: 1ms
memory: 3880kb

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.000000 1.000000 1.000000 -2.000000 1.000000 1.000000 1.000000 0.000000 2.000000 2.000000 0.000000 2.000000 0.000000 0.000000 1.000000 0.000000 0.000000 -1.000000 2.000000 1.000000 1.000000 1.000000 2.000000 1.000000 2.000000 0.000000 0.000000 1.000000 -1.000000 -1.000000 2.000000 1.000000 0.00...

result:

ok answer = YES

Test #27:

score: 12
Accepted
time: 1ms
memory: 5964kb

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.000000 2.000000 0.000000 -3.000000 0.000000 2.000000 2.000000 1.000000 3.000000 3.000000 -1.000000 3.000000 -1.000000 1.000000 2.000000 1.000000 1.000000 -2.000000 1.000000 2.000000 2.000000 0.000000 1.000000 0.000000 3.000000 1.000000 1.000000 0.000000 0.000000 -2.000000 1.000000 2.000000 1.0...

result:

ok answer = YES

Test #28:

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

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.000000 0.000000 0.000000 2.000000 0.000000 0.000000 2.000000 1.000000 1.000000 3.000000 0.000000 2.000000 -1.000000 2.000000 3.000000 3.000000 1.000000 0.000000 3.000000 0.000000 2.000000 2.000000 -1.000000 2.000000 1.000000 0.000000 1.000000 0.000000 2.000000 1.000000 3.000000 3.000000 -1.000...

result:

ok answer = YES

Test #29:

score: 12
Accepted
time: 1ms
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.000000 1.000000 0.000000 2.000000 1.000000 1.000000 2.000000 0.000000 0.000000 2.000000 1.000000 2.000000 0.000000 1.000000 2.000000 2.000000 0.000000 0.000000 2.000000 1.000000 2.000000 2.000000 0.000000 2.000000 0.000000 0.000000 2.000000 -1.000000 2.000000 1.000000 2.000000 2.000000 -1.0000...

result:

ok answer = YES

Test #30:

score: 12
Accepted
time: 1ms
memory: 3608kb

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: 1ms
memory: 4000kb

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.500000 2.000000 0.500000 0.000000 1.500000 1.000000 -0.500000 1.000000 2.500000 1.000000 -0.500000 0.000000 1.500000 1.000000 0.500000 0.000000 0.500000 1.000000 1.500000 0.000000 0.500000 1.000000 0.500000 1.000000 1.500000 0.000000 0.500000 1.000000 1.500000 0.000000 0.500000 2.000000 1.5000...

result:

ok answer = YES

Test #32:

score: 12
Accepted
time: 1ms
memory: 5908kb

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.500000 0.500000 1.000000 1.500000 1.000000 1.000000 0.500000 0.500000 1.500000 1.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.500000 1.000000 0.500000 0.500000 0.500000 1.500000 0.500000 1.000000 1.500000 0.500000 1.000000 1.000000 1.000000 0.500000 1.000000 1.000000 1.000000...

result:

ok answer = YES

Test #33:

score: 12
Accepted
time: 1ms
memory: 5912kb

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.000000 0.000000 2.000000 1.000000 1.000000 2.000000 2.000000 1.000000 1.000000 1.000000 0.000000 2.000000 2.000000 2.000000 2.000000 1.000000 2.000000 2.000000 1.000000 2.000000 1.000000 1.000000 0.000000 0.000000 2.000000 2.000000 2.000000 1.000000 2.000000 1.000000 1.000000 0.000000 2.000000...

result:

ok answer = YES

Test #34:

score: 12
Accepted
time: 1ms
memory: 3772kb

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.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.000000 0.500000 0.500000 0.500000 0.500000 1.000000 0.500000 0.500000 0.000000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.000000 0.500000 0.500000 0.500000 0.500000...

result:

ok answer = YES

Test #35:

score: 12
Accepted
time: 1ms
memory: 6144kb

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.500000 1.000000 1.500000 1.000000 0.500000 1.000000 0.500000 0.000000 0.500000 2.000000 0.500000 0.000000 1.500000 2.000000 -0.500000 0.000000 1.500000 2.000000 -0.500000 -1.000000 2.500000 3.000000 -1.500000 -2.000000 3.500000 3.000000 -1.500000 -2.000000 2.500000 3.000000 -0.500000 -2.000000...

result:

ok answer = YES

Test #36:

score: 12
Accepted
time: 1ms
memory: 6004kb

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.000000 0.500000 1.000000 1.500000 1.000000 0.500000 0.000000 0.500000 1.000000 1.500000 0.000000 0.500000 2.000000 1.500000 -1.000000 0.500000 2.000000 1.500000 -1.000000 -0.500000 3.000000 2.500000 -2.000000 -1.500000 4.000000 2.500000 -2.000000 -1.500000 3.000000 2.500000 -1.000000 -1.500000...

result:

ok answer = YES

Subtask #3:

score: 17
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #37:

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

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.000000 0.000000 -1.000000 1.000000 -1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 1.000000 2.000000 1.000000 1.000000 -1.000000 1.000000 1.000000 1.000000 2.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 1.000000 1.000000 1.000000 0.000000 2.000...

result:

ok answer = YES

Test #38:

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

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.500000 0.500000 -0.500000 0.500000 -0.500000 1.500000 0.500000 1.500000 0.500000 1.500000 0.500000 0.500000 0.500000 1.500000 0.500000 1.500000 -0.500000 1.500000 1.500000 0.500000 2.500000 0.500000 0.500000 0.500000 0.500000 -0.500000 -0.500000 1.500000 0.500000 0.500000 0.500000 0.500000 2....

result:

ok answer = YES

Test #39:

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

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.000000 0.000000 -1.000000 2.000000 1.000000 1.000000 1.000000 0.000000 2.000000 0.000000 1.000000 1.000000 2.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 1.000000 2.000000 0.000000 3.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.00000...

result:

ok answer = YES

Test #40:

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

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.000000 3.000000 -1.000000 -1.000000 3.000000 -2.000000 -1.000000 -4.000000 1.000000 2.000000 -6.000000 -6.000000 -5.000000 2.000000 -10.000000 -5.000000 1.000000 7.000000 -3.000000 4.000000 -1.000000 8.000000 3.000000 1.000000 -1.000000 -6.000000 -1.000000 -4.000000 2.000000 9.000000 -3.000000...

result:

ok answer = YES

Test #41:

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

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: 6020kb

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.000000 1.000000 -4.000000 3.000000 6.000000 -3.000000 4.000000 9.000000 0.000000 -2.000000 -2.000000 4.000000 -3.000000 0.000000 -7.000000 5.000000 5.000000 -7.000000 -6.000000 4.000000 10.000000 -2.000000 -1.000000 -2.000000 5.000000 -4.000000 0.000000 3.000000 3.000000 4.000000 2.000000 4.00...

result:

ok answer = YES

Test #43:

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

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.000000 2.000000 1.000000 1.000000 2.000000 2.000000 -2.000000 1.000000 1.000000 3.000000 0.000000 2.000000 1.000000 -1.000000 0.000000 -1.000000 1.000000 0.000000 -1.000000 -1.000000 0.000000 -1.000000 -1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 2.000000 1...

result:

ok answer = YES

Test #44:

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

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.000000 2.000000 -4.000000 3.000000 -1.000000 -4.000000 0.000000 -1.000000 0.000000 -1.000000 -2.000000 -1.000000 -2.000000 5.000000 0.000000 2.000000 -1.000000 1.000000 5.000000 0.000000 -1.000000 4.000000 4.000000 3.000000 -3.000000 -1.000000 6.000000 -2.000000 2.000000 -2.000000 -2.000000 -2...

result:

ok answer = YES

Test #45:

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

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.500000 4.500000 -3.500000 0.500000 -3.000000 -6.500000 -11.000000 -3.500000 -2.500000 1.500000 -3.500000 1.000000 -4.000000 3.500000 -11.000000 0.000000 -1.500000 -1.000000 4.500000 -0.500000 -3.500000 2.000000 -7.000000 14.000000 -5.500000 -1.500000 3.500000 -4.500000 4.500000 -4.000000 -4.50...

result:

ok answer = YES

Test #46:

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

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.000000 0.000000 0.000000 1.000000 0.000000 -1.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 2.000000 0.000000 2.000000 1.000000 2.000000 1.000000 2.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 1.000000 1.00000...

result:

ok answer = YES

Test #47:

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

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.500000 4.500000 -3.500000 0.500000 -2.500000 -6.500000 -7.500000 -3.500000 -2.500000 1.500000 -1.500000 0.500000 -3.500000 5.500000 -7.500000 0.500000 -1.500000 -0.500000 4.500000 -0.500000 -3.500000 2.500000 -3.500000 10.500000 -5.500000 -1.500000 3.500000 -4.500000 4.500000 -3.500000 -4.5000...

result:

ok answer = YES

Test #48:

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

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.500000 -0.500000 -8.500000 5.500000 2.500000 -1.500000 -2.500000 1.500000 2.500000 -3.500000 3.500000 -4.500000 1.500000 10.500000 -2.500000 5.500000 3.500000 4.500000 9.500000 4.500000 1.500000 7.500000 1.500000 5.500000 -0.500000 3.500000 8.500000 0.500000 -0.500000 1.500000 0.500000 0.5000...

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: 5ms
memory: 5004kb

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.000000 -1.000000 1.000000 0.000000 1.000000 1.000000 3.000000 0.000000 2.000000 3.000000 3.000000 3.000000 -3.000000 3.000000 0.000000 2.000000 1.000000 2.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 3.000000 -2.000000 2.000000 2.000000 2.000000 4.000000 1.000000 -1.000000 5.00...

result:

ok answer = YES

Test #50:

score: 24
Accepted
time: 3ms
memory: 5440kb

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.500000 22.500000 -7.500000 24.500000 0.500000 -8.500000 -6.500000 10.500000 26.500000 16.500000 -8.500000 -21.500000 -4.500000 -5.500000 8.500000 -7.500000 -4.500000 -1.500000 -3.500000 -19.500000 16.500000 -6.500000 4.500000 12.500000 -8.500000 -12.500000 -4.500000 14.500000 -10.500000 -24.50...

result:

ok answer = YES

Test #51:

score: 24
Accepted
time: 3ms
memory: 5608kb

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.000000 7.000000 1.000000 9.000000 8.000000 9.000000 16.000000 1.000000 16.000000 -8.000000 -13.000000 -5.000000 21.000000 -15.000000 5.000000 0.000000 -3.000000 -7.000000 -8.000000 21.000000 -16.000000 -14.000000 4.000000 6.000000 -5.000000 4.000000 16.000000 -1.000000 1.000000 -11.000000 -19....

result:

ok answer = YES

Test #52:

score: 24
Accepted
time: 3ms
memory: 7152kb

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: 6008kb

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.000000 2.000000 1.000000 0.000000 2.000000 0.000000 1.000000 2.000000 -1.000000 2.000000 1.000000 0.000000 -1.000000 3.000000 3.000000 3.000000 1.000000 -1.000000 0.000000 2.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 1.000000 -2.000000 1.000000 1.000000 0.000000 0.00...

result:

ok answer = YES

Test #54:

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

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.000000 0.000000 1.000000 3.000000 -1.000000 1.000000 4.000000 0.000000 1.000000 0.000000 2.000000 4.000000 3.000000 0.000000 -3.000000 1.000000 1.000000 -1.000000 0.000000 0.000000 0.000000 0.000000 3.000000 0.000000 0.000000 1.000000 2.000000 2.000000 0.000000 1.000000 0.000000 1.000000 0.000...

result:

ok answer = YES

Test #55:

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

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.000000 2.000000 2.000000 2.000000 0.000000 2.000000 1.000000 1.000000 -1.000000 0.000000 1.000000 2.000000 1.000000 0.000000 -1.000000 2.000000 2.000000 1.000000 2.000000 1.000000 0.000000 1.000000 0.000000 -2.000000 1.000000 3.000000 1.000000 0.000000 0.000000 1.000000 1.000000 0.000000 3.000...

result:

ok answer = YES

Test #56:

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

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.000000 1.000000 -1.000000 1.000000 1.000000 2.000000 3.000000 0.000000 1.000000 1.000000 -1.000000 1.000000 -1.000000 -1.000000 -1.000000 1.000000 -3.000000 1.000000 0.000000 1.000000 1.000000 -2.000000 2.000000 -1.000000 0.000000 -2.000000 0.000000 1.000000 2.000000 1.000000 3.000000 1.00000...

result:

ok answer = YES

Test #57:

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

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.000000 2.000000 0.000000 1.000000 0.000000 2.000000 0.000000 1.000000 3.000000 2.000000 -1.000000 0.000000 -1.000000 1.000000 2.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 2.000000 -1.000000 1.000000 1.000000 2.000000 1.000000 0.000000 1.000000 -1.000000 2.000000 1.00...

result:

ok answer = YES

Test #58:

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

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.000000 1.000000 2.000000 0.000000 0.000000 1.000000 2.000000 0.000000 -1.000000 1.000000 2.000000 -1.000000 1.000000 -1.000000 2.000000 0.000000 3.000000 2.000000 -1.000000 1.000000 1.000000 -1.000000 0.000000 2.000000 2.000000 1.000000 1.000000 2.000000 2.000000 0.000000 -1.000000 3.000000 -1...

result:

ok answer = YES

Test #59:

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

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.000000 2.000000 3.000000 1.000000 1.000000 2.000000 3.000000 1.000000 0.000000 0.000000 1.000000 -2.000000 2.000000 -2.000000 3.000000 1.000000 2.000000 3.000000 0.000000 0.000000 2.000000 -2.000000 -1.000000 1.000000 1.000000 0.000000 2.000000 3.000000 3.000000 -1.000000 0.000000 4.000000 -2....

result:

ok answer = YES

Test #60:

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

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.000000 -2.000000 0.000000 1.000000 0.000000 1.000000 2.000000 -1.000000 2.000000 2.000000 3.000000 2.000000 -4.000000 3.000000 -1.000000 1.000000 1.000000 3.000000 0.000000 0.000000 1.000000 2.000000 1.000000 2.000000 4.000000 -1.000000 1.000000 2.000000 1.000000 3.000000 0.000000 -1.000000 6....

result:

ok answer = YES

Test #61:

score: 24
Accepted
time: 3ms
memory: 6372kb

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.000000 0.000000 -3.000000 5.000000 0.000000 4.000000 0.000000 -1.000000 3.000000 -1.000000 5.000000 2.000000 2.000000 0.000000 1.000000 -4.000000 1.000000 5.000000 4.000000 -1.000000 -3.000000 0.000000 1.000000 -1.000000 2.000000 0.000000 3.000000 -2.000000 2.000000 0.000000 -2.000000 0.000000...

result:

ok answer = YES

Test #62:

score: 24
Accepted
time: 26ms
memory: 15472kb

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: 36ms
memory: 15776kb

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.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000...

result:

ok answer = YES

Test #64:

score: 24
Accepted
time: 34ms
memory: 15472kb

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: 39ms
memory: 13872kb

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.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000...

result:

ok answer = YES

Test #66:

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

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.000000 1.000000 1.000000 2.000000 1.000000 2.000000 0.000000 -1.000000 0.000000 -1.000000 1.000000 -1.000000 0.000000 2.000000 2.000000 0.000000 2.000000 1.000000 0.000000 2.000000 0.000000 -1.000000 0.000000 -1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 0.000000 1.000000 1.000000 1.0...

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: 50ms
memory: 22024kb

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.000000 29.000000 -28.000000 30.000000 -28.000000 29.000000 -27.000000 29.000000 -28.000000 30.000000 -29.000000 30.000000 -29.000000 31.000000 -29.000000 31.000000 -29.000000 31.000000 -30.000000 32.000000 -31.000000 33.000000 -32.000000 33.000000 -31.000000 33.000000 -32.000000 34.000000 -3...

result:

ok answer = YES

Test #68:

score: 42
Accepted
time: 35ms
memory: 21944kb

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.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000...

result:

ok answer = YES

Test #69:

score: 42
Accepted
time: 41ms
memory: 21368kb

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.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000...

result:

ok answer = YES

Test #70:

score: 42
Accepted
time: 44ms
memory: 27564kb

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.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000...

result:

ok answer = YES

Test #71:

score: 42
Accepted
time: 44ms
memory: 21588kb

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.500000 0.500000 0.500000 1.500000 -0.500000 1.500000 0.500000 0.500000 0.500000 1.500000 -0.500000 1.500000 0.500000 0.500000 0.500000 1.500000 -0.500000 1.500000 0.500000 0.500000 0.500000 1.500000 -0.500000 1.500000 0.500000 0.500000 0.500000 1.500000 -0.500000 1.500000 0.500000 0.500000 0.5...

result:

ok answer = YES

Test #72:

score: 42
Accepted
time: 47ms
memory: 14596kb

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.000000 0.000000 -1.000000 1.000000 -1.000000 -3.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 2.000000 2.000000 0.000000 3.000000 2.000000 1.000000 1.000000 0.000000 0.000000 2.000000 0.000000 2.000000 1.000000 0.000000 1.000000 0.000000 0.000000 3.000000 1.000000 1.000000 2.00...

result:

ok answer = YES

Test #73:

score: 42
Accepted
time: 52ms
memory: 14304kb

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.000000 0.000000 -1.000000 1.000000 -1.000000 -3.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 2.000000 2.000000 0.000000 3.000000 2.000000 1.000000 1.000000 0.000000 0.000000 2.000000 0.000000 2.000000 1.000000 0.000000 1.000000 0.000000 0.000000 3.000000 1.000000 1.000000 2.00...

result:

ok answer = YES

Test #74:

score: 42
Accepted
time: 30ms
memory: 14180kb

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.000000 2.000000 -40.000000 73.000000 83.000000 -68.000000 42.000000 -32.000000 -74.000000 -67.000000 -71.000000 47.000000 -48.000000 43.000000 56.000000 1.000000 21.000000 15.000000 37.000000 -12.000000 -7.000000 -85.000000 65.000000 74.000000 -32.000000 -21.000000 -40.000000 -85.000000 -24....

result:

ok answer = YES

Test #75:

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

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: 6ms
memory: 5416kb

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.000000 0.000000 2.000000 -1.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 3.000000 2.000000 1.000000 0.000000 -1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 -2.000000 0.000000 -1.000000 0.000000 0.000000 -...

result:

ok answer = YES

Test #77:

score: 42
Accepted
time: 9ms
memory: 6440kb

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.000000 2.000000 4.000000 2.000000 -1.000000 0.000000 -2.000000 0.000000 0.000000 0.000000 0.000000 2.000000 -2.000000 1.000000 1.000000 2.000000 0.000000 1.000000 0.000000 2.000000 1.000000 4.000000 1.000000 0.000000 -1.000000 0.000000 2.000000 2.000000 -1.000000 0.000000 2.000000 1.000000 0.0...

result:

ok answer = YES

Test #78:

score: 42
Accepted
time: 19ms
memory: 9648kb

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.000000 2.000000 2.000000 -1.000000 0.000000 2.000000 3.000000 1.000000 3.000000 1.000000 -1.000000 -1.000000 0.000000 0.000000 1.000000 1.000000 4.000000 0.000000 1.000000 3.000000 0.000000 0.000000 1.000000 1.000000 0.000000 1.000000 -1.000000 -1.000000 1.000000 -1.000000 2.000000 1.000000 -...

result:

ok answer = YES

Test #79:

score: 42
Accepted
time: 41ms
memory: 13088kb

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.000000 0.000000 1.000000 0.000000 2.000000 0.000000 2.000000 0.000000 3.000000 1.000000 2.000000 0.000000 1.000000 2.000000 3.000000 2.000000 0.000000 1.000000 2.000000 -1.000000 0.000000 0.000000 0.000000 3.000000 2.000000 1.000000 1.000000 0.000000 2.000000 3.000000 0.000000 0.000000 1.00000...

result:

ok answer = YES

Test #80:

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

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.000000 24.000000 -91.000000 23.000000 -7.000000 2.000000 38.000000 16.000000 -11.000000 -11.000000 -40.000000 12.000000 -13.000000 33.000000 101.000000 -16.000000 30.000000 -14.000000 -3.000000 34.000000 -117.000000 4.000000 20.000000 62.000000 -110.000000 13.000000 -64.000000 -9.000000 -40.0...

result:

ok answer = YES

Test #81:

score: 42
Accepted
time: 18ms
memory: 17072kb

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: 54ms
memory: 20700kb

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.500000 74.500000 -28.500000 18.500000 35.500000 17.500000 0.500000 24.500000 -26.500000 -30.500000 62.500000 23.500000 -18.500000 54.500000 19.500000 19.500000 4.500000 -5.500000 -52.500000 47.500000 -21.500000 12.500000 68.500000 39.500000 -10.500000 -28.500000 75.500000 18.500000 -22.500000...

result:

ok answer = YES

Test #83:

score: 42
Accepted
time: 58ms
memory: 21948kb

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.000000 120.000000 -66.000000 -119.000000 82.000000 -99.000000 -112.000000 -117.000000 -94.000000 -81.000000 130.000000 -113.000000 -79.000000 121.000000 51.000000 -99.000000 1.000000 -28.000000 -112.000000 91.000000 -102.000000 -106.000000 49.000000 87.000000 -100.000000 -122.000000 58.00000...

result:

ok answer = YES

Test #84:

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

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.000000 27.000000 27.000000 -26.000000 -11.000000 -6.000000 -19.000000 -24.000000 -1.000000 12.000000 37.000000 -20.000000 14.000000 28.000000 -42.000000 -6.000000 -92.000000 65.000000 -19.000000 -2.000000 -9.000000 -13.000000 -44.000000 -6.000000 -7.000000 -29.000000 -35.000000 -21.000000 6.0...

result:

ok answer = YES

Test #85:

score: 42
Accepted
time: 34ms
memory: 22020kb

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.000000 -3.000000 4.000000 -2.000000 4.000000 -3.000000 5.000000 -3.000000 4.000000 -2.000000 3.000000 -2.000000 3.000000 -1.000000 3.000000 -1.000000 3.000000 -1.000000 2.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 2.000000 0.000000 1.000000 1.000000 0.000000...

result:

ok answer = YES

Test #86:

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

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.000000 10.000000 -9.000000 11.000000 -9.000000 10.000000 -8.000000 10.000000 -9.000000 11.000000 -10.000000 11.000000 -10.000000 12.000000 -10.000000 12.000000 -10.000000 12.000000 -11.000000 13.000000 -12.000000 14.000000 -13.000000 14.000000 -12.000000 14.000000 -13.000000 15.000000 -13.000...

result:

ok answer = YES

Test #87:

score: 42
Accepted
time: 27ms
memory: 15976kb

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: 67ms
memory: 17256kb

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.500000 -37.500000 -3.000000 -50.500000 -28.500000 49.500000 60.500000 59.500000 34.500000 55.500000 61.500000 27.500000 -54.500000 23.500000 13.500000 65.500000 -46.500000 7.000000 -34.500000 72.500000 15.500000 -28.500000 47.500000 97.500000 3.500000 -3.500000 28.000000 48.500000 98.500000 -...

result:

ok answer = YES

Test #89:

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

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.500000 0.500000 0.500000 1.000000 0.500000 0.500000 1.000000 1.500000 -0.500000 1.500000 0.500000 1.000000 0.500000 1.000000 1.000000 1.500000 0.500000 0.500000 0.500000 1.500000 1.000000 0.000000 2.000000 1.500000 0.500000 0.500000 0.500000 1.000000 0.500000 0.000000 1.000000 0.000000 0.00000...

result:

ok answer = YES

Test #90:

score: 42
Accepted
time: 52ms
memory: 13316kb

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.000000 0.000000 1.000000 0.500000 1.000000 0.500000 0.500000 1.000000 0.500000 0.500000 2.000000 -0.500000 1.000000 0.500000 1.000000 2.000000 0.500000 2.000000 1.500000 1.500000 0.500000 1.500000 1.000000 2.000000 0.500000 1.500000 1.500000 0.500000 0.000000 1.000000 1.000000 0.500000 0.50000...

result:

ok answer = YES

Test #91:

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

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.500000 1.000000 1.500000 1.000000 0.000000 1.500000 0.500000 1.000000 1.000000 0.500000 1.500000 1.500000 1.000000 0.500000 1.500000 -0.500000 1.500000 1.500000 2.000000 1.500000 1.000000 1.500000 2.000000 -0.500000 0.500000 1.000000 0.500000 1.000000 0.500000 0.000000 1.000000 0.500000 0.5000...

result:

ok answer = YES

Test #92:

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

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.500000 -0.500000 0.500000 0.500000 2.500000 0.500000 0.500000 0.500000 3.500000 2.500000 -1.500000 -2.500000 2.500000 1.500000 1.500000 0.500000 4.500000 -1.500000 0.500000 1.500000 0.500000 -2.500000 1.500000 3.500000 2.500000 2.500000 -0.500000 1.500000 -1.500000 -2.500000 2.500000 2.500000...

result:

ok answer = YES

Test #93:

score: 42
Accepted
time: 27ms
memory: 9112kb

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.000000 1.000000 1.000000 2.000000 4.000000 0.000000 2.000000 0.000000 -1.000000 3.000000 3.000000 1.000000 -1.000000 1.000000 2.000000 1.000000 0.000000 -1.000000 1.000000 1.000000 3.000000 1.000000 0.000000 -2.000000 0.000000 -2.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.0...

result:

ok answer = YES

Test #94:

score: 42
Accepted
time: 27ms
memory: 21208kb

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: 22ms
memory: 13712kb

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: 88ms
memory: 23848kb

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.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.000000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000 0.500000...

result:

ok answer = YES

Test #97:

score: 42
Accepted
time: 17ms
memory: 20628kb

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