For the first two subtasks, we can just simulate. $NK$ minutes will suffice because the sequence of positions of an individual cow will start repeating within that time.

Now, onto the full solution. After the first $K$ swaps, we compute where each cow ends up. If a cow started at the $i$-th position, let its new position be $p_i$. Let’s also track the set $s_i$ of all positions that cow $i$ reached during the $K$ swaps. This does not take too much memory because the sum of the sizes of all sets $s_i$ is bounded by $2K+N$ (every swap, at most two cows move, thus adding at most two elements to the sets).

Let’s build a directed graph on the positions that shows how the cows move every $K$ swaps. We have $N$ directed edges from all $i$ to $p_i$ $(1 \le i \le N)$. This graph is a bunch of cycles because after $K$ swaps, there is exactly one cow in each position, so the outdegree and indegree of each node is one. Therefore, the graph is a bunch of disjoint cycles (as with Swapity Swapity Swap).

We claim that the answers for all cows in the same cycle are the same. Because everything repeats every $K$ swaps, if two cows have ever been in the same position after a multiple of $K$ swaps, they would visit the same positions eventually. After $K$ swaps, cow $i$ goes to position $p_i$, so the answers for cow $i$ and cow $p_i$ are the same. This logic extends to every cow in the cycle (the answer for cow $p_i$ is equal to cow $p_{p_i}$ and so on).

So, what exactly is the answer for some cycle? It’s the size of the union of all the sets $s_i$ for each cow $i$ in the cycle. In other words, the answer is the number of unique positions in all the sets in the cycle. The complexity of this solution is $\mathcal{O}(N+K)$.

Chris’ code:

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

int N,K;
int A[200001],B[200001]; //input
int P[100001]; //as described in analysis
vector<int>S[100001]; //as described in analysis
int from[100001]; //from[i] = where the cow in position i originated from
int cnt[100001]; //array to keep track of uniquePos
int uniquePos; //# of unique reachable positions

//add in S_node
void add(int node){
  for (int x:S[node]){
    if (cnt[x]==0)
      uniquePos++;
    cnt[x]++;
  }
}

//remove S_node
void remove(int node){
  for (int x:S[node]){
    if (cnt[x]==1)
      uniquePos--;
    cnt[x]--;
  }
}

bool vis[100001];
queue<int>q; //stores all nodes in current cycle

void dfs(int node){
  vis[node]=true;
  add(node);
  q.push(node);
  if (!vis[P[node]])
    dfs(P[node]);
}

int main(){
  cin>>N>>K;
  for (int i=0;i<K;i++)
    cin>>A[i]>>B[i];
  //initialize from and S
  for (int i=1;i<=N;i++){
    from[i]=i;
    S[i].push_back(i);
  }
  //simulate the first K swaps, keeping track of where each position can reach
  for (int i=0;i<K;i++){
    S[from[A[i]]].push_back(B[i]);
    S[from[B[i]]].push_back(A[i]);
    swap(from[A[i]],from[B[i]]);
  }
  //compute array P after first K swaps
  for (int i=1;i<=N;i++)
    P[from[i]]=i;
  int ans[100001];
  //run a DFS on each cycle
  for (int i=1;i<=N;i++)
    if (!vis[i]){
      dfs(i);
      int tempAns=uniquePos; //the answer 
      //assign the answer for all nodes in the cycle, which we've stored in this queue
      while (!q.empty()){
	remove(q.front());
	ans[q.front()]=tempAns;
	q.pop();
      }
    }
  for (int i=1;i<=N;i++)
    cout<<ans[i]<<endl;
  return 0;
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class DanceMoovesSilver {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int[] cows = new int[n + 1];
        List<Integer>[] viewed = new List[n + 1];
        for (int j = 1; j <= n; j++) {
            cows[j] = j;
            viewed[j] = new ArrayList<>();
            viewed[j].add(j);
        }
        for (long t = 1; t <= k; t++) {
            tokenizer = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(tokenizer.nextToken());
            int b = Integer.parseInt(tokenizer.nextToken());
            int c = cows[a];
            int d = cows[b];
            cows[a] = d;
            cows[b] = c;
            viewed[cows[a]].add(a);
            viewed[cows[b]].add(b);
        }
        int[] answer = new int[n + 1];
        for (int r = 1; r <= n; r++) {
            if (cows[r] != 0) {
                List<Integer> cycle = new ArrayList<>();
                int j = r;
                while (cows[j] != 0) {
                    cycle.add(j);
                    j = cows[j];
                    cows[cycle.get(cycle.size() - 1)] = 0;
                }
                Set<Integer> viewedHere = new HashSet<>();
                for (int cow : cycle) {
                    viewedHere.addAll(viewed[cow]);
                }
                for (int cow : cycle) {
                    answer[cow] = viewedHere.size();
                }
            }
        }
        StringBuilder out = new StringBuilder();
        for (int j = 1; j <= n; j++) {
            out.append(answer[j]).append('\n');
        }
        System.out.print(out);
    }
}