<|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++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int n, m;

// Original graph.
vector<vector<int>> adj;

// DFS tree information.
vector<vector<int>> kids;
vector<int> dep;
vector<int> up_target;
vector<char> seen;

// DP reconstruction data.
//
// plan[v][state] = list of decisions used to obtain this state.
//
// A decision is:
//   {child, action, child_state}
//
// action = 0 means child component was cut;
// action = 1 means child component was merged.
vector<map<int, vector<array<int, 3>>>> plan;

// Final country assignment.
vector<int> country;
int next_country;

// State encoding base.
int nb;

// Encode state (big, target) as one integer.
// big is 0 or 1.
// target is -1 or a depth value.
int encode_state(int big, int target) {
    return big * nb + (target + 1);
}

// Decode big flag from encoded state.
int get_big(int state) {
    return state / nb;
}

// Decode target from encoded state.
int get_target(int state) {
    return state % nb - 1;
}

// Build DFS tree and compute back-edge information.
void dfs(int v, int parent, int depth) {
    seen[v] = 1;
    dep[v] = depth;
    up_target[v] = -1;

    for (int u : adj[v]) {
        if (u == parent) {
            continue;
        }

        if (!seen[u]) {
            kids[v].push_back(u);
            dfs(u, v, depth + 1);
        } else if (dep[u] < dep[v]) {
            // u is an ancestor of v, so v-u is a back edge.
            // We keep the deepest such ancestor.
            up_target[v] = max(up_target[v], dep[u]);
        }
    }
}

// Bottom-up DP on the DFS tree.
void build_dp(int v) {
    // First compute DP for children.
    for (int c : kids[v]) {
        build_dp(c);
    }

    // Current reachable states after processing some children.
    map<int, vector<array<int, 3>>> cur;

    // Initially the unfinished component is only {v}.
    cur[encode_state(0, up_target[v])] = {};

    // Process children one by one.
    for (int c : kids[v]) {
        map<int, vector<array<int, 3>>> nxt;

        for (auto &[state, decisions] : cur) {
            int current_target = get_target(state);

            // ------------------------------------------------------------
            // Option 1: cut child c as a separate country.
            // Allowed only if child's component is already big.
            // ------------------------------------------------------------
            for (auto &[child_state, child_decisions] : plan[c]) {
                if (get_big(child_state) == 1) {
                    if (!nxt.count(state)) {
                        nxt[state] = decisions;
                        nxt[state].push_back({c, 0, child_state});
                    }

                    // One valid child state is enough for this transition.
                    break;
                }
            }

            // ------------------------------------------------------------
            // Option 2: merge child c into v's component.
            // Safe only if child's pending back edges go strictly above v.
            // ------------------------------------------------------------
            for (auto &[child_state, child_decisions] : plan[c]) {
                int child_target = get_target(child_state);

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

                    if (!nxt.count(merged_state)) {
                        nxt[merged_state] = decisions;
                        nxt[merged_state].push_back({c, 1, child_state});
                    }
                }
            }
        }

        cur.swap(nxt);
    }

    plan[v] = cur;
}

// Reconstruct country ids using stored DP decisions.
void build_country(int v, int state, int id) {
    country[v] = id;

    for (auto &[c, action, child_state] : plan[v][state]) {
        if (action == 1) {
            // Child was merged into the same country.
            build_country(c, child_state, id);
        } else {
            // Child was cut, so it starts a new country.
            ++next_country;
            build_country(c, child_state, next_country);
        }
    }
}

// Try to find a valid partition using a fixed DFS root.
bool partition_from_root(int root) {
    kids.assign(n + 1, {});
    dep.assign(n + 1, 0);
    up_target.assign(n + 1, -1);
    seen.assign(n + 1, 0);
    plan.assign(n + 1, {});

    dfs(root, 0, 0);

    build_dp(root);

    // Root's final component must be a valid country:
    // size at least 2 and no pending back edge to an ancestor.
    int final_state = encode_state(1, -1);

    if (!plan[root].count(final_state)) {
        return false;
    }

    country.assign(n + 1, 0);
    next_country = 1;

    build_country(root, final_state, 1);

    return true;
}

void solve_one() {
    cin >> n >> m;

    adj.assign(n + 1, {});

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    nb = n + 2;

    // Try every possible DFS root.
    bool ok = false;

    for (int root = 1; root <= n; root++) {
        if (partition_from_root(root)) {
            ok = true;
            break;
        }
    }

    // The problem guarantees that a solution exists.
    // Therefore ok should always be true.
    (void)ok;

    // Compress country ids to 1..k.
    vector<int> compressed_id(n + 1, 0);
    int cnt = 0;

    for (int v = 1; v <= n; v++) {
        int id = country[v];

        if (compressed_id[id] == 0) {
            compressed_id[id] = ++cnt;
        }

        country[v] = compressed_id[id];
    }

    for (int v = 1; v <= n; v++) {
        if (v > 1) cout << ' ';
        cout << country[v];
    }

    cout << '\n';
}

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

    int tst;
    cin >> tst;

    while (tst--) {
        solve_one();
    }

    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()
```