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

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

int N, M, K;


vector<int> adj[100100];
 
stack<int> S;
 
int cnt = 0;
int dfn[100100], low[100100];
bool in_stack[100100];
int time_in = 0;
int kingdom[100100];

int self_e[100100];

void init(int n, int k){
    N = n;
    K = k;
    for (int i = 0; i < k-1; i++){
        adj[i].push_back(i+1);
    }
}

void dfs(int node){
    dfn[node] = ++time_in;
    low[node] = dfn[node];
    S.push(node);
    in_stack[node] = true;
    for (int nx : adj[node]){
        if (!dfn[nx]){
            dfs(nx);
            low[node] = min(low[node], low[nx]);
        } else if (in_stack[nx]){
            low[node] = min(low[node], dfn[nx]);
        }
    }
    if (low[node] == dfn[node]){
        ++cnt;
        while (S.top() != node){
            kingdom[S.top()] = cnt;
            in_stack[S.top()] = false;
            S.pop();
        }
        kingdom[S.top()] = cnt;
        in_stack[S.top()] = false;
        S.pop();
    }
}

int kcnt[100100];

bool good = false;

int add_teleporter(int u, int v){
    if (good) return true;
    if (u == v){
        self_e[u]++;
    }
    adj[u].push_back(v);
    time_in = 0;
    cnt = 0;
    for (int i = 0; i <= N; i++){
        dfn[i] = low[i] = kcnt[i] = kingdom[i] = 0;
        in_stack[i] = false;
    }
    while (!S.empty()){
        S.pop();
    }
    for (int i = 0; i < N; i++){
        if (!dfn[i]){
            dfs(i);
        }
    }
    for (int i = 0; i < N; i++){
        cout << kingdom[i] << " ";
    }
    cout << "\n";
    for (int i = 0; i < N; i++){
        kcnt[kingdom[i]]++;
    }
    bool work = false;
    for (int i = 0; i < K; i++){
        if (kcnt[kingdom[i]] > 1 || self_e[i]){
            work = true;
            good = true;
        }
    }
    return work;
}