<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

413. Berland Division
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

It is widely known that Berland consists of an even number of cities connected by bidirectional roads. It is possible to travel between every pair of cities using the roads. There is no such pair of cities which is connected by more than one road, and there is no road wich connects a city to itself. Due to the raised conflicts Berland can not exist as a single country. People don't want to share one roof anymore. It was decided to create the Berland Union and divide the Berland into several countries. There were two basic conditions. Firstly, every country must consist of not less than two cities, because no city can survive without help of other cities. Secondly, there must be exactly one path between each pair of cities from one country, which passes through the cities of this country. Help to create the division plan which fulfills these two requirements. Note that you don't need to minimize the number of countries.
Input
Input contains several test cases. The number of test cases tst (1 ≤ tst ≤ 50) is given on the first line of the input. Each test decription consists of a line with two integers n and m (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000, n — even) — number of cities and roads correspondingly. Each of the following m lines contains two integer numbers a and b (1 ≤ a < b ≤ n), describing the road between a and b. The total number of cities in all of the cases doesn't exceed 100, and the total number of roads doesn't exceed 1000.
Output
For each test case output n numbers on a separate line: i-th number should be the number of country which i-th city belongs to. Countries must be numerated from 1 to k, where k is the number of countries in your plan. If there are several solutions, output any of them.
Example(s)
sample input
sample output
2
4 3
1 2
2 3
1 4
4 4
1 2
2 3
1 4
1 3
1 1 1 1
1 2 2 1

<|response|>
## 1. Abridged problem statement

Given a connected simple undirected graph with an even number `n` of vertices, partition all vertices into several groups called countries.

Each country must:

1. contain at least two vertices;
2. have exactly one path between every pair of its vertices using only vertices of this country.

Output any valid country number for every vertex.

The second condition means that the subgraph induced by every country must be a tree.

---

## 2. Key observations

### Observation 1: A country must induce a tree

For a set of vertices to have exactly one path between every pair:

- it must be connected;
- it must not contain a cycle.

So every country must be an induced tree.

---

### Observation 2: Use a DFS spanning tree

Root the graph and build a DFS tree.

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

If we cut some edges of the DFS tree, each remaining component is connected by tree edges. Such a component is valid iff:

1. its size is at least `2`;
2. it does not contain both endpoints of any back edge.

If a component contains both endpoints of a back edge, then the back edge plus the DFS-tree path between its endpoints creates a cycle.

---

### Observation 3: DP on DFS tree

For every vertex `v`, consider the unfinished component containing `v` inside the DFS subtree of `v`.

We only need to know:

- whether this component already has at least two vertices;
- the deepest ancestor reached by a back edge from this component.

Let this state be:

```text
(big, target)
```

where:

- `big = 0`: current component has size `1`;
- `big = 1`: current component has size at least `2`;
- `target = -1`: no back edge from this component to an ancestor;
- otherwise `target` is the maximum depth of an ancestor reached by a back edge.

Why maximum depth? Because the dangerous back edge is the one going to the closest ancestor.

---

## 3. Full solution approach

For every possible DFS root, do the following.

### Step 1: Build DFS tree

During DFS, compute:

```text
dep[v]       = depth of v
kids[v]      = DFS children of v
up_target[v] = deepest ancestor directly connected to v by a back edge
```

If there is no such back edge, then:

```text
up_target[v] = -1
```

---

### Step 2: Bottom-up DP

For each vertex `v`, compute all possible states of the unfinished component containing `v`.

Initially, before processing children:

```text
component = {v}
big = 0
target = up_target[v]
```

Now process each DFS child `c` of `v`.

For the child component, we have two choices.

---

### Choice 1: Cut the child component

The child component becomes a separate country.

This is allowed only if the child component already has size at least `2`.

So if child state is:

```text
(child_big, child_target)
```

then cutting is allowed when:

```text
child_big = 1
```

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

Back edges from that child component to ancestors outside it are fine, because roads between different countries do not affect the induced subgraph of one country.

---

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

We keep the DFS tree edge `v-c`.

This is allowed only if the child component has no back edge to `v`.

If there is a back edge from the child component to `v`, then after merging we would create a cycle.

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

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

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

After merging:

```text
new_big = 1
new_target = max(current_target, child_target)
```

---

### Step 3: Root condition

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

Therefore the final state must be:

```text
big = 1
target = -1
```

The root has no ancestors, so there must be no pending back edge.

---

### Step 4: Reconstruction

During DP, store which choice was used for every child.

Then recursively reconstruct the answer:

- if child was merged, it receives the same country id;
- if child was cut, it receives a new country id.

Finally, compress country ids to `1..k`.

---

### Why try all roots?

For this problem, it is known that for every connected graph with even `n`, at least one DFS root allows such a decomposition. Since `n <= 100`, we can simply try all roots and use the first one that works.

---

### Complexity

For one DFS root:

- there are `O(n)` possible DP states per vertex;
- combining states is small because `n <= 100`.

Trying all roots is easily fast enough for the constraints.

---

## 4. 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;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

sys.setrecursionlimit(10 ** 7)


def solve():
    data = list(map(int, sys.stdin.read().split()))
    ptr = 0

    t = data[ptr]
    ptr += 1

    answers = []

    for _ in range(t):
        n = data[ptr]
        m = data[ptr + 1]
        ptr += 2

        adj = [[] for _ in range(n + 1)]

        for _ in range(m):
            a = data[ptr]
            b = data[ptr + 1]
            ptr += 2

            adj[a].append(b)
            adj[b].append(a)

        # Base for encoding states.
        nb = n + 2

        def encode_state(big, target):
            """
            Encode state (big, target) into one integer.

            big:
                0 = current component has size 1
                1 = current component has size at least 2

            target:
                -1 = no back edge to an ancestor
                otherwise depth of deepest ancestor reached by a back edge
            """
            return big * nb + (target + 1)

        def get_big(state):
            return state // nb

        def get_target(state):
            return state % nb - 1

        def partition_from_root(root):
            # DFS tree.
            kids = [[] for _ in range(n + 1)]

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

            # up_target[v] = deepest ancestor connected to v by a back edge.
            up_target = [-1] * (n + 1)

            seen = [False] * (n + 1)

            # plan[v][state] = decisions used to obtain this state.
            #
            # Decision format:
            #   (child, action, child_state)
            #
            # action = 0: cut child
            # action = 1: merge child
            plan = [dict() for _ in range(n + 1)]

            def dfs(v, parent, depth):
                seen[v] = True
                dep[v] = depth
                up_target[v] = -1

                for u in adj[v]:
                    if u == parent:
                        continue

                    if not seen[u]:
                        kids[v].append(u)
                        dfs(u, v, depth + 1)
                    elif dep[u] < dep[v]:
                        # u is an ancestor of v.
                        up_target[v] = max(up_target[v], dep[u])

            def build_dp(v):
                # Process children first.
                for c in kids[v]:
                    build_dp(c)

                # Initially, component contains only v.
                cur = {
                    encode_state(0, up_target[v]): []
                }

                # Process every child.
                for c in kids[v]:
                    nxt = {}

                    for state, decisions in cur.items():
                        current_target = get_target(state)

                        # ------------------------------------------------
                        # Option 1: cut child as a separate country.
                        # Allowed only if child's component is already big.
                        # ------------------------------------------------
                        for child_state in plan[c]:
                            if get_big(child_state) == 1:
                                if state not in nxt:
                                    nxt[state] = decisions + [
                                        (c, 0, child_state)
                                    ]

                                # One such state is enough.
                                break

                        # ------------------------------------------------
                        # Option 2: merge child into current component.
                        # Safe only if child has no back edge to v.
                        # ------------------------------------------------
                        for child_state in plan[c]:
                            child_target = get_target(child_state)

                            if child_target <= dep[v] - 1:
                                merged_state = encode_state(
                                    1,
                                    max(current_target, child_target)
                                )

                                if merged_state not in nxt:
                                    nxt[merged_state] = decisions + [
                                        (c, 1, child_state)
                                    ]

                    cur = nxt

                plan[v] = cur

            country = [0] * (n + 1)
            next_country = [1]

            def build_country(v, state, cid):
                country[v] = cid

                for c, action, child_state in plan[v][state]:
                    if action == 1:
                        # Merged child: same country.
                        build_country(c, child_state, cid)
                    else:
                        # Cut child: new country.
                        next_country[0] += 1
                        build_country(c, child_state, next_country[0])

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

            # Run DP.
            build_dp(root)

            # Final state required for the root component.
            final_state = encode_state(1, -1)

            if final_state not in plan[root]:
                return None

            build_country(root, final_state, 1)

            return country

        result = None

        # Try all roots.
        for root in range(1, n + 1):
            result = partition_from_root(root)

            if result is not None:
                break

        # A valid root always exists.
        country = result

        # Compress country labels to 1..k.
        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]))

        answers.append(" ".join(compressed))

    sys.stdout.write("\n".join(answers))


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