## 1. Abridged problem statement

Given several connected simple undirected graphs with an even number `n` of vertices, partition the vertices into countries. Each country must contain at least two vertices, and inside every country there must be exactly one path between every pair of its vertices using only vertices of that country. Equivalently, the subgraph induced by each country must be a tree.

For every test case, output any valid country number for each vertex. Countries should be numbered `1..k`.

---

## 2. Detailed editorial

### Key observation

A country must induce a tree:

- It must be connected, because there must be a path between every pair of its cities.
- It must be acyclic, because if there is a cycle, then two vertices on that cycle have more than one path between them.

So we need to split the graph into vertex-disjoint induced trees, each with at least two vertices.

---

### DFS tree viewpoint

Root the graph and build a DFS spanning tree.

In an undirected graph, every non-tree edge in a DFS traversal connects a vertex with one of its ancestors. Such edges are called back edges.

Now imagine cutting some edges of the DFS tree. The connected components of the remaining DFS tree edges are candidate countries.

For such a component to be a valid country:

1. It must contain at least two vertices.
2. It must not contain both endpoints of any back edge.
   Otherwise, the tree path between those endpoints plus the back edge would form a cycle.

So the problem becomes:

> Cut some DFS tree edges so that every resulting block has size at least two and no back edge is fully inside one block.

The solution tries every possible DFS root. For at least one root, such a decomposition exists.

---

### DP state

For a vertex `v`, process its DFS subtree bottom-up.

We consider the unfinished block containing `v`. This block may later be merged with `v`'s parent.

For this unfinished block, we store two pieces of information:

```cpp
big
target
```

where:

- `big = 0` means the block currently contains only one vertex.
- `big = 1` means the block already contains at least two vertices.
- `target` is the maximum depth of an ancestor reached by a back edge from some vertex in this block.
- `target = -1` means there is no such back edge.

The maximum depth corresponds to the closest ancestor reached by a back edge.

The state is encoded as:

```cpp
encode(big, target) = big * nb + (target + 1)
```

where `nb = n + 2`.

---

### Initial state for a vertex

Before processing children, the unfinished block is just `{v}`.

So:

- `big = 0`
- `target = up_target[v]`

Here `up_target[v]` is the closest ancestor of `v` connected to `v` by a back edge, or `-1` if no such ancestor exists.

---

### Processing a child

Suppose we are processing child `c` of `v`.

There are two choices.

---

#### Choice 1: Cut the child block

The unfinished block of child `c` becomes a separate country.

This is allowed only if that child block already has size at least two:

```cpp
child_big == 1
```

The state of `v`'s block does not change.

---

#### Choice 2: Merge the child block into `v`'s block

This means the tree edge `v-c` remains inside the same country.

This is allowed only if the child block has no back edge to `v` or to a descendant of `v` already inside the merged block.

The dangerous case is when the child block has a back edge to `v`, because then adding the tree edge path plus the back edge creates a cycle.

Since `target` stores the deepest ancestor reached by a back edge, merging is safe iff:

```cpp
child_target <= dep[v] - 1
```

That means every back edge from the child block goes strictly above `v`.

After merging:

```cpp
big = 1
target = max(current_target, child_target)
```

The block is definitely big because it contains `v` plus at least one vertex from the child subtree.

---

### Root condition

After processing the root, the whole remaining block must itself be a valid country.

Therefore its final state must be:

```cpp
big = 1
target = -1
```

Why `target = -1`?

Because the root has no ancestors, so there must be no pending back edge going outside the root block.

---

### Reconstruction

During DP, for every reachable state, the solution stores the decisions used:

- whether a child was cut away as a separate country,
- or merged into the current block.

After finding a valid root state, we replay those decisions recursively:

- If a child is merged, it receives the same country number.
- If a child is cut, it receives a new country number.

Finally, country labels are compressed to `1..k`.

---

### Complexity

For each vertex, the number of states is `O(n)`, because:

- `big` has only two possibilities,
- `target` is one of `-1, 0, ..., n`.

For each root, the DP is roughly `O(n^3)` in the worst case, but constraints are tiny:

```text
n <= 100
m <= 1000
total n over tests <= 100
```

So trying all roots is easily fast enough.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<vector<int>> edges;

int nb;
vector<vector<int>> adj, kids;
vector<int> dep, par, up_target;
vector<char> seen;
vector<map<int, vector<array<int, 3>>>> plan;
vector<int> country;
int next_country;

int encode(int big, int target) { return big * nb + (target + 1); }

void dfs(int v, int p, int d) {
    seen[v] = 1;
    par[v] = p;
    dep[v] = d;
    up_target[v] = -1;
    for(int u: adj[v]) {
        if(u == p) {
            continue;
        }
        if(!seen[u]) {
            kids[v].push_back(u);
            dfs(u, v, d + 1);
        } else if(dep[u] < d) {
            up_target[v] = max(up_target[v], dep[u]);
        }
    }
}

void build_dp(int v) {
    for(int c: kids[v]) {
        build_dp(c);
    }

    map<int, vector<array<int, 3>>> cur;
    cur[encode(0, up_target[v])] = {};
    for(int c: kids[v]) {
        map<int, vector<array<int, 3>>> nxt;
        for(auto& [state, decisions]: cur) {
            int target = state % nb - 1;
            for(auto& [child_state, _]: plan[c]) {
                if(child_state / nb == 1) {
                    if(!nxt.count(state)) {
                        nxt[state] = decisions;
                        nxt[state].push_back({c, 0, child_state});
                    }
                    break;
                }
            }

            for(auto& [child_state, _]: plan[c]) {
                int child_target = child_state % nb - 1;
                if(child_target <= dep[v] - 1) {
                    int merged = encode(1, max(target, child_target));
                    if(!nxt.count(merged)) {
                        nxt[merged] = decisions;
                        nxt[merged].push_back({c, 1, child_state});
                    }
                }
            }
        }

        cur.swap(nxt);
    }

    plan[v] = cur;
}

void build_country(int v, int state, int id) {
    country[v] = id;
    for(auto& [c, action, child_state]: plan[v][state]) {
        build_country(c, child_state, action == 1 ? id : ++next_country);
    }
}

bool partition_from(int root) {
    kids.assign(n + 1, {});
    dep.assign(n + 1, 0);
    par.assign(n + 1, 0);
    up_target.assign(n + 1, 0);
    seen.assign(n + 1, 0);
    plan.assign(n + 1, {});

    dfs(root, 0, 0);
    build_dp(root);

    int whole = encode(1, -1);
    if(!plan[root].count(whole)) {
        return false;
    }

    country.assign(n + 1, 0);
    next_country = 1;
    build_country(root, whole, 1);
    return true;
}

void read() {
    cin >> n >> m;
    edges.assign(m, {});
    for(auto& e: edges) {
        e.resize(2);
        cin >> e[0] >> e[1];
    }
}

void solve() {
    // A country must induce a tree, so we look for divisions in which every
    // country is a connected subtree of a rooted DFS spanning tree. With a
    // DFS tree every non-tree edge is a back edge between an ancestor and a
    // descendant, so the task becomes: cut some tree edges so that each
    // resulting piece has at least two vertices and the two endpoints of every
    // back edge land in different pieces (otherwise the piece would close that
    // back edge into a cycle and stop being a tree).
    //
    // We decide the cuts with a bottom-up DP. For each vertex v its "block" is
    // the piece containing v inside v's subtree; the relevant facts about it
    // are whether it already has two vertices and up_target, the depth of the
    // closest ancestor it still reaches through a back edge. The block must be
    // cut before climbing to that ancestor. Processing v's children one by one
    // we either cut a child's block off as a finished country (allowed only
    // when that block already has size two or more) or merge it into v's block
    // (allowed only when the child's deepest pending back edge stays strictly
    // above v, so no back edge becomes internal). plan[v] stores, for every
    // reachable (size, deepest-target) state, which choice was made per child,
    // which lets build_country replay the cuts.
    //
    // A valid division can need a country that is connected only through a back
    // edge, which no single rooted tree expresses. So we try each vertex as the
    // root and accept the first DFS tree whose whole block is finishable with
    // size at least two.

    nb = n + 2;
    adj.assign(n + 1, {});
    for(auto& e: edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    int root = 1;
    while(root <= n && !partition_from(root)) {
        root++;
    }

    vector<int> label(n + 2, 0);
    int last = 0;
    for(int v = 1; v <= n; v++) {
        if(!label[country[v]]) {
            label[country[v]] = ++last;
        }
        country[v] = label[country[v]];
    }

    for(int v = 1; v <= n; v++) {
        cout << country[v] << " \n"[v == n];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys

# Increase recursion limit because we use recursive DFS.
sys.setrecursionlimit(1000000)


def solve():
    # Read all integers from input at once.
    data = list(map(int, sys.stdin.read().split()))

    # Pointer into the input array.
    ptr = 0

    # Number of test cases.
    t = data[ptr]
    ptr += 1

    # Store output lines here.
    out_lines = []

    # Process each test case.
    for _ in range(t):
        # Read number of vertices and edges.
        n = data[ptr]
        m = data[ptr + 1]
        ptr += 2

        # Read edges.
        edges = []
        for _ in range(m):
            a = data[ptr]
            b = data[ptr + 1]
            ptr += 2
            edges.append((a, b))

        # Build adjacency list.
        adj = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        # Base used for encoding states.
        nb = n + 2

        # Encode DP state into one integer.
        #
        # big:
        #   0 means current block has exactly one vertex.
        #   1 means current block has at least two vertices.
        #
        # target:
        #   -1 means no pending back edge to an ancestor.
        #   otherwise, it is the depth of the closest ancestor reached
        #   by a back edge from this block.
        def encode(big, target):
            return big * nb + (target + 1)

        # Try to construct a valid partition using a fixed DFS root.
        def partition_from(root):
            # DFS tree children.
            kids = [[] for _ in range(n + 1)]

            # Depth of each vertex in DFS tree.
            dep = [0] * (n + 1)

            # Parent of each vertex.
            par = [0] * (n + 1)

            # up_target[v] is closest ancestor reached by a back edge from v.
            up_target = [-1] * (n + 1)

            # Visited array for DFS.
            seen = [False] * (n + 1)

            # plan[v] maps encoded state to the decisions producing it.
            #
            # Decision format:
            #   (child, action, child_state)
            #
            # action = 0 means cut child as a separate country.
            # action = 1 means merge child into current country.
            plan = [dict() for _ in range(n + 1)]

            # Standard DFS that also records back edges.
            def dfs(v, p, d):
                # Mark vertex as visited.
                seen[v] = True

                # Store parent and depth.
                par[v] = p
                dep[v] = d

                # Initially there is no back edge from v to an ancestor.
                up_target[v] = -1

                # Explore all neighbors.
                for u in adj[v]:
                    # Ignore the tree edge to parent.
                    if u == p:
                        continue

                    # If u is unvisited, it becomes a DFS child.
                    if not seen[u]:
                        kids[v].append(u)
                        dfs(u, v, d + 1)

                    # If u was already seen and is an ancestor,
                    # edge v-u is a back edge.
                    elif dep[u] < d:
                        # Store the closest ancestor, i.e. maximum depth.
                        up_target[v] = max(up_target[v], dep[u])

            # Bottom-up DP.
            def build_dp(v):
                # First process all children.
                for c in kids[v]:
                    build_dp(c)

                # Initially the block contains only v.
                # It is not big, and its pending target is up_target[v].
                cur = {
                    encode(0, up_target[v]): []
                }

                # Process children one by one.
                for c in kids[v]:
                    # States after processing this child.
                    nxt = {}

                    # Iterate over current states.
                    for state, decisions in cur.items():
                        # Decode current target.
                        target = state % nb - 1

                        # ------------------------------------------------
                        # Option 1: cut child as a separate country.
                        # This is allowed only if child's block is big.
                        # ------------------------------------------------
                        for child_state in plan[c].keys():
                            child_big = child_state // nb

                            if child_big == 1:
                                # State of v's block does not change.
                                if state not in nxt:
                                    nxt[state] = decisions + [
                                        (c, 0, child_state)
                                    ]

                                # One suitable child state is enough.
                                break

                        # ------------------------------------------------
                        # Option 2: merge child into v's block.
                        # ------------------------------------------------
                        for child_state in plan[c].keys():
                            # Decode child's pending target.
                            child_target = child_state % nb - 1

                            # Safe only if child has no back edge to v.
                            # All pending back edges must go strictly above v.
                            if child_target <= dep[v] - 1:
                                # Merged block is definitely big.
                                merged_state = encode(
                                    1,
                                    max(target, child_target)
                                )

                                # Store first way to obtain this state.
                                if merged_state not in nxt:
                                    nxt[merged_state] = decisions + [
                                        (c, 1, child_state)
                                    ]

                    # Continue with updated states.
                    cur = nxt

                # Store DP result for v.
                plan[v] = cur

            # Build country assignments from stored decisions.
            country = [0] * (n + 1)
            next_country = [1]

            def build_country(v, state, cid):
                # Assign current vertex to country cid.
                country[v] = cid

                # Replay decisions for this DP state.
                for c, action, child_state in plan[v][state]:
                    if action == 1:
                        # Child is merged into same country.
                        build_country(c, child_state, cid)
                    else:
                        # Child is cut; create a new country id.
                        next_country[0] += 1
                        build_country(c, child_state, next_country[0])

            # Build DFS tree from this root.
            dfs(root, 0, 0)

            # Run DP.
            build_dp(root)

            # Required final state for the root block:
            # size at least two and no pending ancestor target.
            whole = encode(1, -1)

            # If impossible, this root fails.
            if whole not in plan[root]:
                return None

            # Reconstruct answer.
            build_country(root, whole, 1)

            # Return country assignment.
            return country

        # Try all possible roots.
        answer = None
        for root in range(1, n + 1):
            answer = partition_from(root)
            if answer is not None:
                break

        # The problem guarantees that a solution exists.
        country = answer

        # Compress country labels to 1..k in order of first appearance.
        label = {}
        compressed = []
        last = 0

        for v in range(1, n + 1):
            cid = country[v]

            if cid not in label:
                last += 1
                label[cid] = last

            compressed.append(str(label[cid]))

        # Add this test case output.
        out_lines.append(" ".join(compressed))

    # Print all answers.
    sys.stdout.write("\n".join(out_lines))


if __name__ == "__main__":
    solve()
```

---

## 5. Compressed editorial

Root the graph and take a DFS tree. In an undirected DFS, every non-tree edge connects an ancestor and a descendant. If a country contains both endpoints of such a back edge, then the back edge plus the DFS-tree path creates a cycle, so this is forbidden.

Use DP on the DFS tree. For each vertex `v`, maintain states for the unfinished block containing `v`:

- whether its size is already at least two,
- the closest ancestor depth reached by a back edge from this block, or `-1`.

For every child, either:

1. cut the child block as a finished country, allowed only if it already has size at least two;
2. merge it into `v`'s block, allowed only if its pending back edge target is strictly above `v`.

At the root, require state `(size at least two, target = -1)`. Store transitions to reconstruct country ids. Try every vertex as DFS root and output the first successful partition.
