It is sufficient to manage the following two values for each train:

• the index of train jointed in front of itself;
• the index of train jointed in back of itself.

For each query of \(c_i = 1,2\), one can update the values above in an \(O(1)\) time.
For each query of \(c_i = 3\), one can process it with a naive implementation, due to the constraints that “the sum of numbers of indices of trains to output is at most \(10^6\).”

Therefore, the problem has been solved.

A sample code in C++ follows.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
    ll n,q;cin>>n>>q;
    ll nil=-1;
    vector<ll>front(n+1,nil); // front[i] := The train jointed in front of Train i, or nil if there's no such train.
    vector<ll>back(n+1,nil);  // back[i]  := The train jointed in back of Train i, or nil if there's no such train.
    while(q--){
        ll c;cin>>c;
        if(c==1){
            ll x,y;cin>>x>>y;
            back[x] = y;
            front[y] = x;
        }else if(c==2){
            ll x,y;cin>>x>>y;
            back[x] = nil;
            front[y] = nil;
        }else{
            ll x;cin>>x;
            while(front[x] != nil){
                x = front[x]; // Move to the first of the connected component of x
            }
            vector<ll>ans;
            while(x != nil){
                ans.push_back(x);
                x = back[x];
            }
            cout<<ans.size()<<" ";
            for(ll i=0;i<=(int)ans.size()-1;i++){
                cout<<ans[i];
                if(i!=(int)ans.size()-1)cout<<" ";
                else cout<<endl;
            }
        }
    }

    return 0;
}