定义

基环树指的是一个 $n$ 个节点,$n$ 条边的联通图。

叫基环树的原因是:给定一棵树,在这棵树上加上 任意一条边,就可以形成一个基环树了。

基环树的性质很优秀,比如:

  1. 去掉环上的任意一条边,就可以转化为一棵树。
  2. 基环树可以看作一个环上挂了很多棵子树,如果将环缩成一个点,那么得到的就是一棵树。

所以基环树的常用套路有:

  1. 找环,然后删掉环上的任意一条边 $(u,v)$,对 $u$ 为根的树进行一次树形DP(并强制不选 $u$),再对 $v$ 为根的树进行一次树形DP(并强制不选 $v$)。
  2. 将环缩成一个点,然后分类讨论答案是否经过环两种情况。

例1 洛谷P2607 [ZJOI2008]骑士

题意

给定 $n$ 个骑士,每个骑士有一个能力值 $a_i$,和他的一个痛恨的人 $b_i$(痛恨的人不能是自己)。

从这些骑士中选出若干个,使得两两之间没有痛恨的人,求出最大的能力值总和。

其中,$n \leq 10^6$。

题解

按照每个人 $i$ 与他痛恨的人 $b_i$ 连边,这就可以形成一个基环森林了(由多个基环树组成的森林)。

现在,只考虑一个基环树的话怎么办?

首先发现,如果断开一条边,在树上考虑这个问题的话,就是一个非常简单的树形DP了。

所以我们不妨断开环上的任意一条边 $(u,v)$。

然后以 $u$ 为根,在这个新的树上进行一次树形DP,并强制不选 $u$。

同理,以 $v$ 为根,在这个新的树上进行一次树形DP,并强制不选 $v$。

求两次树形DP得出的最大值即可。

最终答案就是每个基环树求出的最大值之和。


找环的话,只要发现一个 backward edge,记录一下这个 edge 的编号 E,标记一下 EE^1,在树形DP中避开这两条边,就可以达到断开边的效果了。这要求我们建图时,使用 ecnt = 2

• 需要格外注意一下,在断边的时候,必须判断当前枚举的边 e 是否等于 E 或者 E^1,而不能判断边的两端端点,这是防止出现 $(1,2), (2,1)$ 这种情况,可以参考这里

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int n, head[maxn], ecnt = 2;
ll a[maxn];
struct Edge {
    int to, nxt;
} edges[maxn<<1];
void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

int ed, dep[maxn], par[maxn], E;
void dfs1(int u) {
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == par[u]) continue;
        if (dep[to]) {
            E = e;
        } else {
            dep[to] = dep[u] + 1;
            par[to] = u;
            dfs1(to);
        }
    }
}

ll ans = 0, tot = 0;
ll dp[maxn][2];
void dfs2(int u, int p) {
    dp[u][0] = 0;
    dp[u][1] = a[u];
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == p || e == E || e == (E^1)) continue;
        dfs2(to, u);
        dp[u][0] += max(dp[to][0], dp[to][1]);
        dp[u][1] += dp[to][0];
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> a[i] >> v;
        addEdge(i,v); addEdge(v,i);
    }

    for (int u = 1; u <= n; u++) {
        if (!dep[u]) {
            ans = 0; E = 0;
            dep[u] = 1;
            dfs1(u);
            int c1 = edges[E].to, c2 = edges[E^1].to;

            dfs2(c1, 0);
            ans = max(ans, dp[c1][0]);

            dfs2(c2, 0);
            ans = max(ans, dp[c2][0]);

            tot += ans;
        }
    }
    cout << tot << endl;
}

例2 洛谷P4381 [IOI2008] Island

题意

给定一个基环树组成的森林,每条边上有边权,求出每个基环树的最长链的长度之和。

最长链的定义为:一条路径,不经过重复的节点。

其中,$n \leq 10^6$。

题解

既然是基环森林,那就只考虑每个基环树怎么求最长链。

注意到一个基环树由一个环,以及每个环的子树组成,长这样:

img

所以我们可以讨论这个最长链的位置:

第一种情况:最长链不经过环

这说明最长链完全在一个子树内,那么这就是一个树的直径问题。

第二种情况:最长链经过环

如果经过了环,我们设它从环上的某个点 $u$ 的子树开始,到环上另外一个点 $v$ 的子树结束。

并且设 $dis(u,v)$ 为 $u,v$ 在环上的最长距离,设 $d(u)$ 为 $u$ 的子树最大深度。

所以答案就是

$$\max_{(u,v)}\{d(u)+d(v)+dis(u,v)\}$$

但找这样的 $(u,v)$ 是 $O(n^2)$ 的,考虑一下如何优化?

如果我们将一个环 $1,2,3,…,n$ 断开,并复制一份,得到 $1,2,3,…,n,1’,2’,3’,…,n'$,则我们可以快速的算出 $dis(u,v)$。

不妨设 $u<v$,并且求一个距离的前缀和 $a[]$,其中 $a[i]=a[i-1]+w(i-1,i)$。

那么

$$\max_{(u,v)}\{d(u)+d(v)+dis(u,v)\}$$

就可以写成

$$\max_{(u,v)}\{d(u)+d(v)+a[v]-a[u]\}, u,v\in[1,n] \cup [1’,n’], (v-u) \in [1, n-1]$$

当 $v$ 确定时,我们要求的实际上就是

$$\max_u \{d(u) - a[u]\}, u \in [v-n+1,v-1]$$

这就是个单调队列优化dp。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

struct Edge {
    int from, to, nxt;
    ll w;
} edges[maxn<<1];
int head[maxn], ecnt = 2, in[maxn];
void addEdge(int u, int v, ll w) {
    Edge e = {u, v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
bool vis[maxn], ring[maxn];
ll ans = 0;

// solve the component containing u
vector<int> ver;  // vertex in current component
void bfs(int u) {
    vis[u] = 1;
    ver.push_back(u);
    int p = 0;

    while (p < ver.size()) {
        int v = ver[p];
        for (int e = head[v]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (vis[to]) continue;
            vis[to] = 1;
            ver.push_back(to);
        }
        p++;
    }
}

ll dep[maxn], maxdep[maxn];
vector<int> tmp;  // used for storing leaf
int maxi = 0, n;
int q[maxn<<1], hd, tail, par[maxn];

void bfs2(int u) {
    int o = u;
    hd = 1, tail = 0;
    q[++tail] = u;
    par[u] = 0;
    dep[u] = 0;

    while (hd <= tail) {
        u = q[hd]; hd++;
        if (dep[u] > dep[maxi]) maxi = u;
        for (int e = head[u]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (to == par[u] || ring[to]) continue;
            par[to] = u;
            q[++tail] = to;
            dep[to] = dep[u] + edges[e].w;
        }
    }
    maxdep[o] = dep[maxi];
}

ll md = 0;
void bfs3(int u, int v) {
    hd = 1, tail = 0;
    q[++tail] = u;
    par[u] = 0;
    dep[u] = 0;

    while (hd <= tail) {
        u = q[hd]; hd++;
        md = max(md, dep[u]);
        for (int e = head[u]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (to == par[u] || (ring[to] && to != v)) continue;
            par[to] = u;
            q[++tail] = to;
            dep[to] = dep[u] + edges[e].w;
        }
    }

}

vector<int> rings;
bool tag[maxn<<1];
struct Node {
    ll a, d;
} nd[maxn<<1];
bool del[maxn];
void solve(int u) {
    ver.clear();
    tmp.clear();
    bfs(u);
    ll res = 0;
    for (int v : ver) {
        if (in[v] == 1) tmp.push_back(v);
    }
    while (!tmp.empty()) {
        int v = tmp.back(); tmp.pop_back();
        del[v] = 1;
        for (int e = head[v]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (!del[to]) {
                in[v]--; in[to]--;
                if (in[to] == 1) tmp.push_back(to);
            }
        }
    }
    for (int v : ver) {
        if (in[v] >= 2) ring[v] = 1;  // v is on the ring
    }
    rings.clear();
    int cnt = 0;
    for (int v : ver) {
        if (ring[v]) {
            cnt++;
            if (!rings.size()) rings.push_back(v);
            maxi = 0;
            md = 0;
            bfs2(v);
            dep[maxi] = 0;
            bfs3(maxi, v);
            res = max(res, md);
            hd = 1, tail = 0;
        }
    }

    // get the ring
    if (rings.size()) {
        while (rings.size() < cnt) {
            int v = rings.back();
            for (int e = head[v]; e; e = edges[e].nxt) {
                int to = edges[e].to;
                if (!ring[to] || (rings.size() >  1 && to == rings[rings.size()-2])) continue;
                if (to == rings[0]) {
                    goto done;
                }
                rings.push_back(to);
                break;
            }
        }
    }
    done:;

    int ptr = 0;
    if (rings.size()) {
        rings.push_back(rings.front());
        nd[++ptr] = {0, maxdep[rings[0]]};
    }

    int m = rings.size();
    for (int i = 0; i < m-1; i++) {
        int v = rings[i];
        int v2 = rings[i+1];
        for (int e = head[v]; e; e = edges[e].nxt) {
            if (edges[e].to == v2 && !tag[e]) {
                ll w = edges[e].w;
                nd[ptr+1].a = nd[ptr].a + w;
                nd[ptr+1].d = maxdep[v2];
                ptr++;
                tag[e] = tag[e^1] = 1;   // 标记边,防止有大小为2的环!
                break;
            }
        }
    }
    for (int i = 0; i < m-2; i++) {
        nd[ptr+1].a = nd[ptr].a + (nd[i+2].a - nd[i+1].a);
        nd[ptr+1].d = maxdep[rings[i+1]];
        ptr++;
    }

    hd = 1, tail = 0;
    q[++tail] = 1;

    m--;  // now: m is the size of the ring
    for (int i = 2; i <= ptr; i++) {
        while (hd <= tail && i - q[hd] >= m) hd++;
        if (hd <= tail) {
            res = max(res, nd[i].a + nd[i].d + nd[q[hd]].d - nd[q[hd]].a);
        }
        while (hd <= tail && nd[i].d - nd[i].a >= nd[q[tail]].d - nd[q[tail]].a) tail--;
        q[++tail] = i;
    }
    ans += res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v; ll w; cin >> v >> w;
        addEdge(i,v,w); addEdge(v,i,w);
        in[i]++; in[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            solve(i);
        }
    }

    cout << ans << endl;
}

注意点

  1. 所有的树上/图上操作(包括找树的直径)都必须用 bfs 进行,因为 $n \leq 10^6$,dfs 会爆栈。
  2. 找环的时候用拓扑排序,不过注意这个是无向图,所以写法略有不同。
  3. 找出环以后,要按照环的顺序把环断开,不能只考虑哪些节点在环上而不考虑顺序。
  4. 一定要注意 大小为 $2$ 的环,我们在断环为链的时候不能考虑节点之间的关系,而是要标记 edge,因为双向图的缘故,大小为 $2$ 的环之间会有重边,一定要注意!

例3 洛谷P1399 [NOI2013] 快餐店

题意

给定一个 $n$ 个节点,$n$ 条边的无向图(基环树),边上有权值。

现在要在树上找一个位置 $x$,这个位置 $x$ 可以位于边上的任意一处,也可以位于节点上。

如何选择 $x$ 的位置,使得它到 所有节点的最短距离的最大值 最小?输出这个最小值。

形式化的,求:

$$\min_x \{\max_u\{dis(x,u)\}\}$$

其中,$n \leq 10^5$。

题解

先考虑,如果这是一棵树的话怎么办?

那我们只要求出这棵树的直径,然后答案就是 直径/2 了。

对于基环树,我们一般都是断环,得到一棵树,那么对于这个题我们有类似的想法:

猜想:环上必然存在一条边,使得这条边断开以后对整个答案没有任何影响。

证明:我们考虑 $x$ 的位置

  1. $x$ 在环上
  2. $x$ 在一棵子树中

对于第一种情况,我们注意到 $x$ 到所有节点的最短路径中,由环上路径和树内路径组成。

我们只考虑环上的路径(因为我们要证明的是环上的所有边不可能都被用到,至少有一个是用不上的)。

那么问题就相当于,$x$ 到环上所有节点的最短路径,是否存在一条边用不上?

确实如此,因为无论我们怎么画,都会有一条边被断开以后没有任何影响,如图:

img

• 对于第二种情况也完全一样,所以这个结论是正确的。


所以问题就转化成了:

给定一棵基环树,我们现在要断开环上的一条边,求所有断开的方案中,树的直径最小的一个方案,求出最小值?

然后这题就和上一个例子差不多了,一样分类讨论直径在哪:

  1. 断开后,树的直径在子树内
  2. 断开后,树的直径在原先的环上

对于第一种情况,无论断开哪个都不影响答案,所以对于每个子树统计一下直径即可。

对于第二种情况,上一题的单调队列套路不好使了,我们形式化的描述一下这个问题:

给定一个环 $1,2,…,n$,对于每一种断环方案,都求出:

$$\max_{(u,v)}\{d(u)+d(v)+dis(u,v)\}$$

然后取所有断环方案对应的最小值。

这里有了个断环方案要讨论,就变得非常不友好,就算断环成链也没什么思路,我们考虑另外一种方法:

img

假设我们要断开 $(i,i+1)$,那么此时,这个所求的最大值对应的 $(u,v)$ 有几种情况呢?

  1. $(u,v)$ 都在 $[1,i]$ 内。
  2. $(u,v)$ 都在 $[i+1,n]$ 内。
  3. $u$ 在 $[1,i]$,$v$ 在 $[i+1,n]$。

对于第一种,我们同样用前缀和的方式来看,因为 $dis(u,v) = sum(v) - sum(u)$,所以和上一题一样处理一个前缀和即可,本题甚至都不需要单调队列,维护一下前缀的 -sum[u] + d[u] 的最大值即可。

然后我们就可以处理出一个 pre[] 数组,pre[i] 的意思就是如果 $(u,v)$ 都在 $[1,i]$ 内,可以得到的最大值。

同理对于第二种我们用后缀处理一下即可,可以得到 suf[]

对于第三种,我们可以发现我们所求的 $dis(u,v) + d(u) + d(v)$,等于

$u$ 的 前缀链 + $v$ 的 后缀链 + $w(n,1)$

img

所以我们只要把这个前缀链的最大值 maxl[i] 求出即可(同理后缀链最大值也求出 maxr[])。

那么,当我们断开 $(i,i+1)$ 时,就有

$$\max_{(u,v)}\{d(u)+d(v)+dis(u,v)\} = \max\{pre(i), suf(i+1), maxl(i) + maxr(i+1) + w(n,1)\}$$

然后将 $i$ 从 $1$ 枚举到 $n$ 即可。

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

struct Edge {
    int from, to, nxt;
    ll w;
} edges[maxn<<1];
int head[maxn], ecnt = 2, in[maxn];
void addEdge(int u, int v, ll w) {
    Edge e = {u, v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
bool ring[maxn];
ll ans = 0;

ll dep[maxn], maxdep[maxn];
vector<int> tmp;  // used for storing leaf
int maxi = 0, n;
int q[maxn<<1], hd, tail, par[maxn];

void bfs2(int u) {
    int o = u;
    hd = 1, tail = 0;
    q[++tail] = u;
    par[u] = 0;
    dep[u] = 0;

    while (hd <= tail) {
        u = q[hd]; hd++;
        if (dep[u] > dep[maxi]) maxi = u;
        for (int e = head[u]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (to == par[u] || ring[to]) continue;
            par[to] = u;
            q[++tail] = to;
            dep[to] = dep[u] + edges[e].w;
        }
    }
    maxdep[o] = dep[maxi];
}

ll md = 0;
void bfs3(int u, int v) {
    hd = 1, tail = 0;
    q[++tail] = u;
    par[u] = 0;
    dep[u] = 0;

    while (hd <= tail) {
        u = q[hd]; hd++;
        md = max(md, dep[u]);
        for (int e = head[u]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (to == par[u] || (ring[to] && to != v)) continue;
            par[to] = u;
            q[++tail] = to;
            dep[to] = dep[u] + edges[e].w;
        }
    }

}

vector<int> rings;
bool tag[maxn<<1];
struct Node {
    ll a, d;
} nd[maxn<<1];
bool del[maxn];
ll maxl[maxn], maxr[maxn], pre[maxn], suf[maxn];
void solve() {
    ll res = 0;
    for (int v = 1; v <= n; v++) {
        if (in[v] == 1) tmp.push_back(v);
    }
    while (!tmp.empty()) {
        int v = tmp.back(); tmp.pop_back();
        del[v] = 1;
        for (int e = head[v]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (!del[to]) {
                in[v]--; in[to]--;
                if (in[to] == 1) tmp.push_back(to);
            }
        }
    }
    for (int v = 1; v <= n; v++) {
        if (in[v] >= 2) ring[v] = 1;  // v is on the ring
    }
    int cnt = 0;
    for (int v = 1; v <= n; v++) {
        if (ring[v]) {
            cnt++;
            if (!rings.size()) rings.push_back(v);
            maxi = 0;
            md = 0;
            bfs2(v);
            dep[maxi] = 0;
            bfs3(maxi, v);
            res = max(res, md);
            hd = 1, tail = 0;
        }
    }

    // get the ring
    if (rings.size()) {
        while (rings.size() < cnt) {
            int v = rings.back();
            for (int e = head[v]; e; e = edges[e].nxt) {
                int to = edges[e].to;
                if (!ring[to] || (rings.size() >  1 && to == rings[rings.size()-2])) continue;
                if (to == rings[0]) {
                    goto done;
                }
                rings.push_back(to);
                break;
            }
        }
    }
    done:;

    int ptr = 0;
    if (rings.size()) {
        rings.push_back(rings.front());
        nd[++ptr] = {0, maxdep[rings[0]]};
    }

    int m = rings.size();
    for (int i = 0; i < m-1; i++) {
        int v = rings[i];
        int v2 = rings[i+1];
        for (int e = head[v]; e; e = edges[e].nxt) {
            if (edges[e].to == v2 && !tag[e]) {
                ll w = edges[e].w;
                nd[ptr+1].a = nd[ptr].a + w;
                nd[ptr+1].d = maxdep[v2];
                ptr++;
                tag[e] = tag[e^1] = 1;   // 标记边,防止有大小为2的环!
                break;
            }
        }
    }
    for (int i = 0; i < m-2; i++) {
        nd[ptr+1].a = nd[ptr].a + (nd[i+2].a - nd[i+1].a);
        nd[ptr+1].d = maxdep[rings[i+1]];
        ptr++;
    }

    hd = 1, tail = 0;
    ll R = res;
    res = 1e18;

    m--;  // now: m is the size of the ring

    // maxl: record a+d
    for (int i = 1; i <= m; i++) maxl[i] = max(maxl[i-1], nd[i].a + nd[i].d);
    for (int i = m; i >= 1; i--) maxr[i] = max(maxr[i+1], nd[m+1].a - nd[i].a + nd[i].d);

    // pre: record the maximum of two i,j <= pre, which dis(i,j) + d[i] + d[j] is maximum (just record minimum of -a + d)
    ll mn = 0;
    for (int i = 1; i <= m; i++) {
        pre[i] = max(pre[i-1], mn + nd[i].a + nd[i].d);
        mn = max(mn, -nd[i].a + nd[i].d);
    }

    mn = 0;
    for (int i = m; i >= 1; i--) {
        suf[i] = max(suf[i+1], mn + nd[m+1].a - nd[i].a + nd[i].d);
        mn = max(mn, -(nd[m+1].a - nd[i].a) + nd[i].d);
    }
    for (int i = 1; i <= m; i++) {  // break (i,i+1)
        ll r1 = 0, r2 = 0;
        r1 = max(pre[i], suf[i+1]);
        r2 = maxl[i] + maxr[i+1];
        res = min(res, max(r1,r2));
    }

    ans += max(R, res);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u,v; ll w; cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
        in[u]++; in[v]++;
    }
    solve();
    printf("%.1f\n",(double)(ans)*0.5);
}

例4 BAPC2022H. House Numbering

题意

给定一个 $n$ 个点,$n$ 条边的联通无向图。

每条边有一个权值 $w$,意味着这条边的两端需要分别标上 $1,w$ 或者 $w,1$。

问是否存在一种方案,使得所有点的边上没有被标上相同的元素。有,则输出方案。

其中,$n \leq 10^5$,所有边的 $w > 1$。

img

如图,这就是一种合理标号方式,其中 $w_{1,2}=2, w_{2,3}=9, w_{1,3}=3$。

题解

首先注意这是一个基环树。所以要围绕环做文章。

经过一段时间的观察后可以发现,如果我们把这个看作一个有向图,箭头指向的点会获得这个边的 $1$,另外一个点获得 $w$,那么所有不在环上的,都应该是向外指的。

因为一旦有一个向内指的,环上一旦出现一个来自于树的 $1$,那么就不成立了。

所以不在环上的部分都可以决定了。

剩下的只有环了。

可以发现环要么是顺时针指,要么是逆时针指,所以只要判断这两个情况就行。

img

代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n;
struct Edge {
    int to, nxt, w;
    int idx;
} edges[maxn<<1];
int head[maxn], ecnt = 2;
void addEdge(int u, int v, int w, int idx) {
    Edge e = {v, head[u], w, idx};
    head[u] = ecnt;
    edges[ecnt++] = e;
}

bool iscycle[maxn];
bool vis[maxn];
int cu, cv, cidx, pre[maxn];
bool found = 0;
void dfs(int u) {
    vis[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to, w = edges[e].w;
        if (v == pre[u]) continue;
        if (vis[v]) {
            if (found) return;
            found = 1;
            int cur = u;
            while (cur != v) {
                iscycle[cur] = 1;
                cur = pre[cur];
            }
            iscycle[v] = 1;

            cu = u, cv = v;
            cidx = edges[e].idx;
        } else {
            pre[v] = u;
            dfs(v);
        }
    }
}

int ans[maxn];
void dfs2(int u, int p, int f) {
    vis[u] = 1;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int v = edges[e].to, w = edges[e].w, idx = edges[e].idx;
        if (v == p) continue;
        if (vis[v]) {
            if (!found) ans[idx] = (f ? u : v), found = 1;
            continue;
        }

        if (!iscycle[v]) {  // then must point to v
            ans[idx] = v;
        } else {
            assert(iscycle[u] && iscycle[v]);
            if (f) {
                ans[idx] = u;
            } else {
                ans[idx] = v;
            }
        }
        dfs2(v, u, f);
    }
}

bool check() {
    for (int u = 1; u <= n; u++) {
        set<int> se;
        int cnt = 0;
        for (int e = head[u]; e; e = edges[e].nxt) {
            int v = edges[e].to, w = edges[e].w, idx = edges[e].idx;
            if (ans[idx] == u) se.insert(1);
            else se.insert(w);
            cnt++;
        }
        if (se.size() != cnt) return 0;
    }
    return 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u,v,w; cin >> u >> v >> w;
        addEdge(u,v,w,i);
        addEdge(v,u,w,i);
    }

    dfs(1);

    memset(vis, 0, sizeof(vis));
    found = 0;
    dfs2(cu, -1, 0);  // start with any point on the cycle

    if (check()) {
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << "\n";
        return 0;
    }


    memset(vis, 0, sizeof(vis));
    found = 0;
    dfs2(cu, -1, 1);  // start with any point on the cycle

    if (check()) {
        for (int i = 1; i <= n; i++) cout << ans[i] << " ";
        cout << "\n";
        return 0;
    }

    cout << "impossible\n";
}