<|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.

121. Bridges painting

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


New Berland consists of N (1£ N£ 100) islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).


Input

There is N on the fisrt line of input. Next N lines contain a list of islands connected with given island. Every list is finished by 0.


Output

If needed painting exists then write N lines. Write “1” and “2” in each line. Write “1” if bridge is painted white and “2” in other case. Write 0 at the end of any list. If needed painting does not exist then write “No solution”.


Sample Input

6
2 3 0
1 3 0
1 2 5 0
5 0
4 6 3 0
5 0
Sample Output

1 2 0
1 2 0
2 2 1 0
2 0
2 2 1 0
2 0
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged problem statement
Given an undirected simple graph on N islands (vertices) and bridges (edges), paint each bridge either color 1 (white) or color 2 (black) so that every island of degree ≥ 2 has at least one incident bridge of each color. Islands of degree 0 or 1 have no additional requirement. If such a coloring exists, output for each island the colors of its incident bridges in the same order as the input (ending the list with 0). Otherwise, output “No solution”.

2. Key observations
- If you take a trail (a walk without repeating edges) and color edges alternately 1,2,1,2,… then every interior vertex of that trail sees both colors on its two incident trail-edges.
- To cover all edges in a connected component, one would like an Eulerian trail or circuit. A connected graph has an Eulerian circuit exactly when every vertex has even degree.
- If some vertices have odd degree, we can pair them arbitrarily by adding “fake” edges. This makes all degrees even and allows extraction of an Eulerian circuit on the augmented graph.
- Once we have such a circuit, we split it at fake edges into maximal sub-trails consisting only of real edges, and then color each sub-trail alternately.
- Interior vertices of each sub-trail get both colors. Endpoints of sub-trails coincide with fake-edge incidences (or real degree-1 vertices), which is acceptable. Finally, verify that every original vertex of degree ≥ 2 indeed sees both colors.

3. Full solution approach
a. Read N and build the graph:
   - Assign each undirected bridge a unique ID `e`.
   - Maintain for each island a list of incident edge IDs in input order so we can reproduce the required output order.
   - Build an adjacency list of oriented edges: for real edge e=(u,v), store (u → v, code = 2·e) and (v → u, code = 2·e+1).

b. Find all vertices of odd degree (in the real graph). Pair them arbitrarily and add a fake edge per pair, with IDs ≥ m so their codes are ≥ 2·m.

c. On the augmented graph (real + fake edges), run Hierholzer’s algorithm to decompose each component into Eulerian circuits, using a per-vertex adjacency pointer and a `used` array over edges.

d. For each Eulerian circuit, rotate it cyclically so that if it contains a fake edge it starts at one. Then split the circuit at every fake edge into segments of consecutive real edges; each segment is a maximal real-only trail.

e. Color each real-only trail alternately starting with color 1, flipping the color edge by edge. As you color an oriented edge, record on both endpoints (via a bitmask) which color they have seen.

f. After coloring all trails, verify that every vertex whose original degree ≥ 2 has seen both colors (bitmask == 0b110 == 6). If any fails, print “No solution”.

g. Otherwise, for each island u (in order 1…N), print the colors of its incident real-edges (in input order) followed by 0.

4. C++ implementation
```cpp
#include <bits/stdc++.h>
// #include <coding_library/graph/eulerian_paths.hpp>

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;
};

class EulerianPaths {
  private:
    void dfs(int u, vector<int>& path, vector<bool>& used, vector<int>& po) {
        for(; po[u] < (int)adj[u].size();) {
            int idx = po[u]++;
            if(!used[adj[u][idx].second >> 1]) {
                used[adj[u][idx].second >> 1] = true;
                dfs(adj[u][idx].first, path, used, po);
                path.push_back(adj[u][idx].second);
            }
        }
    }

  public:
    int n, m;
    vector<int> deg;
    vector<vector<pair<int, int>>> adj;
    vector<pair<int, int>> edges;

    EulerianPaths(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        m = 0;
        adj.assign(n + 1, {});
        deg.assign(n + 1, 0);
        edges.clear();
    }

    int add_edge(int u, int v) {
        adj[u].push_back({v, m * 2});
        adj[v].push_back({u, m * 2 + 1});
        edges.push_back({u, v});
        deg[u]++;
        deg[v]++;
        m++;

        return edges.size() - 1;
    }

    vector<vector<int>> find_paths() {
        vector<bool> used(m, false);
        vector<int> po(n + 1, 0);

        vector<int> odd_vertices;
        for(int i = 0; i <= n; i++) {
            if(deg[i] % 2 == 1) {
                odd_vertices.push_back(i);
            }
        }

        int total_edges = m;
        for(int i = 0; i < (int)odd_vertices.size() / 2; i++) {
            int u = odd_vertices[2 * i], v = odd_vertices[2 * i + 1];
            adj[u].push_back({v, 2 * total_edges});
            adj[v].push_back({u, 2 * total_edges + 1});
            total_edges++;
            used.push_back(false);
            edges.push_back({u, v});
        }

        vector<vector<int>> paths;
        for(int u = 0; u <= n; u++) {
            if(!adj[u].empty()) {
                vector<int> path;
                dfs(u, path, used, po);
                if(!path.empty()) {
                    auto it = find_if(path.begin(), path.end(), [&](int x) {
                        return x >= 2 * m;
                    });
                    if(it != path.end()) {
                        rotate(path.begin(), it, path.end());
                    }

                    vector<int> current_path;
                    for(int x: path) {
                        if(x < 2 * m) {
                            current_path.push_back(x);
                        } else if(!current_path.empty()) {
                            paths.push_back(current_path);
                            current_path.clear();
                        }
                    }
                    if(!current_path.empty()) {
                        paths.push_back(current_path);
                    }
                }
            }
        }

        return paths;
    }

    pair<int, int> get_edge(int edge_i) {
        if(edge_i & 1) {
            return edges[edge_i >> 1];
        } else {
            return {edges[edge_i >> 1].second, edges[edge_i >> 1].first};
        }
    }

    vector<pair<int, int>> get_path_edges(const vector<int>& path) {
        vector<pair<int, int>> result;
        for(int edge_i: path) {
            result.push_back(get_edge(edge_i));
        }
        return result;
    }

    bool is_cycle(const vector<int>& path) {
        int start = get_edge(path[0]).first;
        int end = get_edge(path.back()).second;
        return start == end;
    }
};

int n;
map<pair<int, int>, int> edge_id;
vector<vector<int>> input;
EulerianPaths ep;

void read() {
    cin >> n;
    input.resize(n);
    ep.init(n);
    for(int i = 0; i < n; i++) {
        input[i].clear();
        int x;
        cin >> x;
        while(x != 0) {
            x--;
            if(edge_id.count({i, x})) {
                input[i].push_back(edge_id[{i, x}]);
            } else {
                int edge = ep.add_edge(i, x);
                edge_id[{x, i}] = edge;
                edge_id[{i, x}] = edge;
                input[i].push_back(edge);
            }
            cin >> x;
        }
    }
}

void solve() {
    // Each bridge must be coloured white(1)/black(2) so that every island with
    // degree >= 2 touches at least one of each colour. Build a multigraph and
    // pair up odd-degree vertices with extra "fake" edges so the graph becomes
    // Eulerian; an Euler trail then alternates colours edge by edge along its
    // path. Walking a trail and flipping the colour at every step guarantees
    // that any internal vertex (where the trail passes through) sees both
    // colours; the fake edges only split trails and are ignored when emitting
    // the answer. After colouring we verify each island of degree >= 2 has both
    // colours present (mask == 0b110, i.e. bits for colour 1 and 2 set);
    // otherwise there is no solution.

    vector<int> state(ep.m, -1);
    vector<int> mask(n, 0);
    auto paths = ep.find_paths();
    for(auto& path: paths) {
        int f = 1;
        for(int edge_2x: path) {
            state[edge_2x >> 1] = f;
            auto [u, v] = ep.get_edge(edge_2x);
            mask[u] |= 1 << f;
            mask[v] |= 1 << f;
            f = 3 - f;
        }
    }

    const int need_mask = 6;
    for(int i = 0; i < n; i++) {
        if(ep.deg[i] >= 2 && mask[i] != need_mask) {
            cout << "No solution\n";
            return;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int edge: input[i]) {
            cout << state[edge] << ' ';
        }
        cout << "0\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys
sys.setrecursionlimit(10**7)

def read_graph():
    """Read input, assign a unique ID to each undirected bridge,
       return N, edge list, degrees, and per-vertex input order."""
    N = int(sys.stdin.readline())
    edge_id = {}            # map sorted (u,v)->eid
    edges = []              # edges[e] = (u,v)
    degree = [0]*N
    input_order = [[] for _ in range(N)]

    for u in range(N):
        for tok in sys.stdin.readline().split():
            v = int(tok)
            if v == 0:
                break
            v -= 1
            a, b = min(u,v), max(u,v)
            if (a,b) in edge_id:
                e = edge_id[(a,b)]
            else:
                e = len(edges)
                edges.append((u,v))
                edge_id[(a,b)] = e
                degree[u] += 1
                degree[v] += 1
            input_order[u].append(e)
    return N, edges, degree, input_order

def build_augmented_adj(N, edges, degree):
    """Build adjacency with real edges oriented as eid2 = 2*e or 2*e+1.
       Then pair odd-degree vertices with fake edges."""
    m = len(edges)
    adj = [[] for _ in range(N)]
    # real edges
    for e, (u,v) in enumerate(edges):
        adj[u].append((v, 2*e))
        adj[v].append((u, 2*e+1))
    # pair odd vertices
    odds = [u for u in range(N) if degree[u] % 2 == 1]
    fake_e = m
    for i in range(0, len(odds), 2):
        u, v = odds[i], odds[i+1]
        adj[u].append((v, 2*fake_e))
        adj[v].append((u, 2*fake_e+1))
        fake_e += 1
    return adj, fake_e

def extract_trails(adj, total_e):
    """Run Hierholzer on the augmented graph of total_e edges (real+fake),
       return a list of real-only trails (each is a list of eid2 codes)."""
    used = [False]*total_e
    ptr = [0]*len(adj)
    trails = []

    def dfs(u, path):
        while ptr[u] < len(adj[u]):
            v, eid2 = adj[u][ptr[u]]
            ptr[u] += 1
            e = eid2 >> 1
            if not used[e]:
                used[e] = True
                dfs(v, path)
                path.append(eid2)

    for u in range(len(adj)):
        if ptr[u] < len(adj[u]):
            path = []
            dfs(u, path)
            if not path:
                continue
            # rotate so that if there is a fake edge, we start there
            first_fake = next((i for i,x in enumerate(path) if (x>>1) >= total_e//2), None)
            if first_fake is not None:
                path = path[first_fake:] + path[:first_fake]
            # split at fake edges
            cur = []
            for eid2 in path:
                e = eid2 >> 1
                if e < total_e//2:
                    cur.append(eid2)
                elif cur:
                    trails.append(cur)
                    cur = []
            if cur:
                trails.append(cur)
    return trails

def solve():
    N, edges, degree, input_order = read_graph()
    adj, fake_end = build_augmented_adj(N, edges, degree)
    total_edges = fake_end  # real edges = len(edges), fake_end = real + fake

    # get all real-only trails
    trails = extract_trails(adj, total_edges)

    m = len(edges)
    color = [-1]*m           # final color of each real edge
    mask = [0]*N             # bitmask of colors seen at each vertex

    # color each trail alternately
    for trail in trails:
        c = 1
        for eid2 in trail:
            e = eid2 >> 1
            if e >= m:
                # shouldn't happen in a real-only trail
                continue
            color[e] = c
            u,v = edges[e]
            # if eid2&1==1 then orientation was reversed
            if eid2 & 1:
                u, v = v, u
            mask[u] |= 1<<c
            mask[v] |= 1<<c
            c = 3 - c

    # verify all high-degree vertices saw both colors
    for u in range(N):
        if degree[u] >= 2 and mask[u] != (1<<1)|(1<<2):
            print("No solution")
            return

    # output in input order
    out = []
    for u in range(N):
        line = [str(color[e]) for e in input_order[u]]
        line.append('0')
        out.append(' '.join(line))
    print('\n'.join(out))

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

Explanation of the main steps:
- We make the graph Eulerian by pairing odd vertices with fake edges.
- We run Hierholzer’s algorithm to get circuits covering all edges.
- Rotating and splitting at fake edges gives us real-only trails.
- Alternating coloring on each trail guarantees interior vertices see both colors.
- A final check ensures every original high-degree vertex indeed has both colors.
