stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main()

{

	int n,m,a[200001];

	bool b1[200001],b2[200001];

	cin>>n>>m;

	memset(b1,1,sizeof(b1));

	memset(b2,1,sizeof(b2));

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

		cin>>a[i];

		b1[a[i]]=false;

	}

	for(int i=m;i>=1;i--){

		if (b2[a[i]]==true){

			cout<<a[i]<<endl;

			b2[a[i]]=0;

		}

	}

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

		if (b1[i]==true) cout<<i<<endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

bool flag[250000];

int a[250000];

int main()

{

	memset(flag,1,sizeof(flag));

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

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

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

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

		if(flag[a[i]])

		printf("%d\n",a[i]),flag[a[i]]=0;

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

		if(flag[i])

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

		return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<memory.h>

using namespace std;

bool vis[200005];

bool vis1[200005];

int a[200005];

int main()

{

    memset(vis,0,sizeof(vis));

    memset(vis1,0,sizeof(vis1));

    int n,m;

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

    int j=0;

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

    {

        int b;

        scanf("%d",&b);

        vis[b]=1;

        a[j++]=b;

    }

    while(j--)

    {

        if(vis1[a[j]]==0)

        {

            printf("%d\n",a[j]);

            vis1[a[j]]=1;

        }

    } 

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

    {

        if(vis[i]==0) 

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

    }

    return 0;

} 

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

bool flag[250000];

int a[250000];

int main()

{

	memset(flag,1,sizeof(flag));

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

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

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

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

		if(flag[a[i]])

		printf("%d\n",a[i]),flag[a[i]]=0;

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

		if(flag[i])

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

		return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



int main()

{

    int n,m;

    cin>>n>>m;\

    int mark[n+1],check[n+1];

    memset(mark,0,sizeof(mark));

    memset(check,0,sizeof(check));

    vector<int>v;

    while(m--)

    {

        int p;

        cin>>p;

        v.push_back(p);

    }

    for(int i=v.size()-1;i>=0;i--)

    {

        if(check[v[i]]==0)

        {

            check[v[i]]=1;

            cout<<v[i]<<endl;

        }

        mark[v[i]]=1;

    }

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

    {

        if(mark[i]==0)

            cout<<i<<endl;

    }

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

bool flag[250000];

int a[250000];

int main()

{

	memset(flag,1,sizeof(flag));

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

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

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

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

		if(flag[a[i]])

		printf("%d\n",a[i]),flag[a[i]]=0;

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

		if(flag[i])

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

		return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define N 1000002

#define pb push_back

int hit[N], a[N];

int main(){

    int n, m;

    cin >> n >> m;

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

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

    }

    for (int i=m; i>=1; i--){

        int x = a[i];

        if (hit[x] == 0) printf("%d\n", x);

        hit[x] = 1;

    }

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

        if (hit[i] == 0) printf("%d\n", i);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

bool flag[250000];

int a[250000];

int main()

{

	memset(flag,1,sizeof(flag));

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

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

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

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

		if(flag[a[i]])

		printf("%d\n",a[i]),flag[a[i]]=0;

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

		if(flag[i])

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

		return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

using namespace std;



int N, M;//?度? n 的序列,有 m 个操作

int F[205000];

bool Jud[205000];



int main()

{

    cin >> N >> M;

    memset(Jud, true, sizeof(Jud));

    for(int i = 1; i <= M; i++)    cin >> F[i];

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

        if(Jud[F[i]] == true){

            Jud[F[i]] = false;

            cout << F[i] << endl;

        }

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

        if(Jud[i] == true)

            cout << i << endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

bool flag[250000];

int a[250000];

int main()

{

	memset(flag,1,sizeof(flag));

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

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

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

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

		if(flag[a[i]])

		printf("%d\n",a[i]),flag[a[i]]=0;

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

		if(flag[i])

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

		return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



constexpr ll N=100001;

vector <ll> tree[N];

vector <ll> exam (N,0);

map<pair<ll,ll>,ll> I;

vector <pair <ll,ll>> v(N);



ll maxcol=0;

void dfs(pair <int,int> now){

  ll ncol=1;



  for (auto i:tree[now.first]){

    if (exam[i]) continue;

    if (ncol==now.second) ncol++;

    exam[i]=ncol;

    I[make_pair(now.first,i)]=I[make_pair(i,now.first)]=ncol;

    maxcol=max(maxcol,ncol);



    dfs(make_pair(i,ncol));

    ncol++;

  }



}



  int main(){

    ll n;

    cin>>n;

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

      ll a,b;

      cin>>a>>b;

      tree[a].emplace_back(b);

      tree[b].emplace_back(a);

      v[i]=make_pair(a,b);

    }

    exam[1]=N;



    dfs(make_pair(1,0));





    cout<<maxcol<<endl;

    for (ll i=0;i<n-1; i++){

      cout<<I[v[i]]<<endl;

    }



  }


// Optimized solution to the same problem (faster):


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> l_l;

typedef pair<int, int> P;

#define rep(i,n) for(ll i=0;i<n;++i)

const int INF=1001001001;

int main(){

  ll n;

  cin>>n;

  vector<vector<P>> g(n);

  vector<int> cn(n,INF);

  vector<int> ce(n-1,INF);

  rep(i,n-1){

    int a1,b1;

    cin>>a1>>b1;

    a1--;b1--;

    g[a1].push_back(make_pair(b1,i));

    g[b1].push_back(make_pair(a1,i));



  }





queue <int> q;

q.push(0);

int maxc=0;

while (!q.empty()){

  int now=q.front();

  q.pop();

  int cnt=1;



  for(auto to:g[now]){

    int nod=to.first;

    int edg=to.second;



    if (ce[edg]!=INF)continue;

    if (cn[now]==cnt) cnt++;

    ce[edg]=cnt;

    cn[nod]=cnt;

    maxc=max(maxc,cnt);

    q.push(nod);

    cnt++;

  }



}

cout<<maxc<<endl;

rep(i,n-1){

  cout<<ce[i]<<endl;

}













  }


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

typedef long long int ll;

typedef pair<int, int> P;



int n;

vector<vector<int>> graph(101010, vector<int>(0));

vector<int> colors(101010);

map<P, int> edge_num;

int mc = 0;



void dfs(int a, int pa, int pc){

  int c = 1;

  for(int x : graph.at(a)){

    if(x == pa) continue;

    if(c == pc) c++;

    colors.at(edge_num[P(x, a)]) = c;

    dfs(x, a, c);

    c++;

  }

  mc = max(c - 1, mc);

}



int main(){

  cin >> n;

  rep(i, n - 1){

    int a, b;

    cin >> a >> b;

    graph.at(a).emplace_back(b);

    graph.at(b).emplace_back(a);

    edge_num[P(a, b)] = edge_num[P(b, a)] = i;

  }

  

  dfs(1, 0, 0);

  

  cout << mc << endl;

  rep(i, n - 1) cout << colors[i] << endl;

  

  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep2(i,m,n) for (int i = (m); i < (n); ++i)

#define rep(i,n) rep2(i,0,n)

typedef long long int ll;

typedef long double ld;

typedef pair<int, int> P;

template<typename T> struct V : vector<T> { using vector<T>::vector; };

V() -> V<int>;

V(size_t) -> V<int>;

template<typename T> V(size_t, T) -> V<T>;

template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }

template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }

template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }

struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}

template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

const int INF = 1<<30;

const ll LINF = 1LL<<61;



vector<vector<P>> G;

vector<int> ans;



void func(int cur, int p, int c)

{

    int nc = 1;

    for(auto [to, e]:G[cur])

    {

        if(to == p) continue;

        if(nc == c) nc++;

        ans[e] = nc;

        func(to, cur, nc);

        nc++;

    }

    return;

}



int main()

{

    int n;

    cin >> n;

    G.assign(n, vector<P>(0));

    ans.assign(n-1, 0);

    rep(i,n-1)

    {

        int u, v;

        cin >> u >> v;

        --u; --v;

        G[u].emplace_back(v, i);

        G[v].emplace_back(u, i);

    }

    func(0, -1, 0);

    ll ans1 = 0;

    for(auto x:ans) chmax(ans1, x);

    cout << ans1 << endl;

    for(auto x:ans) cout << x << "\n";

    



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// 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;

}

// Optimized solution to the same problem (faster):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

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



const int cm = 1<<17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha(){

	if(ci-cn == cm){ fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}



inline int getint(){

	int A = 0;

	if(ci-cn+16 > cm) while((ct=getcha()) >= '0') A = A*10 + ct - '0';

	else while ((ct=*ci++) >= '0') A = A*10 + ct - '0';

	return A;

}



const int dm = 1<<20;

char dn[dm], *di = dn;

inline void putint(int x){

	char c[10];

	int d; for(d=0; x; d++, x/=10) c[d] = x%10 + '0';

	for(int i=d-1; i>=0; --i) *di++ = c[i];

	*di++ = '\n';

}



int main(){

	int N = getint();

	int G[N], C[N-1];

	rp(i, 0, N-1){

		int p = getint(); C[i] = getint();

		G[--C[i]] = p-1;

	}



	int K = 1;

	int pre_colors[N]; rp(i, 0, N) pre_colors[i] = 0;



	rp(c, 1, N){

		int p = G[c];

		int color = pre_colors[p] + 1;

		pre_colors[p] = G[c] = color==G[p]? ++color: color;

		K = max(K, color);

	}



	putint(K);

	for(int c:C) putint(G[c]);

	fwrite(dn, 1, di - dn, stdout);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

#define NMAX 100000



int K = 1;

vector<vector<int>> tree(NMAX);

int colors[NMAX];



void dfs(int p, int p_color){

	int color = 1;

	for(int c:tree[p]){

		if(colors[c]) continue;

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

		K = max(K, color);

		dfs(c, color++);

	}

}



int main(){

	int N; cin>>N;

	int C[N-1];

	for(int i=0; i<N-1; ++i){

		int p; scanf("%d%d", &p, C+i); p--,C[i]--;

		tree[p].push_back(C[i]);

		tree[C[i]].push_back(p);

	}

	colors[0] = NMAX;

	dfs(0, -1);

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

	for(int c:C) printf("%d\n", colors[c]);

}

// Optimized solution to the same problem (faster):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

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



const int cm = 1<<17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha(){

	if(ci-cn == cm){ fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}



inline int getint(){

	int A = 0;

	if(ci-cn+16 > cm) while((ct=getcha()) >= '0') A = A*10 + ct - '0';

	else while ((ct=*ci++) >= '0') A = A*10 + ct - '0';

	return A;

}



const int dm = 1<<20;

char dn[dm], *di = dn;

inline void putint(int x){

	char c[10];

	int d; for(d=0; x; d++, x/=10) c[d] = x%10 + '0';

	for(int i=d-1; i>=0; --i) *di++ = c[i];

	*di++ = '\n';

}



int main(){

	int N = getint();

	int G[N], C[N-1];

	rp(i, 0, N-1){

		int p = getint(); C[i] = getint();

		G[--C[i]] = p-1;

	}



	int K = 1;

	int pre_colors[N]; rp(i, 0, N) pre_colors[i] = 0;



	rp(c, 1, N){

		int p = G[c];

		int color = pre_colors[p] + 1;

		pre_colors[p] = G[c] = color==G[p]? ++color: color;

		K = max(K, color);

	}



	putint(K);

	for(int c:C) putint(G[c]);

	fwrite(dn, 1, di - dn, stdout);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

#define NMAX 100000



int K = 1;

vector<vector<int>> tree(NMAX);

int colors[NMAX];



void dfs(int p, int p_color){

	int color = 1;

	for(int c:tree[p]){

		if(colors[c]) continue;

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

		K = max(K, color);

		dfs(c, color++);

	}

}



int main(){

	int N; cin>>N;

	int C[N-1];

	for(int i=0; i<N-1; ++i){

		int p; scanf("%d%d", &p, C+i); p--,C[i]--;

		tree[p].push_back(C[i]);

	}

	colors[0] = NMAX;

	dfs(0, -1);

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

	for(int c:C) printf("%d\n", colors[c]);

}

// Optimized solution to the same problem (faster):
// D - Coloring Edges on Tree

#include <bits/stdc++.h>

using namespace std;

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



const int cm = 1<<17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha(){

	if(ci-cn == cm){ fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}



inline int getint(){

	int A = 0;

	if(ci-cn+16 > cm) while((ct=getcha()) >= '0') A = A*10 + ct - '0';

	else while ((ct=*ci++) >= '0') A = A*10 + ct - '0';

	return A;

}



const int dm = 1<<20;

char dn[dm], *di = dn;

inline void putint(int x){

	char c[10];

	int d; for(d=0; x; d++, x/=10) c[d] = x%10 + '0';

	for(int i=d-1; i>=0; --i) *di++ = c[i];

	*di++ = '\n';

}



int main(){

	int N = getint();

	int G[N], C[N-1];

	rp(i, 0, N-1){

		int p = getint(); C[i] = getint();

		G[--C[i]] = p-1;

	}



	int K = 1;

	int pre_colors[N]; rp(i, 0, N) pre_colors[i] = 0;



	rp(c, 1, N){

		int p = G[c];

		int color = pre_colors[p] + 1;

		pre_colors[p] = G[c] = color==G[p]? ++color: color;

		K = max(K, color);

	}



	putint(K);

	for(int c:C) putint(G[c]);

	fwrite(dn, 1, di - dn, stdout);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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]);

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem: