USACO 2020 Feb Contest #1

//
//  main.cpp
//  USACO_2020_FEB_01
//
//  Created by Shin Lee on 21/02/2020.
//  Copyright © 2020 Shin Lee. All rights reserved.
// NO EFFICIENCY VERSION

//#include <stdc++.h>
#include <bits/stdc++.h>
using namespace std;
int n, m ,k;
const int s = 1e5+5;
int original[s];
int c[s], c2[s];
pair<int, int> rule[s];
vector<int>road[s];
int visit[s];
vector<int>connections[s];
void update(){
    for(int i=1;i<=n;i++){
        original[i]=c[i];
    }
}
void dfs(int num, int idx){
    if(visit[num]==1){
        return;
    }
    visit[num]=1;
    connections[idx].push_back(num);
    dfs(road[num][0],idx);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
    cin >> n >> m >> k;
    for(int i=0;i<m;i++){
        cin >> rule[i].first >> rule[i].second;
    }
    //initial 배열

    for(int i=1;i<=n;i++){
        original[i]=i;
        c[i]=i;
    }

    //최초 한번
    for(int i=0;i<m;i++){
        //flip, do the thing
        for(int j=rule[i].first;j<=rule[i].second;j++){
            c[rule[i].second+rule[i].first-j] = original[j];
        }
        update();
    }

    k--;
    for(int i=1;i<=n;i++){
        road[i].push_back(c[i]);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(visit[i]!=1){
            dfs(i,cnt);
            cnt++;
        }
    }

    for(int i=0;i<cnt;i++){
        for(int j=0;j<connections[i].size();j++){
            //printf("%d, ",connections[i][j]);
        }
        //printf("\n");
    }
    for(int i=0;i<cnt;i++){
        for(int j=0;j<connections[i].size();j++){
            c2[connections[i][j]]=connections[i][(j+k%connections[i].size()+1)%connections[i].size()];
        }
    }

    for(int i=1;i<=n;i++){
        printf("%d\n",c2[i]);
    }
    return 0;
}