QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#187653#7502. Painting the RoadsCrysflyAC ✓107ms411460kbC++144.4kb2023-09-24 19:44:542023-09-24 19:44:54

Judging History

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

  • [2023-09-24 19:44:54]
  • 评测
  • 测评结果:AC
  • 用时:107ms
  • 内存:411460kb
  • [2023-09-24 19:44:54]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
#define i128 __int128
//#define int long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 300005
#define inf 0x3f3f3f3f

int n,m;
int col[maxn],wei[maxn];
vector<pii>e[maxn];

int fa[maxn],cc[maxn],cd[maxn],fw[maxn];
void dfs0(int u,int pa){
	for(auto [v,id]:e[u]){
		if(v==pa)continue;
		fa[v]=u,fw[v]=id;
		dfs0(v,u);
		cc[u]^=cc[v];
	}
	if(pa){
		if(col[fw[u]]!=cc[u]) cc[u]^=1,cd[u]=1;
	}
}

int V=10005;
int f[5005][20010],sz[maxn],ss[maxn],g[20010];
void dfs(int u){
	memset(f[u],63,sizeof f[u]);
	sz[u]=0;
	f[u][V]=0;
	for(auto [v,id]:e[u]){
		if(v==fa[u])continue;
		dfs(v);
		memset(g,63,sizeof g);
		For(i,-sz[u],sz[u]) if(f[u][i+V]<inf)
			For(j,-sz[v],sz[v]) if(f[v][j+V]<inf)
				g[i+j+V]=min(g[i+j+V],f[u][i+V]+f[v][j+V]);
		For(j,-sz[v],sz[v]) f[v][j+V]=inf;
		sz[u]+=sz[v];
		sz[u]=min(sz[u],10000);
		For(i,-sz[u],sz[u]) f[u][i+V]=g[i+V],g[i+V]=inf;
	}
	if(ss[u]){
		memset(g,63,sizeof g);
		For(i,-sz[u],sz[u]) g[i+V+ss[u]]=f[u][i+V];
		sz[u]+=ss[u];
		sz[u]=min(sz[u],10000);
		For(i,-sz[u],sz[u]) f[u][i+V]=g[i+V],g[i+V]=inf;
	}
	if(fa[u]){
		memset(g,63,sizeof g);
		int w=wei[fw[u]];
	//	cout<<"wei "<<u<<" "<<w<<"\n";
		if(cc[u]){
			For(i,-sz[u],sz[u]) g[i+V-1]=f[u][i+V];
		}else{
			For(i,-sz[u],sz[u]) g[i+V]=f[u][i+V];
		}
		++sz[u];
		sz[u]=min(sz[u],10000);
		Rep(i,sz[u],-sz[u]){
			if(i+2<=sz[u]) g[i+V]=min(g[i+V],g[i+V+2]);
			f[u][i+V]=inf;
			if(g[i+V]<inf) f[u][i+V]=g[i+V]+w*(i>0?i:-i);
		}
	}
//	cout<<"u: "<<u<<"\n";
//	For(i,-sz[u],sz[u]) cout<<f[u][i+V]<<" "; cout<<"\n";
}

void work()
{
	n=read(),m=read();
	For(i,1,n)e[i].clear(),cc[i]=fa[i]=fw[i]=ss[i]=cd[i]=0;
	For(i,2,n){
		int u=read(),v=read();
		wei[i]=read(),col[i]=read();
		e[u].pb(mkp(v,i));
		e[v].pb(mkp(u,i));
	}
	dfs0(1,0);
	For(i,1,n) cc[i]=cd[i];
	For(i,1,m){
		int x=read();
		++ss[x],cc[x]^=1;
	}
//	For(i,1,n)cout<<ss[i]<<" \n"[i==n];
//	For(i,1,n)cout<<cc[i]<<" \n"[i==n];
	dfs(1);
	int res=inf;
	For(i,0,sz[1]) res=min(res,f[1][i+V]);
	if(res==inf) res=-1;
	cout<<res<<"\n";
}

signed main()
{
//	cout<<5000*5000ll*10<<"\n";
//	freopen("data.in","r",stdin);
	memset(g,63,sizeof g);
	int T=read();
	while(T--)work();
	return 0;
}
/*

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 20168kb

input:

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

output:

3
9
21
-1
42

result:

ok 5 number(s): "3 9 21 -1 42"

Test #2:

score: 0
Accepted
time: 19ms
memory: 20032kb

input:

1000
5 5
1 2 4 1
2 3 9 0
3 4 10 1
3 5 8 1
1 5 2 5 1
5 3
1 2 7 1
1 3 7 0
2 4 9 0
3 5 4 1
3 4 3
5 3
1 2 7 1
2 3 1 0
1 4 7 1
4 5 5 1
4 4 3
5 1
1 2 3 1
1 3 6 0
2 4 10 0
2 5 7 0
1
5 3
1 2 10 1
1 3 10 0
1 4 1 1
3 5 4 0
2 5 2
5 5
1 2 7 0
1 3 5 0
2 4 8 1
2 5 10 0
2 2 3 5 4
5 4
1 2 6 1
1 3 4 0
3 4 4 0
1 5 5 ...

output:

22
-1
19
3
11
8
11
7
8
0
10
1
1
7
5
28
12
-1
19
16
12
13
-1
32
9
18
16
14
10
12
16
0
11
-1
17
-1
9
14
27
8
11
-1
6
6
15
18
46
0
14
9
-1
5
8
22
-1
-1
17
-1
25
6
0
24
6
15
21
15
22
-1
6
0
65
20
5
28
20
0
20
19
18
-1
10
0
16
9
19
6
21
11
11
4
6
20
11
0
8
8
31
8
23
-1
8
-1
11
-1
9
13
-1
-1
19
9
20
19
6
...

result:

ok 1000 numbers

Test #3:

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

input:

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

output:

47
-1
84
68
61
112
39
-1
-1
48
71
-1
-1
77
-1
-1
59
97
-1
-1
74
52
-1
-1
-1
84
48
-1
68
60
57
-1
79
68
-1
79
51
-1
33
48
62
-1
-1
113
84
44
-1
79
-1
76
64
-1
-1
110
42
40
56
81
-1
73
68
-1
74
125
67
44
-1
103
-1
-1
-1
89
64
-1
85
-1
50
-1
64
-1
-1
94
46
75
-1
-1
-1
101
67
61
-1
-1
18
100
57
102
-1
-...

result:

ok 250 numbers

Test #4:

score: 0
Accepted
time: 29ms
memory: 26156kb

input:

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

output:

149
233
-1
204
-1
145
164
-1
-1
-1
185
182
-1
145
252
-1
-1
160
186
163
-1
256
182
173
202
238
410
-1
169
-1
259
-1
103
117
171
-1
-1
-1
163
-1
-1
265
-1
-1
-1
162
136
140
-1
-1
217
211
193
114
246
251
133
176
-1
-1
219
139
195
-1
214
180
-1
223
132
153
-1
-1
-1
172
310
102
-1
200
-1
-1
195
-1
-1
20...

result:

ok 100 numbers

Test #5:

score: 0
Accepted
time: 43ms
memory: 61016kb

input:

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

output:

1335
2129
1372
1752
1354
1809
1309
1542
1359
-1

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 43ms
memory: 59028kb

input:

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

output:

-1
1604
-1
-1
1375
1450
-1
1448
1350
1366

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 39ms
memory: 61052kb

input:

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

output:

1433
-1
1365
-1
1425
2849
1360
1571
1369
1666

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 64ms
memory: 214920kb

input:

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

output:

-1
-1

result:

ok 2 number(s): "-1 -1"

Test #9:

score: 0
Accepted
time: 76ms
memory: 214892kb

input:

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

output:

6761
8789

result:

ok 2 number(s): "6761 8789"

Test #10:

score: 0
Accepted
time: 83ms
memory: 214840kb

input:

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

output:

6858
-1

result:

ok 2 number(s): "6858 -1"

Test #11:

score: 0
Accepted
time: 85ms
memory: 216888kb

input:

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

output:

6616
7292

result:

ok 2 number(s): "6616 7292"

Test #12:

score: 0
Accepted
time: 71ms
memory: 409520kb

input:

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

output:

18174

result:

ok 1 number(s): "18174"

Test #13:

score: 0
Accepted
time: 67ms
memory: 411460kb

input:

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

output:

9970

result:

ok 1 number(s): "9970"

Test #14:

score: 0
Accepted
time: 63ms
memory: 409548kb

input:

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

output:

5981

result:

ok 1 number(s): "5981"

Test #15:

score: 0
Accepted
time: 72ms
memory: 409612kb

input:

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

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 88ms
memory: 409588kb

input:

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

output:

20709

result:

ok 1 number(s): "20709"

Test #17:

score: 0
Accepted
time: 87ms
memory: 409520kb

input:

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

output:

14832

result:

ok 1 number(s): "14832"

Test #18:

score: 0
Accepted
time: 86ms
memory: 409388kb

input:

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

output:

12769

result:

ok 1 number(s): "12769"

Test #19:

score: 0
Accepted
time: 80ms
memory: 409452kb

input:

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

output:

11987

result:

ok 1 number(s): "11987"

Test #20:

score: 0
Accepted
time: 92ms
memory: 409484kb

input:

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

output:

13461

result:

ok 1 number(s): "13461"

Test #21:

score: 0
Accepted
time: 91ms
memory: 409528kb

input:

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

output:

15399

result:

ok 1 number(s): "15399"

Test #22:

score: 0
Accepted
time: 103ms
memory: 409352kb

input:

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

output:

13750

result:

ok 1 number(s): "13750"

Test #23:

score: 0
Accepted
time: 92ms
memory: 409544kb

input:

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

output:

12984

result:

ok 1 number(s): "12984"

Test #24:

score: 0
Accepted
time: 57ms
memory: 409448kb

input:

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

output:

439

result:

ok 1 number(s): "439"

Test #25:

score: 0
Accepted
time: 90ms
memory: 409484kb

input:

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

output:

15533

result:

ok 1 number(s): "15533"

Test #26:

score: 0
Accepted
time: 76ms
memory: 409412kb

input:

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

output:

8937

result:

ok 1 number(s): "8937"

Test #27:

score: 0
Accepted
time: 69ms
memory: 409552kb

input:

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

output:

-1

result:

ok 1 number(s): "-1"

Test #28:

score: 0
Accepted
time: 107ms
memory: 409488kb

input:

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

output:

13800

result:

ok 1 number(s): "13800"

Test #29:

score: 0
Accepted
time: 60ms
memory: 409588kb

input:

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

output:

45838

result:

ok 1 number(s): "45838"

Test #30:

score: 0
Accepted
time: 75ms
memory: 409616kb

input:

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

output:

25924

result:

ok 1 number(s): "25924"

Test #31:

score: 0
Accepted
time: 83ms
memory: 409468kb

input:

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

output:

12327

result:

ok 1 number(s): "12327"

Test #32:

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

input:

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

output:

4786
496
1115
11038
124
130
1428
96
13
16
16

result:

ok 11 numbers

Test #33:

score: 0
Accepted
time: 83ms
memory: 249704kb

input:

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

output:

8836
1053
4019
3
-1

result:

ok 5 number(s): "8836 1053 4019 3 -1"

Test #34:

score: 0
Accepted
time: 82ms
memory: 337712kb

input:

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

output:

10832
2333
11
448
35
19
31

result:

ok 7 numbers

Test #35:

score: 0
Accepted
time: 52ms
memory: 194292kb

input:

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

output:

6476
1307
2806
1343
845
-1
38
-1

result:

ok 8 numbers

Test #36:

score: 0
Accepted
time: 71ms
memory: 401328kb

input:

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

output:

4094
139
79
27
23
12

result:

ok 6 numbers

Test #37:

score: 0
Accepted
time: 68ms
memory: 362340kb

input:

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

output:

8810
1090
672
6

result:

ok 4 number(s): "8810 1090 672 6"

Test #38:

score: 0
Accepted
time: 86ms
memory: 303008kb

input:

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

output:

11103
2545
59
841
147
3

result:

ok 6 numbers

Test #39:

score: 0
Accepted
time: 80ms
memory: 333636kb

input:

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

output:

10827
197
301
591

result:

ok 4 number(s): "10827 197 301 591"

Test #40:

score: 0
Accepted
time: 72ms
memory: 387116kb

input:

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

output:

16879
553
185
147
9

result:

ok 5 number(s): "16879 553 185 147 9"

Test #41:

score: 0
Accepted
time: 64ms
memory: 186232kb

input:

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

output:

5526
279
1357
6801
51
923
22

result:

ok 7 numbers

Test #42:

score: 0
Accepted
time: 58ms
memory: 183996kb

input:

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

output:

5835
1541
-1
410
497
2164
282
430
18
10

result:

ok 10 numbers

Test #43:

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

input:

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

output:

1403
294
397
5166
54
-1
125

result:

ok 7 numbers

Test #44:

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

input:

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

output:

3159
2345
2014
1100
-1
-1
-1

result:

ok 7 numbers

Test #45:

score: 0
Accepted
time: 66ms
memory: 288504kb

input:

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

output:

3794
7195
438
22
-1
6
2

result:

ok 7 numbers

Test #46:

score: 0
Accepted
time: 77ms
memory: 282480kb

input:

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

output:

9237
3709
516
164
69
64
2
0

result:

ok 8 numbers

Test #47:

score: 0
Accepted
time: 71ms
memory: 366428kb

input:

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

output:

670
10553
-1
25
26
15

result:

ok 6 numbers

Test #48:

score: 0
Accepted
time: 59ms
memory: 171756kb

input:

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

output:

4556
2135
3162
1315
181
73

result:

ok 6 numbers

Test #49:

score: 0
Accepted
time: 64ms
memory: 255912kb

input:

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

output:

3834
1509
-1
145
97
-1

result:

ok 6 numbers

Test #50:

score: 0
Accepted
time: 68ms
memory: 262000kb

input:

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

output:

7846
-1
993
704
48
43

result:

ok 6 numbers

Test #51:

score: 0
Accepted
time: 64ms
memory: 188160kb

input:

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

output:

2781
7389
2626
2096
967
55
-1
3
9

result:

ok 9 numbers