using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
const int NMAX = 1e5 + 11;
int n, m;
vi g[NMAX], ans;
bool dfs(int u, vi &tin, int &cur_time, int start_time)
{
    if (tin[u] > start_time)
    {
        ans.push_back(u);
        return true;
    }
    tin[u] = ++cur_time;
    for (auto v : g[u])
    {
        if (dfs(v, tin, cur_time, start_time))
        {
            if (tin[u] >= tin[ans.front()])
                ans.push_back(u);
            return true;
        }
    }
    tin[u] = start_time;
    return false;
}
bool has_cycle(void)
{
    vi tin(n + 1, 0);
    int cur_time, start_time = 1;
    for (int u = 1; u <= n; ++u)
    {
        cur_time = start_time;
        if (tin[u] == 0 and dfs(u, tin, cur_time, start_time))
            return true;
        start_time = cur_time;
    }
    return false;
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
    }
    if (has_cycle())
    {
        cout << ans.size() << endl;
        for_each(ans.rbegin(), ans.rend(), [](int x) { cout << x << " "; }),
            cout << endl;
    }
    else
    {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using iii = array<int, 3>;
using vi = vector<int>;
struct dsu
{
    int n, nc, lc;
    vi parent, sz;
    dsu(int n)
    {
        nc = n;
        lc = 0;
        parent.resize(n);
        sz.assign(n, 1);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
    int find_set(int u)
    {
        if (u == parent[u])
            return u;
        return parent[u] = find_set(parent[u]);
    }
    void union_set(int u, int v)
    {
        u = find_set(u);
        v = find_set(v);
        if (u != v)
        {
            if (sz[u] < sz[v])
                swap(u, v);
            parent[v] = parent[u];
            sz[u] += sz[v];
            nc -= 1;
            lc = max(lc, sz[u]);
        }
    }
};
int main(void)
{
    int n, m, u, v;
    cin >> n >> m;
    dsu d(n);
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v, --u, --v;
        d.union_set(u, v);
        cout << d.nc << " " << d.lc << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using iii = array<int, 3>;
using vi = vector<int>;
struct dsu
{
    int n;
    vi parent, sz;
    dsu(int n)
    {
        parent.resize(n);
        sz.assign(n, 1);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }
    int find_set(int u)
    {
        if (u == parent[u])
            return u;
        return parent[u] = find_set(parent[u]);
    }
    void union_set(int u, int v)
    {
        u = find_set(u);
        v = find_set(v);
        if (u != v)
        {
            if (sz[u] < sz[v])
                swap(u, v);
            parent[v] = parent[u];
            sz[u] += sz[v];
        }
    }
    bool is_connected(int l, int r)
    {
        int p = find_set(l);
        for (int u = l; u <= r; ++u)
            if (p != find_set(u))
                return false;
        return true;
    }
};
int main(void)
{
    int n, m;
    vector<iii> edges;
    cin >> n >> m;
    edges.resize(m);
    for (auto &[c, u, v] : edges)
        cin >> u >> v >> c;
    sort(edges.begin(), edges.end());
    dsu d(n + 1);
    ll ans = 0;
    for (auto [c, u, v] : edges)
    {
        if (d.find_set(u) == d.find_set(v))
            continue;
        d.union_set(u, v);
        ans += c;
    }
    if (d.is_connected(1, n))
        cout << ans << endl;
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, sz[NMAX];
vi g[NMAX];
void calc_sz(int u, int p = -1)
{
    sz[u] = 1;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        calc_sz(v, u - 1);
        sz[u] += sz[v];
    }
}
int main(void)
{
    cin >> n;
    for (int v = 1; v < n; ++v)
    {
        int u;
        cin >> u, u--;
        g[u].push_back(v);
    }
    calc_sz(0);
    for (int i = 0; i < n; ++i)
    {
        cout << sz[i] - 1 << " ";
    }
    cout << endl;
    return 0;
}

using namespace std;
using ll = long long;
template <typename T>
using vx = vector<T>;
template <typename T>
using vvx = vector<vx<T>>;
const ll INF = 1e16;
const vvx<ll> floyd_warshall(int n, const vvx<int> &g)
{
    vvx<ll> dist(n + 1, vx<ll>(n + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else if (g[i][j])
                dist[i][j] = g[i][j];
            else
                dist[i][j] = INF;
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    return dist;
}
int main(void)
{
    int n, m, q, u, v, w;
    cin >> n >> m >> q;
    vvx<int> g(n + 1, vx<int>(n + 1, 0));
    while (m--)
    {
        cin >> u >> v >> w;
        if (g[u][v])
            w = min(w, g[u][v]);
        g[u][v] = w;
        g[v][u] = w;
    }
    auto ans = floyd_warshall(n, g);
    while (q--)
    {
        cin >> u >> v;
        cout << (ans[u][v] == INF ? -1 : ans[u][v]) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using lli = pair<ll, int>;
template <typename T>
using pqueue = priority_queue<T>;
const int NMAX = 1e5 + 11;
const ll INF = 1e16;
int n, m;
vii g[NMAX];
vector<ll> dijkstra(int start)
{
    pqueue<lli> q;
    vector<ll> distance(n + 1, INF);
    vector<bool> processed(n + 1, false);
    distance[start] = 0;
    q.push({0, start});
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (processed[u])
            continue;
        processed[u] = true;
        for (auto [v, w] : g[u])
        {
            if (distance[u] + w < distance[v])
            {
                distance[v] = distance[u] + w;
                q.push({-distance[v], v});
            }
        }
    }
    return distance;
}
int main(void)
{
    int u, v, w;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(v, w);
    }
    auto ans = dijkstra(1);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, m, tin[NMAX], cur_time;
vi g[NMAX], ans;
bool dfs(int u, int p)
{
    if (tin[u] != 0)
    {
        ans.push_back(u);
        return true;
    }
    tin[u] = ++cur_time;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        if (dfs(v, u))
        {
            if (tin[u] >= tin[ans.front()])
                ans.push_back(u);
            return true;
        }
    }
    return false;
}
bool has_cycle(void)
{
    for (int u = 1; u <= n; ++u)
    {
        cur_time = 0;
        if (tin[u] == 0 and dfs(u, 0))
            return true;
    }
    return false;
}
int main(void)
{
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (has_cycle())
    {
        cout << ans.size() << endl;
        for (auto u : ans)
            cout << u << " ";
        cout << endl;
    }
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, m, group[NMAX];
vi g[NMAX];
bool dfs(int u, int p, int gr)
{
    group[u] = gr;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        if (group[v] and group[v] == group[u])
            return false;
        if (not group[v] and not dfs(v, u, (gr == 1 ? 2 : 1)))
            return false;
    }
    return true;
}
bool bipartite_check(void)
{
    for (int u = 1; u <= n; ++u)
    {
        if (not group[u])
            if (dfs(u, 0, 1) == false)
                return false;
    }
    return true;
}
int main(void)
{
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (bipartite_check())
    {
        for (int i = 1; i <= n; ++i)
            cout << group[i] << " ";
        cout << endl;
    }
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using mii = map<int, int>;
const int NMAX = 1e5 + 11;
int n, m;
bool visited[NMAX];
vi g[NMAX];
void reconstruct_path(int s, int e, const mii &came_from)
{
    vi ans;
    int cur = s;
    ans.push_back(s);
    do
    {
        cur = came_from.at(cur);
        ans.push_back(cur);
    } while (cur != e);
    cout << ans.size() << endl;
    reverse(ans.begin(), ans.end());
    for (auto computer : ans)
        cout << computer << " ";
    cout << endl;
}
void bfs(int start, int target)
{
    mii came_from;
    queue<int> q;
    q.push(start);
    while (not q.empty())
    {
        int u = q.front();
        q.pop();
        if (u == target)
        {
            reconstruct_path(u, start, came_from);
            return;
        }
        for (auto v : g[u])
        {
            if (not visited[v])
            {
                q.push(v);
                came_from[v] = u;
                visited[v] = true;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
}
int main(void)
{
    int u, v;
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1, n);
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
int n, m, parent[NMAX], sz[NMAX];
void make_set(int u)
{
    parent[u] = u;
    sz[u] = 1;
}
int find_set(int u)
{
    if (u == parent[u])
        return u;
    return parent[u] = find_set(parent[u]);
}
void union_set(int u, int v)
{
    u = find_set(u);
    v = find_set(v);
    if (u != v)
    {
        if (sz[u] < sz[v])
            swap(u, v);
        parent[v] = u;
        sz[u] += sz[v];
    }
}
int main(void)
{
    int u, v;
    cin >> n >> m;
    for (int u = 1; u <= n; ++u)
        make_set(u);
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        union_set(u, v);
    }
    vi heads;
    for (int u = 1; u <= n; ++u)
        if (find_set(u) == u)
            heads.push_back(u);
    int reps = heads.size();
    cout << reps - 1 << endl;
    if (reps == 1)
        return 0;
    for (int i = 1; i < reps; ++i)
        cout << heads[i - 1] << " " << heads[i] << endl;
    return 0;
}