/<> 10838 (LCA w/out binary jumping)

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <numeric>
#include <iomanip>
using namespace std;
#define pii pair<int , int>
#define ll long long
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
const long long dl[2] = {1, -1};
const long long MOD = 1000000007;
const long long MAXN = 100005;

int N, K;
int par[MAXN];
int color[MAXN];
int depth[MAXN];
int visited[MAXN];

int LCA(int x, int y, int k){
    for(int i = 0; i < 1005; i++){
        visited[x] = k;
        if(x == 0) {
            break;
        }
        x = par[x];
    }
    for(int i = 0; i < 1005; i++){
        if(visited[y] == k or y == 0){
            return y;
        }
        y = par[y];
    }
    return y;
}

int main() {
    FAST;
    cin >> N >> K;
    memset(depth, 2, sizeof(depth));
    depth[0] = 1;
    for(int r, x, y, z, k = 1; k <= K; k++){
        cin >> r;
        if(r == 1){
            cin >> x >> y >> z;
            int lca = LCA(x, y, k);
            while(x != lca){
                color[x] = z;
                x = par[x];
            }
            while(y != lca){
                color[y] = z;
                y = par[y];
            }
        }
        else if(r == 2){
            cin >> x >> y;
            par[x] = y;
        }
        else{
            cin >> x >> y;
            int lca = LCA(x, y, k);
            set<int> colors;
            while(x != lca){
                colors.insert(color[x]);
                x = par[x];
            }
            while(y != lca){
                colors.insert(color[y]);
                y = par[y];
            }
            cout << colors.size() << "\n";
        }
    }
}

/*
6 8
2 1 3
2 5 3
1 5 4 8
3 4 5
2 3 4
1 0 3 7
3 2 5
3 4 2
 */