stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#define rp(i,s,e) for(int i=(s);i<(e);++i)

#define eb emplace_back

#define NMAX 100000



int K = 1;

vvi tree(NMAX);

vi colors(NMAX), visited(NMAX);



void dfs(int p, int p_color){

	K = max(K, (int)tree[p].size());

	int color = 1;

	for(int c:tree[p]){

		if(visited[c]) continue;

		visited[c] = true;

		colors[c] = color==p_color? ++color: color;

		dfs(c, color++);

	}

}



int main(){

	int N; cin>>N;

	vi C(N-1);

	rp(i, 0, N-1){

		int p,c; cin>>p>>c; p--,c--;

		tree[p].eb(c); tree[c].eb(p);

		C[i] = c;

	}

	visited[0] = true;

	dfs(0, -1);

	cout<< K <<endl;

	for(auto c:C) cout<< colors[c] <<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2854148479533292x):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

#define rp(i,s,e) for(int i=(s);i<(e);++i)



#define NMAX 100000

int K = 1;

struct Edge{ int id, c; };

vector<Edge> Edges[NMAX];

int colors[NMAX];



void dfs(int p, int p_color){

	int color = 1;

	for(auto e:Edges[p]){

		K = max(K, colors[e.id] = color==p_color? ++color: color);

		dfs(e.c, color++);

	}

}



int main(){

	int N; cin>>N;

	rp(id, 0, N-1){

		int p,c; scanf("%d%d",&p,&c); p--,c--;

		Edges[p].push_back({id, c});

	}

	dfs(0, 0);

	printf("%d\n", K);

	rp(i, 0, N-1) printf("%d\n", colors[i]);

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



int n;

vector <pair<int, int>> tree[100010];

vector <int> visited;

set <int> coloured[100010];

vector <int> ans;

int k;



void dfs(int u, int p, int pc)

{

    int c = 1;



    for (auto v: tree[u])

    {

        if (v.first == p)

            continue;



        coloured[u].insert(c);

        coloured[v.first].insert(c);

        

        if (c == pc)

            c++;



        k = max(k, c);

        ans[v.second] = c;

        dfs(v.first, u, c);

        c++;

    }

}



int main()

{

    cin >> n;



    vector <pair<int, int>> edges;



    for (int i = 1; i < n; i++)

    {

        int u, v;



        cin >> u >> v;



        edges.push_back({u, v});



        tree[u].push_back({v, i-1});

        tree[v].push_back({u, i-1});

    }



    ans.assign(n-1, 0);

    dfs(1, 0, 0);



    cout << k << "\n";

    for (int c: ans)

    {

        cout << c << "\n";

    }



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.598068593938619x):
#include <bits/stdc++.h>



using namespace std;



int n;

vector <pair<int, int>> tree[100010];

vector <int> visited;

vector <int> ans;

int k;



void dfs(int u, int p, int pc)

{

    int c = 1;



    for (auto v: tree[u])

    {

        if (v.first == p)

            continue;



        if (c == pc)

            c++;



        k = max(k, c);

        ans[v.second] = c;

        dfs(v.first, u, c);

        c++;

    }

}



int main()

{

    cin >> n;



    vector <pair<int, int>> edges;



    for (int i = 1; i < n; i++)

    {

        int u, v;



        cin >> u >> v;



        edges.push_back({u, v});



        tree[u].push_back({v, i-1});

        tree[v].push_back({u, i-1});

    }



    ans.assign(n-1, 0);

    dfs(1, 0, 0);



    cout << k << "\n";

    for (int c: ans)

    {

        cout << c << "\n";

    }



    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

using namespace std;



typedef pair <int, int> pii;

typedef pair <int, pii> piii;



vector <int> from[100010];

vector <piii> query;

int ans[100010];

int max_d[100010];



void print(int x, int d, int c){

//	cout << x << " " << d << " " << c << endl;

	if (max_d[x] >= d) return ;

	max_d[x] = d;

	if (ans[x] == 0) ans[x] = c;

	for (int i = 0; i < from[x].size(); i++){

		int v = from[x][i];

		print(v, d - 1, c);

	}

}



int main(){

	int n, m, q;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++){

		int u, v;

		scanf("%d%d", &u, &v);

		from[u].push_back(v);

		from[v].push_back(u);

	}

	scanf("%d", &q);

	for (int i = 0; i < q; i++){

		int v, d, c;

		scanf("%d%d%d", &v, &d, &c);

		query.push_back(mp(v, mp(d, c)));

	}

	reverse(query.begin(), query.end());

	memset(max_d, -1, sizeof(max_d));

	for (int i = 0; i < q; i++){

		piii t = query[i];

		print(t.fi, t.se.fi, t.se.se);

	}

	for (int i = 1; i <= n; i++){

		printf("%d\n", ans[i]);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.893132115303195x):
#include<iostream>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

using namespace std;

const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};

const long long llinf=9223372036854775807ll;

const int N=100005;

int n,m,q,tot,fst[N],pnt[N*2],nxt[N*2],ans[N],dp[N][11],a,b;

int main(){

	cin>>n>>m;

	for(int i=1;i<=m;i++)

	{

		cin>>a>>b;

		pnt[++tot]=b;

		nxt[tot]=fst[a];

		fst[a]=tot;

		pnt[++tot]=a;

		nxt[tot]=fst[b];

		fst[b]=tot;

	}

	cin>>q;

	for(int i=1;i<=q;i++)

		cin>>a>>b>>ans[i],dp[a][b]=i;

	for(int i=9;i>=0;i--)

		for(int x=1;x<=n;x++)

		{

			dp[x][i]=max(dp[x][i],dp[x][i+1]);

			for(int j=fst[x];j;j=nxt[j])

				dp[x][i]=max(dp[x][i],dp[pnt[j]][i+1]);

		}

	for(int i=1;i<=n;i++)

		cout<<ans[dp[i][0]]<<'\n';

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define MAXN 100010

int Adj[MAXN],V[MAXN*2],nxt[MAXN*2],c;

void AddEdge(int u,int v)

{

	c++;V[c]=v,nxt[c]=Adj[u];Adj[u]=c;

}

int vis[MAXN],st[MAXN],col[MAXN],dis[MAXN],cnt,sd[MAXN];

void BFS(int s,int d,int C)

{

	if(dis[s]>=d) return;

	dis[s]=d,vis[s]=cnt;

	if(col[s]==0) col[s]=C;

	int l=0,r=0;

	st[r]=s;

	sd[r++]=0;

	while(l<r)

	{

		int u=st[l];

		if(sd[l++]==d) continue;

		int nd=d-sd[l-1]-1;

		for(int i=Adj[u];i;i=nxt[i])

			if(vis[V[i]]!=cnt)

			{

				int v=V[i];

				vis[v]=cnt;

				if(dis[v]>=nd) continue;

				if(col[v]==0) col[v]=C;

				dis[v]=nd;

				st[r]=v;

				sd[r++]=sd[l-1]+1;

			}

	}

}

int n,m,s[MAXN],d[MAXN],C[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	memset(dis,-1,sizeof dis);

	int u,v;

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d",&u,&v);

		AddEdge(u,v);

		AddEdge(v,u);

	}

	scanf("%d",&cnt);

	for(int i=1;i<=cnt;i++)

		scanf("%d%d%d",&s[i],&d[i],&C[i]);

	while(cnt)

	{

		BFS(s[cnt],d[cnt],C[cnt]);

		cnt--;

	}

	for(int i=1;i<=n;i++)

		printf("%d\n",col[i]);

}

// Faster C++ solution for the same problem (measured speedup: 2.988335222655152x):
#include<cstdio>

using namespace std;

const int maxn = 100000;

int n, m, qu;

struct node

{

	int nxt;

	int to;

}edge[2 * maxn + 10];

int head[maxn + 10];

int top;

void add_e(const int &u, const int &v)

{

	++top;

	edge[top].nxt = head[u];

	edge[top].to = v;

	head[u] = top;

	return ;

}



int ques[maxn + 10][3];

bool ok[maxn + 10][20];

int q[maxn + 10][3];

int he, ta;

int color[maxn + 10];



void bfs(const int &p)

{

	++ta;

	q[ta][0] = ques[p][0];

	q[ta][1] = ques[p][1];

	q[ta][2] = ques[p][2];

	while(he != ta)

	{

		++he;

		if(ok[q[he][0]][q[he][1]])

			continue;

		if(color[q[he][0]] == 0)

			color[q[he][0]] = q[he][2];

		for(int i = 0; i <= q[he][1]; ++i)

		{

			ok[q[he][0]][i] = 1;

		}

		if(q[he][1] == 0)

			continue;

		for(int i = head[q[he][0]]; i; i = edge[i].nxt)

		{

			if(ok[edge[i].to][q[he][1] - 1])

				continue;

			++ta;

			q[ta][0] = edge[i].to;

			q[ta][1] = q[he][1] - 1;

			q[ta][2] = q[he][2];

			

		}

	}

	return ;

}



int main()

{

	scanf("%d%d", &n, &m);

	int a, b;

	for(int i = 1; i <= m; ++i)

	{

		scanf("%d%d", &a, &b);

		add_e(a, b);

		add_e(b, a);

	}

	scanf("%d", &qu);

	for(int i = 1; i <= qu; ++i)

	{

		scanf("%d%d%d", &ques[i][0], &ques[i][1], &ques[i][2]);

	}

	for(int i = qu; i > 0; --i)

	{

		he = 0;

		ta = 0;

		bfs(i);

	}

	for(int i = 1; i <= n; ++i)

		printf("%d\n", color[i]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

using namespace std;



typedef pair <int, int> pii;

typedef pair <int, pii> piii;



vector <int> from[100010];

vector <piii> query;

int ans[100010];

int max_d[100010];



void print(int x, int d, int c){

//	cout << x << " " << d << " " << c << endl;

	if (max_d[x] >= d) return ;

	max_d[x] = d;

	if (ans[x] == 0) ans[x] = c;

	for (int i = 0; i < from[x].size(); i++){

		int v = from[x][i];

		print(v, d - 1, c);

	}

}



int main(){

	int n, m, q;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++){

		int u, v;

		scanf("%d%d", &u, &v);

		from[u].push_back(v);

		from[v].push_back(u);

	}

	scanf("%d", &q);

	for (int i = 0; i < q; i++){

		int v, d, c;

		scanf("%d%d%d", &v, &d, &c);

		query.push_back(mp(v, mp(d, c)));

	}

	reverse(query.begin(), query.end());

	memset(max_d, -1, sizeof(max_d));

	for (int i = 0; i < q; i++){

		piii t = query[i];

		print(t.fi, t.se.fi, t.se.se);

	}

	for (int i = 1; i <= n; i++){

		printf("%d\n", ans[i]);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 19.634536855268152x):
#include<cstdio>

using namespace std;

const int maxn = 100000;

int n, m, qu;

struct node

{

	int nxt;

	int to;

}edge[2 * maxn + 10];

int head[maxn + 10];

int top;

void add_e(const int &u, const int &v)

{

	++top;

	edge[top].nxt = head[u];

	edge[top].to = v;

	head[u] = top;

	return ;

}



int ques[maxn + 10][3];

bool ok[maxn + 10][20];

int q[maxn + 10][3];

int he, ta;

int color[maxn + 10];



void bfs(const int &p)

{

	++ta;

	q[ta][0] = ques[p][0];

	q[ta][1] = ques[p][1];

	q[ta][2] = ques[p][2];

	while(he != ta)

	{

		++he;

		if(ok[q[he][0]][q[he][1]])

			continue;

		if(color[q[he][0]] == 0)

			color[q[he][0]] = q[he][2];

		for(int i = 0; i <= q[he][1]; ++i)

		{

			ok[q[he][0]][i] = 1;

		}

		if(q[he][1] == 0)

			continue;

		for(int i = head[q[he][0]]; i; i = edge[i].nxt)

		{

			if(ok[edge[i].to][q[he][1] - 1])

				continue;

			++ta;

			q[ta][0] = edge[i].to;

			q[ta][1] = q[he][1] - 1;

			q[ta][2] = q[he][2];

			

		}

	}

	return ;

}



int main()

{

	scanf("%d%d", &n, &m);

	int a, b;

	for(int i = 1; i <= m; ++i)

	{

		scanf("%d%d", &a, &b);

		add_e(a, b);

		add_e(b, a);

	}

	scanf("%d", &qu);

	for(int i = 1; i <= qu; ++i)

	{

		scanf("%d%d%d", &ques[i][0], &ques[i][1], &ques[i][2]);

	}

	for(int i = qu; i > 0; --i)

	{

		he = 0;

		ta = 0;

		bfs(i);

	}

	for(int i = 1; i <= n; ++i)

		printf("%d\n", color[i]);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

using namespace std;

const int inf=2147483647,dx[]={-1,0,1,0},dy[]={0,-1,0,1};

const long long llinf=9223372036854775807ll;

const int N=100005;

int n,m,q,tot,fst[N],pnt[N*2],nxt[N*2],ans[N],dp[N][11],a,b;

int main(){

	cin>>n>>m;

	for(int i=1;i<=m;i++)

	{

		cin>>a>>b;

		pnt[++tot]=b;

		nxt[tot]=fst[a];

		fst[a]=tot;

		pnt[++tot]=a;

		nxt[tot]=fst[b];

		fst[b]=tot;

	}

	cin>>q;

	for(int i=1;i<=q;i++)

		cin>>a>>b>>ans[i],dp[a][b]=i;

	for(int i=9;i>=0;i--)

		for(int x=1;x<=n;x++)

		{

			dp[x][i]=max(dp[x][i],dp[x][i+1]);

			for(int j=fst[x];j;j=nxt[j])

				dp[x][i]=max(dp[x][i],dp[pnt[j]][i+1]);

		}

	for(int i=1;i<=n;i++)

		cout<<ans[dp[i][0]]<<'\n';

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.043377998421465x):
#include<cstdio>

using namespace std;

const int maxn = 100000;

int n, m, qu;

struct node

{

	int nxt;

	int to;

}edge[2 * maxn + 10];

int head[maxn + 10];

int top;

void add_e(const int &u, const int &v)

{

	++top;

	edge[top].nxt = head[u];

	edge[top].to = v;

	head[u] = top;

	return ;

}



int ques[maxn + 10][3];

bool ok[maxn + 10][20];

int q[maxn + 10][3];

int he, ta;

int color[maxn + 10];



void bfs(const int &p)

{

	++ta;

	q[ta][0] = ques[p][0];

	q[ta][1] = ques[p][1];

	q[ta][2] = ques[p][2];

	while(he != ta)

	{

		++he;

		if(ok[q[he][0]][q[he][1]])

			continue;

		if(color[q[he][0]] == 0)

			color[q[he][0]] = q[he][2];

		for(int i = 0; i <= q[he][1]; ++i)

		{

			ok[q[he][0]][i] = 1;

		}

		if(q[he][1] == 0)

			continue;

		for(int i = head[q[he][0]]; i; i = edge[i].nxt)

		{

			if(ok[edge[i].to][q[he][1] - 1])

				continue;

			++ta;

			q[ta][0] = edge[i].to;

			q[ta][1] = q[he][1] - 1;

			q[ta][2] = q[he][2];

			

		}

	}

	return ;

}



int main()

{

	scanf("%d%d", &n, &m);

	int a, b;

	for(int i = 1; i <= m; ++i)

	{

		scanf("%d%d", &a, &b);

		add_e(a, b);

		add_e(b, a);

	}

	scanf("%d", &qu);

	for(int i = 1; i <= qu; ++i)

	{

		scanf("%d%d%d", &ques[i][0], &ques[i][1], &ques[i][2]);

	}

	for(int i = qu; i > 0; --i)

	{

		he = 0;

		ta = 0;

		bfs(i);

	}

	for(int i = 1; i <= n; ++i)

		printf("%d\n", color[i]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

using namespace std;



typedef pair <int, int> pii;

typedef pair <int, pii> piii;



vector <int> from[100010];

vector <piii> query;

int ans[100010];

int max_d[100010];



void print(int x, int d, int c){

//	cout << x << " " << d << " " << c << endl;

	if (max_d[x] >= d) return ;

	max_d[x] = d;

	if (ans[x] == 0) ans[x] = c;

	for (int i = 0; i < from[x].size(); i++){

		int v = from[x][i];

		print(v, d - 1, c);

	}

}



int main(){

	int n, m, q;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++){

		int u, v;

		scanf("%d%d", &u, &v);

		from[u].push_back(v);

		from[v].push_back(u);

	}

	scanf("%d", &q);

	for (int i = 0; i < q; i++){

		int v, d, c;

		scanf("%d%d%d", &v, &d, &c);

		query.push_back(mp(v, mp(d, c)));

	}

	reverse(query.begin(), query.end());

	memset(max_d, -1, sizeof(max_d));

	for (int i = 0; i < q; i++){

		piii t = query[i];

		print(t.fi, t.se.fi, t.se.se);

	}

	for (int i = 1; i <= n; i++){

		printf("%d\n", ans[i]);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.817543441165315x):
#include <bits/stdc++.h>

#define sc(x) scanf("%d", &x)

#define pr(x) printf("%d\n", x)

#define lowbit(x) (x & -x)

#define ll long long

#define N 100010

using namespace std;

int n, m, col[N], tot = 0, head[N], maxx[N], q;

struct Xiao

{

	int next, to;

}e[N * 2];

struct Wang

{

	int v, d, c;

}qvq[N];

inline void add(int x, int y)

{

	e[++tot].next = head[x];

	e[tot].to = y;

	head[x] = tot;

}

inline void dfs(int d, int sc, int x, int fa)

{

	if (d <= maxx[x]) return;

	maxx[x] = d;

	if (col[x] == 0) col[x] = sc;

	for (int i = head[x]; i; i = e[i].next)

	{

		int y = e[i].to;

		if (y == fa) continue;

		dfs(d - 1, sc, y, x);

	}

}

int main()

{

	sc(n);

	sc(m);

	for (int i = 1; i <= m; i++)

	{

		int a, b;

		sc(a);

		sc(b);

		add(a, b);

		add(b, a);

	}

	sc(q);

	for (int i = 1; i <= q; i++)

	{

		sc(qvq[i].v);

		sc(qvq[i].d);

		sc(qvq[i].c);

	}

	memset(maxx, -1, sizeof maxx);

	for (int i = q; i >= 1; i--)

	dfs(qvq[i].d, qvq[i].c, qvq[i].v, 0);

	for (int i = 1; i <= n; i++)

	printf("%d\n", col[i]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define regi register int

int n,m,q;

int pos[200001],d[200001],c[200001];

int color[200001][20];

std::vector<int>e[300001];

inline int read(){int r=0,c=0,w;for(;!isdigit(c=getchar());r=c);for(w=c^48;isdigit(c=getchar());w=w*10+(c^48));return r^45?w:-w;}

void dfs(int x, int d, int c){

	if(color[x][d]||d==-1)

	  return;

	color[x][d]=c;

	for(regi i=0;i<e[x].size();++i) {

		regi y=e[x][i];

		dfs(y,d-1,c);

	}

	dfs(x,d-1,c);

}

main(){

  n=read();

  m=read();

	for(regi i=1,x,y;i<=m;++i){

		x=read();

		y=read();

		e[x].push_back(y);

		e[y].push_back(x);

	}

	q=read();

	for(regi i=1;i<=q;++i){

		pos[i]=read();

		d[i]=read();

		c[i]=read();

	}

	for(regi i=q;i;--i)

		dfs(pos[i],d[i],c[i]);

	for(regi i=1;i<=n;++i)

		printf("%d\n",color[i][0]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.73005816865259x):
#include <bits/stdc++.h>

#define sc(x) scanf("%d", &x)

#define pr(x) printf("%d\n", x)

#define lowbit(x) (x & -x)

#define ll long long

#define N 100010

using namespace std;

int n, m, col[N], tot = 0, head[N], maxx[N], q;

struct Xiao

{

	int next, to;

}e[N * 2];

struct Wang

{

	int v, d, c;

}qvq[N];

inline void add(int x, int y)

{

	e[++tot].next = head[x];

	e[tot].to = y;

	head[x] = tot;

}

inline void dfs(int d, int sc, int x, int fa)

{

	if (d <= maxx[x]) return;

	maxx[x] = d;

	if (col[x] == 0) col[x] = sc;

	for (int i = head[x]; i; i = e[i].next)

	{

		int y = e[i].to;

		if (y == fa) continue;

		dfs(d - 1, sc, y, x);

	}

}

int main()

{

	sc(n);

	sc(m);

	for (int i = 1; i <= m; i++)

	{

		int a, b;

		sc(a);

		sc(b);

		add(a, b);

		add(b, a);

	}

	sc(q);

	for (int i = 1; i <= q; i++)

	{

		sc(qvq[i].v);

		sc(qvq[i].d);

		sc(qvq[i].c);

	}

	memset(maxx, -1, sizeof maxx);

	for (int i = q; i >= 1; i--)

	dfs(qvq[i].d, qvq[i].c, qvq[i].v, 0);

	for (int i = 1; i <= n; i++)

	printf("%d\n", col[i]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



const int N = 300001;

int n, m, tot = 0, q;

int head[N], Next[N], ver[N], num[N];

int ans[N][20] = {};

struct edge{

	int x, y, z;

}a[N];



vector <int> vis[N];



void dfs(int x,int y,int z) {

	if (y == -1) return;

	if (ans[x][y]) return;

	ans[x][y] = z;

	for (int i=0;i<vis[x].size();++i) dfs(vis[x][i], y-1, z);

}



int main() {

	scanf("%d%d",&n,&m);

	for (int i=1;i<=m;i++) {

		int x, y;

		scanf("%d%d",&x,&y);

		vis[x].push_back(y);

		vis[y].push_back(x);

	}

	for (int i=1;i<=n;i++) vis[i].push_back(i);

	scanf("%d",&q);

	for (int i=1;i<=q;i++) {

		int x, y, z;

		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);

	}

	for (int i=q;i;--i) dfs(a[i].x, a[i].y, a[i].z);

	for (int i=1;i<=n;i++) printf("%d\n",ans[i][0]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.735171283305617x):
#include <bits/stdc++.h>

#define sc(x) scanf("%d", &x)

#define pr(x) printf("%d\n", x)

#define lowbit(x) (x & -x)

#define ll long long

#define N 100010

using namespace std;

int n, m, col[N], tot = 0, head[N], maxx[N], q;

struct Xiao

{

	int next, to;

}e[N * 2];

struct Wang

{

	int v, d, c;

}qvq[N];

inline void add(int x, int y)

{

	e[++tot].next = head[x];

	e[tot].to = y;

	head[x] = tot;

}

inline void dfs(int d, int sc, int x, int fa)

{

	if (d <= maxx[x]) return;

	maxx[x] = d;

	if (col[x] == 0) col[x] = sc;

	for (int i = head[x]; i; i = e[i].next)

	{

		int y = e[i].to;

		if (y == fa) continue;

		dfs(d - 1, sc, y, x);

	}

}

int main()

{

	sc(n);

	sc(m);

	for (int i = 1; i <= m; i++)

	{

		int a, b;

		sc(a);

		sc(b);

		add(a, b);

		add(b, a);

	}

	sc(q);

	for (int i = 1; i <= q; i++)

	{

		sc(qvq[i].v);

		sc(qvq[i].d);

		sc(qvq[i].c);

	}

	memset(maxx, -1, sizeof maxx);

	for (int i = q; i >= 1; i--)

	dfs(qvq[i].d, qvq[i].c, qvq[i].v, 0);

	for (int i = 1; i <= n; i++)

	printf("%d\n", col[i]);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

using namespace std;



typedef pair <int, int> pii;

typedef pair <int, pii> piii;



vector <int> from[100010];

vector <piii> query;

int ans[100010];

int max_d[100010];



void print(int x, int d, int c){

//	cout << x << " " << d << " " << c << endl;

	if (max_d[x] >= d) return ;

	max_d[x] = d;

	if (ans[x] == 0) ans[x] = c;

	for (int i = 0; i < from[x].size(); i++){

		int v = from[x][i];

		print(v, d - 1, c);

	}

}



int main(){

	int n, m, q;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++){

		int u, v;

		scanf("%d%d", &u, &v);

		from[u].push_back(v);

		from[v].push_back(u);

	}

	scanf("%d", &q);

	for (int i = 0; i < q; i++){

		int v, d, c;

		scanf("%d%d%d", &v, &d, &c);

		query.push_back(mp(v, mp(d, c)));

	}

	reverse(query.begin(), query.end());

	memset(max_d, -1, sizeof(max_d));

	for (int i = 0; i < q; i++){

		piii t = query[i];

		print(t.fi, t.se.fi, t.se.se);

	}

	for (int i = 1; i <= n; i++){

		printf("%d\n", ans[i]);

	}

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.1135511353752097x):
#include<bits/stdc++.h>



typedef long long ll;



const int maxn = 1e5+10;



int cor[maxn][14], qwq[maxn], qaq[maxn], c[maxn];



std::vector <int> pb[maxn];



int n, m, a, b, q;



void l(int v1, int deep, int dd)

{

    if(deep==-1)  return;

    if(cor[v1][deep] ) return;

    cor[v1][deep]=dd;

    for(int i =0;i<pb[v1].size();i++)

        l(pb[v1][i], deep-1, dd);

}



int read()

{

	int x=0, ch= getchar(), f=1;

	while(!isdigit(ch)){ if(ch == '-')f = -1, ch = getchar();}

	while(isdigit(ch)) x = x *10 + ch-'0', ch = getchar();

	return x * f;

} 



int main()

{

    n=read(), m=read();

    for(int i=1;i<=m;i++) a=read(), b=read(), pb[a].push_back(b), pb[b].push_back(a);

    for(int i=1;i<=n;i++) pb[i].push_back(i);

    q=read();

    for(int i=1;i<=q;i++) qwq[i]=read(), qaq[i] = read(), c[i] = read();

    for(int i=q;i>=1;i--)  l(qwq[i], qaq[i], c[i]);

    for(int i=1;i<=n;i++) std::cout<<cor[i][0]<<std::endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define regi register int

int n,m,q;

int pos[200001],d[200001],c[200001];

int color[200001][20];

std::vector<int>e[300001];

inline int read(){int r=0,c=0,w;for(;!isdigit(c=getchar());r=c);for(w=c^48;isdigit(c=getchar());w=w*10+(c^48));return r^45?w:-w;}

void dfs(int x, int d, int c){

	if(color[x][d]||d==-1)

	  return;

	color[x][d]=c;

	for(regi i=0;i<e[x].size();++i) {

		regi y=e[x][i];

		dfs(y,d-1,c);

	}

	dfs(x,d-1,c);

}

main(){

  n=read();

  m=read();

	for(regi i=1,x,y;i<=m;++i){

		x=read();

		y=read();

		e[x].push_back(y);

		e[y].push_back(x);

	}

	q=read();

	for(regi i=1;i<=q;++i){

		pos[i]=read();

		d[i]=read();

		c[i]=read();

	}

	for(regi i=q;i;--i)

		dfs(pos[i],d[i],c[i]);

	for(regi i=1;i<=n;++i)

		printf("%d\n",color[i][0]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.6598574507673693x):
#include<bits/stdc++.h>



typedef long long ll;



const int maxn = 1e5+10;



int cor[maxn][14], qwq[maxn], qaq[maxn], c[maxn];



std::vector <int> pb[maxn];



int n, m, a, b, q;



void l(int v1, int deep, int dd)

{

    if(deep==-1)  return;

    if(cor[v1][deep] ) return;

    cor[v1][deep]=dd;

    for(int i =0;i<pb[v1].size();i++)

        l(pb[v1][i], deep-1, dd);

}



int read()

{

	int x=0, ch= getchar(), f=1;

	while(!isdigit(ch)){ if(ch == '-')f = -1, ch = getchar();}

	while(isdigit(ch)) x = x *10 + ch-'0', ch = getchar();

	return x * f;

} 



int main()

{

    n=read(), m=read();

    for(int i=1;i<=m;i++) a=read(), b=read(), pb[a].push_back(b), pb[b].push_back(a);

    for(int i=1;i<=n;i++) pb[i].push_back(i);

    q=read();

    for(int i=1;i<=q;i++) qwq[i]=read(), qaq[i] = read(), c[i] = read();

    for(int i=q;i>=1;i--)  l(qwq[i], qaq[i], c[i]);

    for(int i=1;i<=n;i++) std::cout<<cor[i][0]<<std::endl;

    return 0;

}