#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
struct UnionFind{
  vector<int> par, rank, sz, esz;
  UnionFind(int n){
    par.assign(n, 0);
    rank.assign(n, 0);
    sz.assign(n, 1);
    esz.assign(n, 0);
    rep(i, n) par[i] = i;
  }
  int find(int x){
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void merge(int x, int y){
    x = find(x);
    y = find(y);
    if(rank[x] < rank[y]) swap(x, y);
    esz[x]++;
    if(x == y) return;
    if(rank[x] == rank[y]) rank[x]++;
    par[y] = x;
    sz[x] += sz[y];
    esz[x] += esz[y];
  }
};
int main(){
  int n, res=0;
  cin >> n;
  UnionFind uf(pow(10, 6));
  for(int i=0; i<n; i++){
    int a, b;
    cin >> a >> b;
    uf.merge(a,b);
  }
  for(int i=0; i<pow(10,6); i++){
    if(uf.par[i] == i){
      res += min(uf.sz[i], uf.esz[i]);
    }
  }
  cout << res << endl;
}
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
il int read()
{
	int re=0,k=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}
il void write(int x)
{
	if(x<0) return putchar('-'),write(-x),void();
	if(x<10)return putchar(x+48),void();
	return write(x/10),putchar(x%10+48),void();
}
int col[200005],l,n,m;
int fa[200005],head[200005],tot;
int find(int x)
{
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
struct ss{
	int node,nxt,w;
}e[400005];
void add(int u,int v,int w)
{
	e[++tot].nxt=head[u];
	head[u]=tot;
	e[tot].node=v;
	e[tot].w=w;
}

void dfs(int x,int fa,int c)
{
//	cerr<<x
	col[x]=c;
	for(rg int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].node;
		if(y==fa)continue;
		if(c==e[i].w)
		{
			dfs(y,x,c%n+1);
		}
		else
		{
			dfs(y,x,e[i].w);
		}
	}
}
signed main()
{
	n=read();m=read();
	for(rg int i=1;i<=n;i++)
		fa[i]=i;
	for(rg int i=1,a,b,c;i<=m;i++)
	{
		a=read();b=read();c=read();
		int x=find(a);
		int y=find(b);
		if(x==y)continue;
		fa[x]=y;
		add(a,b,c);
		add(b,a,c);
	}
	
	dfs(1,0,1);
	for(rg int i=1;i<=n;i++)
		write(col[i]),puts("");
}