D - Pigeon Swap
Source: atcoder
Difficulty: 350

Problem Statement
There are
N
pigeons labeled
1, 2, \ldots, N
and
N
nests labeled
1, 2, \ldots, N
.
Initially, pigeon
i
(1 \leq i \leq N)
is in nest
i
.
You will perform
Q
operations on these pigeons.
There are three types of operations:
Type
1
: You are given integers
a
and
b
(1 \leq a \leq N, 1 \leq b \leq N)
. Take pigeon
a
out of its current nest and move it to nest
b
.
Type
2
: You are given integers
a
and
b
(1 \leq a < b \leq N)
. Move all pigeons in nest
a
to nest
b
, and move all pigeons in nest
b
to nest
a
. These two moves happen simultaneously.
Type
3
: You are given an integer
a
(1 \leq a \leq N)
. Pigeon
a
reports the label of the nest it is currently in.
Print the result of each Type
3
operation in the order the operations are given.
Constraints
1 \leq N \leq 10^6
1 \leq Q \leq 3 \times 10^5
Every operation is of Type
1
,
2
, or
3
.
All operations are valid according to the problem statement.
There is at least one Type
3
operation.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
Q
op _ 1
op _ 2
\vdots
op _ Q
Here,
op _ i
on the line
i+1
represents the
i
-th operation in one of the following formats.
If the
i
-th operation is of Type
1
,
op _ i
is in the following format:
1
a
b
This corresponds to a Type
1
operation with the given integers being
a
and
b
.
If the
i
-th operation is of Type
2
,
op _ i
is in the following format:
2
a
b
This corresponds to a Type
2
operation with the given integers being
a
and
b
.
If the
i
-th operation is of Type
3
,
op _ i
is in the following format:
3
a
This corresponds to a Type
3
operation with the given integer being
a
.
Output
Let the number of Type
3
operations be
q
. Print
q
lines. The
i
-th line
(1 \leq i \leq q)
should contain the nest number reported in the
i
-th Type
3
operation.
Sample Input 1
6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2
Sample Output 1
4
5
2
5
In the operations given, the pigeons move as shown in the figure below:
The nest numbers to be reported for the Type
3
operations are
4,5,2,5
. Print
4
,
5
,
2
,
5
on separate lines.
Sample Input 2
1 2
1 1 1
3 1
Sample Output 2
1
The destination nest of a Type
1
operation may be the same as the nest the pigeon is currently in.
Sample Input 3
30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8
Sample Output 3
3
15
7

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

#define ll long long
#define endl "\n"
using namespace std;
const int N = 1e6 + 5;
int n, q;
int cur[N]; // i鸟所在巢穴
int g[N];   // i位置的巢穴
int id[N];  // i巢穴的位置
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cur[i] = i;
        g[i] = i;
        id[i] = i;
    }
    while (q--)
    {
        int op, x, y;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            cur[x] = g[y];
        }
        else if (op == 2)
        {
            cin >> x >> y;
            id[g[x]] = y;
            id[g[y]] = x;
            swap(g[x], g[y]);
        }
        else if (op == 3)
        {
            cin >> x;
            cout << id[cur[x]] << endl;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	if len(s) == 0 {
		return
	}
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()
	N, Q := getI(), getI()

	p := make([]int, N) // 鳩の場所
	pos2idx := make([]int, N)
	idx2pos := make([]int, N)

	for i := 0; i < N; i++ {
		p[i] = i
		pos2idx[i] = i
		idx2pos[i] = i
	}

	for qi := 0; qi < Q; qi++ {
		op := getI()
		switch op {
		case 1:
			a, b := getI()-1, getI()-1
			p[a] = pos2idx[b] // 箱に移動する
		case 2:
			a, b := getI()-1, getI()-1
			pos2idx[a], pos2idx[b] = pos2idx[b], pos2idx[a]
			idx2pos[pos2idx[a]] = a
			idx2pos[pos2idx[b]] = b
		case 3:
			a := getI() - 1
			nb := idx2pos[p[a]]
			out(nb + 1)
		}
	}

}

Java solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static StringBuffer ret = new StringBuffer();
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//	static int T = 1;
	static StringTokenizer st;
	static int N, Q, nest_idx_label[], nest_label_idx[], pigeon_nest_idx[];

	public static void main(String[] args) throws Exception {
//		T = Integer.parseInt(br.readLine());
//		for (int i = 0; i < T; i++)
		problem();

		System.out.print(ret.toString());
	}

	@Override
	public void finalize() throws Exception {
		br.close();
	}

	private static void problem() throws Exception {
		setInput();
		solve();
	}

	private static void setInput() throws Exception {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		nest_idx_label = new int[N + 1];
		nest_label_idx = new int[N + 1];
		pigeon_nest_idx = new int[N + 1];
	}

	private static void solve() throws Exception {
		for (int i = 1; i <= N; i++) {
			nest_idx_label[i] = i;
			nest_label_idx[i] = i;
			pigeon_nest_idx[i] = i;
		}
		int op, a, b, temp;
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			op = Integer.parseInt(st.nextToken());
			if (op == 1) {
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				pigeon_nest_idx[a] = nest_label_idx[b];
			} else if (op == 2) {
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				nest_idx_label[nest_label_idx[a]] = b;
				nest_idx_label[nest_label_idx[b]] = a;
				temp = nest_label_idx[b];
				nest_label_idx[b] = nest_label_idx[a];
				nest_label_idx[a] = temp;
			} else {
				a = Integer.parseInt(st.nextToken());
				ret.append(nest_idx_label[pigeon_nest_idx[a]]).append('\n');
			}
		}
	}
}

JavaScript solution:
function Main(input) {
  const l = input.trim().split('\n');
  const [n, q] = l[0].split(' ').map(v => parseInt(v));
  const o = l.slice(1).map(v => v.split(' ').map(v => parseInt(v)));

  const p = Array(n).fill().map((_, i) => i); // pigions: in which nest?
  const lb = Array(n).fill().map((_, i) => i); // labeled pigions: in which nest?
  const s = Array(n).fill().map((_, i) => i); // nests: with which labeled pigion
  const ans = [];

  for (let i = 0; i < q; i ++) {
    if (o[i][0] === 1) {
      let [a, b] = [o[i][1] - 1, o[i][2] - 1];
      p[a] = lb[b];
    } else if (o[i][0] === 2) {
      let [a, b] = [o[i][1] - 1, o[i][2] - 1];
      let c = s[lb[a]];
      s[lb[a]] = s[lb[b]];
      s[lb[b]] = c;

      c = lb[a];
      lb[a] = lb[b];
      lb[b] = c;
    }
    if (o[i][0] === 3) {
      let a = o[i][1] - 1;
      ans.push(s[p[a]] + 1);
    }
  }

  console.log(
    ans.join('\n')
  );
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Python solution:
#!/usr/bin/env python3
from sys import stdin

_tokens = (y for x in stdin for y in x.split())
def read(): return next(_tokens)
def iread(): return int(next(_tokens))


def dprint(*args, pretty=True):
    def _inner(v):
        def _dim(v): return (1 + min(_dim(x) for x in v) if v else 1) if isinstance(v, (list, tuple)) else 1 if isinstance(v, str) and len(v) > 1 else 0
        def _format_2d(v): return '\n' + '\n'.join([' '.join([str(y) for y in x]) for x in v])
        def _format_3d(v): return '\n' + '\n'.join(['\n'.join([' '.join([str(z) for z in y]) for y in x]) + '\n' for x in v]).rstrip('\n')
        dim = _dim(v) if pretty else -1
        return _format_3d(v) if dim == 3 else _format_2d(v) if dim == 2 else str(v)
    from ast import Call, parse, unparse, walk
    from inspect import currentframe, getsourcelines
    frame = currentframe().f_back
    source_lines, start_line = getsourcelines(frame)
    tree = parse(source_lines[frame.f_lineno - max(1, start_line)].strip())
    call_node = next(node for node in walk(tree) if isinstance(node, Call) and node.func.id == 'dprint')
    arg_names = [unparse(arg) for arg in call_node.args]
    print(', '.join([f'\033[4;35m{name}:\033[0m {_inner(value)}' for name, value in zip(arg_names, args)]))


def main():
    n, q = iread(), iread()
    x = [i for i in range(n)]
    y = [i for i in range(n)]
    z = [i for i in range(n)]
    ans = []
    for _ in range(q):
        t = iread()
        if t == 1:
            a, b = iread() - 1, iread() - 1
            x[a] = z[b]
        elif t == 2:
            a, b = iread() - 1, iread() - 1
            z[a], z[b] = z[b], z[a]
            y[z[a]] = a
            y[z[b]] = b
        else:
            a = iread() - 1
            ans.append(y[x[a]] + 1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Ruby solution:
#!/usr/bin/env ruby
# frozen_string_literal: true

n, q = gets.split.map(&:to_i)
p2b = (0...n).to_a # 鳩 -> 袋
b2h = (0...n).to_a # 袋 -> 巣
h2b = (0...n).to_a # 巣 -> 袋
(0...q).each do
  num, a, b = gets.split.map(&:to_i)
  a -= 1
  case num
  when 1
    b -= 1
    p2b[a] = h2b[b]
  when 2
    b -= 1
    h2b[a], h2b[b] = h2b[b], h2b[a]
    b2h[h2b[a]] = a
    b2h[h2b[b]] = b
  else
    puts b2h[p2b[a]] + 1
  end
end
# 鳩 > 袋 > 巣の関係
# 鳩と巣は直接関連していない
# 1のクエリ(鳩を指定して移す)の場合は袋を移動している