QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783161#9630. 沙堆wcdrML 18ms62680kbC++175.7kb2024-11-26 00:13:362024-11-26 00:13:39

Judging History

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

  • [2024-11-26 00:13:39]
  • 评测
  • 测评结果:ML
  • 用时:18ms
  • 内存:62680kb
  • [2024-11-26 00:13:36]
  • 提交

answer

#include<random>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
//#define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
//#define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
//#define int LL
//#define double long double
#define mkp make_pair
#define par pair<int,int>
#define psb push_back
#define epb emplace_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
//	return getchar();
	static char buf[Mxxx],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
//	return fl?0:putchar(ch),0;
	static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
	return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
	char ch=gc();
	int gans=0,gflag=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
	char ch=gc();
	int gflag=0;gans=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
	if(x>9)write(x/10);
	pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
	if(x<0)pc('-'),x=-x;
	write(x);pc(ch);
}
inline void writechar(char x,char ch)
{
	pc(x);pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
	return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
	return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
	return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
	x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
	x=Min(x,y);
}
const int Mx=1e6;
int n,cnt,c[Mx+5],h[Mx+5],du[Mx+5],nxt[(Mx<<1)+5],tto[(Mx<<1)+5];
inline void ade(int x,int y){nxt[++cnt]=h[x];tto[h[x]=cnt]=y;du[y]++;}
inline void Ade(int x,int y){ade(x,y),ade(y,x);}
inline vector<int> Mrg(vector<int>&x,vector<int>&y)
{
	int sx=!x.empty()?x.size():0,sy=!y.empty()?y.size():0;
	int i,j;vector<int>v;v.clear();
	for(i=j=0;i<sx&&j<sy;)v.epb((x[i]<=y[j]?x[i++]:y[j++]));
	for(;i<sx;i++)v.epb(x[i]);
	for(;j<sy;j++)v.epb(y[j]);
	return v;
}
vector<int>vec[Mx+5],rcd[Mx+5];int tt[Mx+5];
inline void DFS(int x,int y)
{
	int i,j,k,t,p,v,ls,to;vector<int>tmp;tmp.clear();
	for(i=h[x];i;i=nxt[i])
	{
		if((to=tto[i])^y)
		{
			DFS(to,x);
			tmp=Mrg(tmp,vec[to]);
		}
	}
//	cout<<"Ck_tmp_before:"<<x<<" "<<(!tmp.empty()?tmp.size():0)<<":";
//	for(int vv:tmp)cout<<vv<<" ";
//	cout<<"\n";
//	for(i=1,j=0,k=!tmp.empty()?tmp.back():0;c[x]>=du[x]&&i<=k;i++)
//	{
//		for(t=0;j<(int)tmp.size()&&tmp[j]==i;j++)t++;
//		c[x]-=t+(y!=0);if(y)c[y]++;
//		tt[x]++;
//	}
	for(ls=i=0,k=!tmp.empty()?tmp.size():0;i<k&&c[x]>=du[x];i=j)
	{
		for(j=i;j<k&&tmp[j]==tmp[i];j++);
		t=j-i;t+=(y?tmp[i]-ls:0);
//		if(c[x]-t<du[x]&&(tmp[i]>ls+1)&&y&&c[x]-(tmp[i]-ls-1)<du[x])
		if(tmp[i]>ls+1&&y&&c[x]-(tmp[i]-ls-1)<du[x])
		{
			t=c[x]-du[x]+1;c[x]-=t;
			tt[x]+=t;c[y]+=t;
			break;
		}
		c[x]-=t;tt[x]+=tmp[i]-ls;
		if(y)c[y]+=tmp[i]-ls;
		ls=tmp[i];
	}
//	if(i<=k)
	if(i<k)
	{
		assert(c[x]<du[x]);
		vector<int>v;v.clear();
//		for(;j<(int)tmp.size();j++)v.epb(tmp[j]-tt[x]);
		for(;i<k;i++)v.epb(tmp[i]-tt[x]);
		swap(v,tmp);
	}
	else
	{
		tmp.clear();
		if(c[x]>=du[x])
		{
			assert(y);
			t=c[x]-du[x]+1;//tt[x]+=t;
			c[x]-=t;c[y]+=t;
		}
	}
//	cout<<"Ck_tmp_after:"<<x<<" "<<(!tmp.empty()?tmp.size():0)<<":";
//	for(int vv:tmp)cout<<vv<<" ";
//	cout<<"\n";
	for(i=1;i<=du[x]-1-c[x];i++)vec[x].epb(i);
	for(i=0,ls=0,p=du[x]-1-c[x],k=!tmp.empty()?tmp.size():0;i<k;i++)
	{
		vec[x].epb(p+(v=tmp[i])-ls+1);
		rcd[x].epb(ls=v);p=vec[x].back();
	}
//	cout<<"Ck_vec:"<<x<<" "<<(!vec[x].empty()?vec[x].size():0)<<":";
//	for(int vv:vec[x])cout<<vv<<" ";
//	cout<<"\n";
//	cout<<"Ck_Final_c:"<<x<<":"<<c[x]<<" "<<du[x]<<"|"<<tt[x]<<" "<<c[y]<<"\n";
}
inline void Slv(int x,int y)
{
	int i,j,k,t,to;int ls;
//	for(i=1,j=0,k=!rcd[x].empty()?rcd[x].back():0;c[x]>=du[x]&&i<=k;i++)
//	{
//		for(t=0;j<(int)rcd[x].size()&&rcd[x][j]==i;j++)t++;
//		c[x]-=t+(y!=0);tt[x]++;
//	}
	for(ls=i=0,k=!rcd[x].empty()?rcd[x].size():0;i<k&&c[x]>=du[x];i=j)
	{
		for(j=i;j<k&&rcd[x][j]==rcd[x][i];j++);
		t=j-i;t+=(y?rcd[x][i]-ls:0);
//		if(c[x]-t<du[x]&&(rcd[x][i]>ls+1)&&y&&c[x]-(rcd[x][i]-ls-1)<du[x])
		if(rcd[x][i]>ls+1&&y&&c[x]-(rcd[x][i]-ls-1)<du[x])
		{
			t=c[x]-du[x]+1;c[x]-=t;
			tt[x]+=t;
			break;
		}
		c[x]-=t;tt[x]+=rcd[x][i]-ls;
		ls=rcd[x][i];
	}
//	cout<<"Slv???:"<<x<<" "<<k<<":"<<c[x]<<" "<<du[x]<<"???"<<i<<"\n";
	if(c[x]>=du[x])
	{
		assert(i==k);
		t=c[x]-du[x]+1;//tt[x]+=t;
		c[x]-=t;
	}
	for(i=h[x];i;i=nxt[i])
	{
		if((to=tto[i])^y)
		{
			c[to]+=tt[x];
			Slv(to,x);
		}
	}
}
signed main()
{
	#ifndef ONLINE_JUDGE
//	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	#endif
	int i,s=0;n=read();
	for(i=1;i<n;i++)Ade(read(),read());
	for(i=1;i<=n;i++)c[i]=read(),s+=du[i]-1;
	for(i=1;i<=n;i++)if((s-=c[i])<0)return writenum(-1,10),output;
	DFS(1,0);Slv(1,0);for(i=1;i<=n;i++)writenum(c[i],i==n?10:32);
	return output;
}
/*
6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1
*/
/*
12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 58740kb

input:

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

output:

1 2 0 1 0 0

result:

ok single line: '1 2 0 1 0 0'

Test #2:

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

input:

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

output:

0 1 2 1 1 0 1 1 0 0 0 0

result:

ok single line: '0 1 2 1 1 0 1 1 0 0 0 0'

Test #3:

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

input:

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

output:

1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 1 0 2 1 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0

result:

ok single line: '1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 ...0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0'

Test #4:

score: 0
Accepted
time: 14ms
memory: 61588kb

input:

5000
1 2
1 3
2 4
4 5
3 6
5 7
7 8
6 9
8 10
9 11
10 12
11 13
13 14
14 15
12 16
16 17
15 18
17 19
16 20
18 21
16 22
15 23
20 24
24 25
25 26
22 27
23 28
19 29
27 30
29 31
27 32
28 33
32 34
31 35
26 36
34 37
35 38
35 39
33 40
38 41
40 42
42 43
30 44
41 45
37 46
39 47
47 48
36 49
48 50
46 51
44 52
51 53
4...

output:

1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 2 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 2 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 2 ...

result:

ok single line: '1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #5:

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

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
9 11
10 12
6 13
11 14
12 15
13 16
16 17
14 18
17 19
17 20
19 21
15 22
21 23
22 24
18 25
23 26
24 27
25 28
28 29
27 30
29 31
26 32
30 33
19 34
34 35
32 36
20 37
37 38
31 39
35 40
39 41
40 42
42 43
41 44
33 45
43 46
38 47
46 48
45 49
48 50
44 51
49 52
51 53
50...

output:

1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 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 2 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 2 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 ...

result:

ok single line: '1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #6:

score: 0
Accepted
time: 18ms
memory: 61848kb

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
10 11
9 12
11 13
12 14
13 15
15 16
14 17
17 18
16 19
18 20
19 21
21 22
20 23
22 24
23 25
24 26
26 27
25 28
28 29
27 30
29 31
31 32
30 33
32 34
33 35
35 36
34 37
36 38
37 39
39 40
38 41
40 42
31 43
41 44
43 45
44 46
42 47
46 48
45 49
48 50
49 51
51 52
52 53
5...

output:

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 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 2 0 1 2 1 1 1 1 1 1 1 1 2 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 3 1 2 1 1 1 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 ...

result:

ok single line: '1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #7:

score: 0
Accepted
time: 11ms
memory: 61556kb

input:

5000
1 2
1 3
2 4
3 5
5 6
4 7
7 8
6 9
9 10
10 11
8 12
11 13
13 14
12 15
14 16
16 17
7 18
15 19
18 20
19 21
17 22
22 23
20 24
24 25
23 26
21 27
25 28
27 29
29 30
28 31
26 32
31 33
30 34
32 35
35 36
34 37
33 38
38 39
39 40
40 41
37 42
41 43
43 44
42 45
36 46
44 47
45 48
46 49
48 50
47 51
43 52
49 53
52...

output:

1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 2 1 1 1 2 0 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 0 1 1 0 2 1 1 1 0 2 1 1 1 0 1 1 1 0 0 1 1 1 1 1 2 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 4 0 1 0 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok single line: '1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #8:

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

input:

5000
1 2
1 3
2 4
3 5
5 6
4 7
6 8
8 9
8 10
10 11
9 12
11 13
7 14
13 15
12 16
14 17
15 18
16 19
18 20
19 21
20 22
17 23
21 24
24 25
23 26
26 27
22 28
25 29
27 30
28 31
31 32
30 33
32 34
33 35
34 36
35 37
37 38
38 39
36 40
40 41
39 42
29 43
42 44
44 45
42 46
46 47
41 48
47 49
49 50
45 51
43 52
51 53
48...

output:

1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 0 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 3 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 ...

result:

ok single line: '1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #9:

score: 0
Accepted
time: 18ms
memory: 62680kb

input:

5000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
7 10
8 11
9 12
10 13
11 14
13 15
14 16
15 17
17 18
16 19
17 20
12 21
18 22
20 23
21 24
24 25
23 26
20 27
22 28
28 29
25 30
29 31
27 32
30 33
32 34
34 35
33 36
30 37
36 38
31 39
35 40
37 41
26 42
39 43
38 44
19 45
42 46
44 47
40 48
46 49
49 50
45 51
48 52
47 53
50...

output:

1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 2 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 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 0 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 2 1 1 1 1 1 1 2 1 ...

result:

ok single line: '1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #10:

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

input:

5000
1 2
2 3
1 4
3 5
4 6
5 7
6 8
7 9
6 10
6 11
10 12
11 13
13 14
12 15
9 16
14 17
15 18
16 19
17 20
18 21
21 22
22 23
18 24
20 25
23 26
25 27
8 28
28 29
26 30
24 31
27 32
19 33
30 34
29 35
33 36
34 37
37 38
35 39
34 40
32 41
36 42
42 43
39 44
43 45
44 46
45 47
46 48
41 49
47 50
49 51
48 52
52 53
50 ...

output:

1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 0 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 0 1 1 1 3 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 1 1 2 ...

result:

ok single line: '1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #11:

score: 0
Accepted
time: 11ms
memory: 59848kb

input:

5000
1 2
2 3
3 4
4 5
1 6
6 7
7 8
5 9
8 10
10 11
9 12
12 13
11 14
13 15
10 16
15 17
14 18
17 19
17 20
16 21
20 22
19 23
22 24
23 25
24 26
25 27
25 28
21 29
18 30
26 31
27 32
30 33
31 34
32 35
34 36
36 37
37 38
38 39
35 40
39 41
40 42
29 43
41 44
44 45
42 46
41 47
43 48
28 49
47 50
46 51
50 52
51 53
5...

output:

1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 2 1 2 1 0 1 1 1 1 1 1 1 1 0 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 2 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 ...

result:

ok single line: '1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #12:

score: 0
Accepted
time: 13ms
memory: 61696kb

input:

5000
1 2
1 3
3 4
2 5
4 6
6 7
5 8
7 9
8 10
9 11
10 12
3 13
11 14
14 15
11 16
13 17
17 18
16 19
15 20
20 21
21 22
18 23
19 24
22 25
12 26
24 27
27 28
25 29
26 30
29 31
30 32
23 33
30 34
34 35
33 36
35 37
32 38
37 39
36 40
18 41
39 42
28 43
41 44
31 45
43 46
44 47
40 48
46 49
47 50
49 51
42 52
38 53
45...

output:

1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 0 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok single line: '1 1 2 1 1 1 1 1 1 1 2 1 1 1 0 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'

Test #13:

score: -100
Memory Limit Exceeded

input:

1000000
1 2
1 3
2 4
3 5
4 6
5 7
7 8
8 9
9 10
8 11
6 12
12 13
13 14
11 15
15 16
14 17
16 18
11 19
15 20
18 21
10 22
22 23
19 24
20 25
15 26
25 27
25 28
28 29
17 30
30 31
29 32
30 33
24 34
31 35
34 36
33 37
23 38
28 39
32 40
26 41
21 42
42 43
27 44
39 45
36 46
43 47
37 48
34 49
44 50
47 51
50 52
48 53...

output:

1 1 1 1 1 1 1 2 1 1 2 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 0 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 ...

result: