{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "42902ea1",
   "metadata": {},
   "source": [
    "# Maximum flow problem"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87820260",
   "metadata": {},
   "source": [
    "***max_flow.ipynb***\n",
    "\n",
    "Finding the maximum number of vertex-disjoint paths between two nodes in a telecommunications network.\n",
    "\n",
    "© Copyright 2025 Fair Isaac Corporation\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0.\n",
    " \n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "\n",
    "This example uses FICO® Xpress software. By running it, you agree to the Community License terms of the [Xpress Shrinkwrap License Agreement](https://www.fico.com/en/shrinkwrap-license-agreement-fico-xpress-optimization-suite-on-premises) with respect to the FICO® Xpress software. See the [licensing options](https://www.fico.com/en/fico-xpress-trial-and-licensing-options) overview for additional details and information about obtaining a paid license."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70ade133",
   "metadata": {},
   "source": [
    "## Problem description and formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "657415c5",
   "metadata": {},
   "source": [
    "We wish to test the reliability of a telecommunications network of eleven sites (nodes) connected by bidirectional data links.  The key requirement is that nodes 10 and 11 (the \\'source\\' and \\'sink\\') must remain connected even if any three other nodes fail.  By finding the maximum number of vertex‑disjoint paths between nodes 10 and 11, we quantify how many simultaneous failures can be tolerated while preserving connectivity.\n",
    "\n",
    "Let $\\mathcal{A} = \\{\\exists(i,j), \\forall i,j \\in \\mathcal{N}\\}$ be the set of existing undirected arcs in the network, and $f_{i,j}$ a binary decision variable equal to 1 if one unit of flow is sent along arc $i$ to $j$, and 0 otherwise. The source ($s = 10$) and sink ($t = 11$) nodes are defined *a priori*.\n",
    "\n",
    "We aim to maximize the number of disjoint paths starting from the source. Each arc $(s\\to j)$ carrying flow represents a distinct path out of $s$.  By maximizing this sum, we want to pack as many vertex‑disjoint routes as possible:\n",
    "\n",
    "$$\n",
    "\\max \\sum_{(s,j)\\in \\mathcal{A}} f_{s,j}\n",
    "$$\n",
    "\n",
    "* Flow conservation at intermediate nodes:\n",
    "   $$\n",
    "   \\sum_{(i,k)\\in \\mathcal{A}} f_{i,k}\n",
    "   \\;=\\;\n",
    "   \\sum_{(k,i)\\in \\mathcal{A}} f_{k,i},\n",
    "   \\quad\\forall\\,i\\in \\mathcal{N}\\setminus\\{s,t\\}.\n",
    "   $$\n",
    "   - Ensures that for any node $i$ other than $s$ or $t$, the number of incoming flow units equals the number of outgoing units, creating continuous paths.\n",
    "\n",
    "* Vertex capacity (at most one outgoing):\n",
    "   $$\n",
    "   \\sum_{(i,k)\\in \\mathcal{A}} f_{i,k}\n",
    "   \\;\\le\\; 1,\n",
    "   \\quad\\forall\\,i\\in \\mathcal{N}\\setminus\\{s,t\\}.\n",
    "   $$\n",
    "   - Limits each intermediate node to at most one unit of outgoing flow, preventing two paths from sharing that node.\n",
    "\n",
    "* No flow back into the source: \n",
    "   $$\n",
    "   \\sum_{(k,s)\\in \\mathcal{A}} f_{k,s}\n",
    "   \\;=\\; 0.\n",
    "   $$\n",
    "   - Do not any path from re‑entering the source, preserving a purely outward flow interpretation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5899ee3f",
   "metadata": {},
   "source": [
    "## Data preparation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d94ce83e",
   "metadata": {},
   "source": [
    "We firstly import the necessary packages and define the node set `NODES = [1…11]` and define `SOURCE=10` and `SINK=11`. We then list all the undirected links in the network in `base_arcs`, and create the directed arc list `ARCS` by adding both $(u,v)$ and $(v,u)$ for each undirected pair. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c59e2cec",
   "metadata": {},
   "outputs": [],
   "source": [
    "import xpress as xp\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Define nodes, source, and sink\n",
    "NODES = list(range(1, 12))  \n",
    "SOURCE, SINK = 10, 11\n",
    "\n",
    "# Undirected base arcs\n",
    "base_arcs = [\n",
    "    (1, 2), (1, 3), (1, 11),\n",
    "    (2, 3), (2, 8), (2, 9),\n",
    "    (3, 4), (3, 9), (3, 10), (3, 11),\n",
    "    (4, 5), (4, 6), (4, 11),\n",
    "    (5, 9), (5, 11),\n",
    "    (6, 7), (6, 9), (6, 10),\n",
    "    (7, 8), (7, 10),\n",
    "    (8, 10),\n",
    "    (9, 10)\n",
    "]\n",
    "\n",
    "# Make arcs bidirectional\n",
    "ARCS = []\n",
    "for u, v in base_arcs:\n",
    "    ARCS.append((u, v))\n",
    "    ARCS.append((v, u))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f3babeb",
   "metadata": {},
   "source": [
    "## Model implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a234848b",
   "metadata": {},
   "source": [
    "We create an Xpress problem named **Maxflow** and define a set of binary variables `flow` passing the list of arcs to [p.addVariables()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addVariables.html). This creates a dictionary whose keys are a tuple of indices.\n",
    "\n",
    "The **objective** is added via [p.setObjective()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.setObjective.html) to maximize the total flow leaving the source node. Then, three **constraint** sets are added by passing expressions directly to [p.addConstraint()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addConstraint.html) with list comprehension.\n",
    "\n",
    "After constructing the model, we invoke [p.optimize()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.optimize.html) to solve it.  We then retrieve the objective value to report the maximum number of disjoint paths, and report each path by tracing through arcs with $f_{i,j}=1$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49ae6aa7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total number of paths: 4\n",
      "10 - 3 - 11\n",
      "10 - 6 - 4 - 11\n",
      "10 - 8 - 2 - 1 - 11\n",
      "10 - 9 - 5 - 11\n"
     ]
    }
   ],
   "source": [
    "p = xp.problem(name=\"Maxflow\")\n",
    "\n",
    "# Binary variables for each directed arc\n",
    "flow = p.addVariables(ARCS, vartype=xp.binary, name=\"f\")\n",
    "\n",
    "# Objective function: maximize number of outgoing flow from SOURCE\n",
    "p.setObjective(\n",
    "    xp.Sum(flow[(SOURCE, n)] for n in NODES if (SOURCE, n) in flow),\n",
    "    sense=xp.maximize\n",
    ")\n",
    "\n",
    "# Constraints:\n",
    "# 1. Conservation: sum incoming = sum outgoing\n",
    "p.addConstraint(\n",
    "    xp.Sum(flow[(m,n)] for m in NODES if (m,n) in flow)\n",
    "  == xp.Sum(flow[(n,m)] for m in NODES if (n,m) in flow)\n",
    "    for n in NODES if n not in (SOURCE, SINK)\n",
    ")\n",
    "\n",
    "# 2. Capacity: at most one outgoing unit\n",
    "p.addConstraint(\n",
    "    xp.Sum(flow[(n,m)] for m in NODES if (n,m) in flow)\n",
    "    <= 1\n",
    "    for n in NODES if n not in (SOURCE, SINK)\n",
    ")\n",
    "\n",
    "# 3. No return to SOURCE\n",
    "p.addConstraint(\n",
    "    xp.Sum(flow[(m,SOURCE)] for m in NODES if (m, SOURCE) in flow)\n",
    "    == 0\n",
    ")\n",
    "\n",
    "# Solve the problem\n",
    "p.controls.outputlog = 0        # Turn off solver logging for cleaner output\n",
    "p.optimize()\n",
    "\n",
    "# Print total number of disjoint paths\n",
    "num_paths = int(p.attributes.objval)\n",
    "print(\"Total number of paths:\", num_paths)\n",
    "\n",
    "# Print each path\n",
    "paths = []\n",
    "sol = p.getSolution(flow)\n",
    "for n in NODES:\n",
    "    if (SOURCE, n) in flow and sol[(SOURCE, n)] > 0.5:\n",
    "        path = [SOURCE, n]\n",
    "        curr = n\n",
    "        while curr != SINK:\n",
    "            for m in NODES:\n",
    "                if sol.get((curr, m)) is not None and sol.get((curr, m)) > 0.5:\n",
    "                    path.append(m)\n",
    "                    curr = m\n",
    "                    break\n",
    "        paths.append(path)\n",
    "        print(\" - \".join(map(str, path)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83723816",
   "metadata": {},
   "source": [
    "## Visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3baf5545",
   "metadata": {},
   "source": [
    "The visualization consists of three key elements:\n",
    "* **Base network**: represented by grey lines, each corresponding to an undirected link from the `base_arcs` set.\n",
    "* **Flow paths**: shown as in differently coloured lines, indicating each directed arc where `flow[idx] = 1`.\n",
    "* **Nodes**: depicted as white circles placed at each $(x, y)$ coordinate, with the node number displayed above each circle. The node positions are defined by the node coordinates loaded from `POS_LIST` and stored in the dictionary `pos[node]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "85af9215",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAxYAAAIrCAYAAAByLQ9gAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjEsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvc2/+5QAAAAlwSFlzAAAPYQAAD2EBqD+naQAAS/hJREFUeJzt3QmclnW5//FrZlBglNhEhFPijlgqWqaWaxpkQqAg5l8E9SAJHktNzylPeSw0044cyRQXUFlKBFFQTEbsqGiKmUdIhVBQMQ0Q2UQBlZnn/7p+MMM9MMuz3Mtv+bxfr2mYDW7I+5m5nuv+3t+yXC6XEwAAAAAoQXkpXwwAAAAAisECAAAAQMkYLAAAAACUjMECAAAAQMkYLAAAAACUjMECAAAAQMkYLAAAAACUjMECAAAAQMkYLAAAAACUjMECADJy7bXXSllZWUFf884775ivue+++wr+8/Rr9Gv19/DF+eefL7vvvnvWhwEAYLAAgHjU/tBe+9KqVSvp2rWr9O7dW37729/Khg0bxGULFy40g1C+Q0nt0FT7UllZKYcccoj87Gc/k48++qigP3vjxo3m93v66aeLPHoAQBoYLAAgRr/85S9l0qRJMnbsWLn00kvN+y677DI59NBD5W9/+1u9z9Ufsjdt2lTQ79+tWzfzNeedd17Bx6Zfo1+rv0cxg8UvfvGLgrcd+u+g/x6jR4+Wgw8+WK6//nr5zne+I7lcrqDBQv9sBgsAsFuLrA8AAHxy2mmnyde+9rW6t3/605/K//7v/0qfPn3ke9/7nixatEhat25tPtaiRQvzUojabUgxKioqzEuaBg4cKHvssYf59cUXXywDBgyQhx56SObNmyfHHntsqscCAEgWGwsASNi3vvUt+fnPfy7Lli2TyZMnN5mxmDNnjhx33HHSrl07kx3o3r27XH311c1mLHR4Of7442W33XYzX9uvXz8zxDSXsdhnn33M0PPcc8/J17/+dTO07LfffjJx4sR6X3fWWWeZX5988sl1lzcVs0HQfwv19ttvy2effSbXXHONfPWrX5W2bduaY9e/w1NPPVXv79upUyfza91a1P7Z+m8X9f7770v//v3Nv5l+/pVXXinV1dX1PmfKlCnmz2rTpo184QtfMFukMWPGFPx3AAA0jMECAFJQe+nSE0880ejnvP766+aH/E8//dRcUnXzzTebLcef//znJn/vJ5980mQ5PvjgA/MD9xVXXCHPP/+8fPOb38zr0qUlS5aYzcK3v/1t82e2b9/ehKL1eNQJJ5wgP/zhD82vdcjRS5v0pUePHgX+K4gsXbrUvO7YsaPJWowbN05OOukkufHGG82xr1q1yvxd5s+fbz5PhwS9nEqdccYZdX/2mWeeWfd76gChX6O/53//93/LiSeeaP4ed911V72B7ZxzzjF/N/2zfv3rX5s/t7l/WwBA/rgUCgBS8MUvftE8K1/7g3VD9IdffRb/8ccfr7t8KB9XXXWVdOjQQV544QXzWumz90cccYT813/9l0yYMKHJr1+8eLHMnTvXbAvUoEGD5Etf+pLce++95gd13WDoxzSErsOH/kCerzVr1pjXH3/8sRmqbr/9duncubP5/Vq2bGkGn1133bXu8y+66CKTxbj11ltl/PjxZouhQ8+IESPksMMOk8GDB+/0Z2zevFnOPvtssxWqveTqyCOPNF+vX6cee+wxs6WoqqpK/XIwAAgFGwsASIleptPU3aH0EiY1c+ZMqampyev3XL58uXl2XzcMtUOF0h/CdQj44x//2OzvoXdrqh0qarcEegnWW2+9JaXS30d/v3333Vd+8IMfyAEHHGB+yNe7ROkP+LVDhf59dQjZsmWLyaj83//9X0F/jg4TUfr3iR6//tt+8sknZngDACSDwQIAUqLP2uv1/Y3RZ9318qVhw4aZZ/W///3vy9SpU5scMjS3UfsD/I70UqUPP/zQ/EDdlL333nun9+klQ2vXrpVSTZ8+3fwwr3kMveTqtddeMzmHWrpN0SFIsx16KZMOITp4rF+/Pu8/Q7+2NofR2PGPHDlSDjroIBOu1+3RhRdeKLNnzy757wcA2I7BAgBS8N5775kflvUZ+8bo3aL0kiTNTGgmQ29Pq8OGbh52DCLHqbFLgwq5JWxjNJ9x6qmnmtzD/vvvX+9jGmTXTYu+Xy9b0h/0dQjRgHe+G5umjj9qzz33NJudRx55xORWNCCuQ8bQoUOL+nsBAHbGYAEAKdDAsdKQcVPKy8vllFNOMb0P2h2hvQ96x6fonZKiajspNCexo7///e8mq6E5hVIV2hCejwcffNDkN/T2szpI6b+NDiGamUjiz9bLrvr27WtyHpp10Uuz9O5XukkBAJSOwQIAEqaDwahRo0zO4Nxzz2026BzVs2dP81rvFNWQLl26mM/RS4rWrVtX93695EjD0t/97ndj+TvUDifRP6NUtZuG6GbkxRdfNCH0KM1jlPpnr169eqcBTi/BaurfFgAQwF2h9DaBWjr1ox/9SG655ZasDwcA6ugdnXRToCHklStXmqFCL+/RzYJehtNUuZ3eYlYvhTr99NPN5+vtY/XZdc0EaLdFY37zm9+Yy3q0cO5f//VfTbu23lVJ70K1Y99DsXR40UFAb9Wql3TpHZ30kiW9xKhYemtd3VbobWT176zdFnfccYcJk2seJXqJmL7vgQceMDkJDal/5StfMS/50tyKDm56zPrvqdkU/TfSv1cxt811lfZ9/Md//If571QbzfXSPL37V7TUEUB29tlnn7rsXJTmxG677TaxnXODxUsvvSR33nln3TNNAGATLXyrvexGfwDWEjZ9AuSCCy5oMrit9Np/vf3qPffcY0LXehmTZhO0GE6HhMbo5UOaT9Bby+qfv8suu5iv0yFAtyRx2GuvvcwP/TfccIMZXjTzoZdnlTJYaL5ixYoV5jFdbwOrw4PmLqZNm7ZT+Z72XVx66aVy+eWXm1vy6t+1kMFCb1OrvRY6qOnmQ/8+ml/RwUu3FyHQMLveHEBLDnWw0MD7m2++aYLuAOz5Obc6kqnT7bPm7GpLSm1XlosjnZcSfQZL702u3xiuu+4680wTGwsAIdFsgD7LrJmNhjodgMb85Cc/MYWAzz77bNaHAiBPl112mcyaNcs8CZBE1i1uTj1Nc8kll5h1uT47BwAh0t4KVUiBHqD0Ujy95Emf+dRNkxYo3n333VkfFoBG6HZWt7h6e2wXhgqnLoWaMmWKKUzSFREAhEgvkdIXDTMfc8wxWR8OHKOFgWPHjpUrrrhCrr76avP99Ic//KG5bI/b7gL2mTFjhrl0Uy8bdYUTg8U//vEPE9TWAGRTwUcA8Nnw4cNNeFkzCLUt3UC+tBtENxa/+tWvzNu6sdDrtzU7w2AB2Gf8+PHmxhxdu3YVVzgxWLz88svm7iiar6ilwRa9e8rvfvc7c6vAfAqSAMBleqcpoFh6a2INyEfpHbG0HR2AXZYtW2bKUvXOeS5xYrDQsqhXX3213vv0DisHH3ywuW0eQwUAAE3TO0LtWKT4xhtv1JUsArDHvffea7JQmi12iRODhd6iccfbCmpZU8eOHQu63SAAAKHSW/V+4xvfMJdCDRo0SP7yl7+YW/DqCwC7Llu89957zSWKLVo48aO6m3eFAgAAxTnqqKPk4Ycflvvvv988Kadt8HrL9qba4AGk78knn5R3333X3A3KNU71WAAAAACwExsLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQMgYLAAAAACVjsAAAAABQshbikFwuJ6tXr5aPP/5Ydt99d+nYsaOUlZVlfVgAADiD76WA3XIOn6NObCzWrVsnY8aMkR49ekinTp1k3333Na/1bX2/fhwAADSO76WA3dZ5cI6W5XQsslhVVZUMGjRINm7cKAMGDDAv7du3l7Vr18r06dPNS2VlpUydOlV69+6d9eECAGAdvpcCdqvy5By1erDQf+Q+ffqYf8Bx48bJXnvttdPnrFixQoYNG2Y+d9asWVb/YwMAkDa+lwJ2q/LoHLV2sNB1T7du3eT444+XGTNmSIsWjcdBtmzZIv3795dnn31Wli1bJu3atUv1WAEAsBHfSwG7rfPsHLU2YzFhwgSzDtLJral/ZKUfv/vuu83nT5w4MbVjBADAZnwvBew2wbNz1MqNhR6SBlV69uwpU6ZMyfvrzj77bFmwYIEsWrTImfQ8AABJ4HspYLech+eolbeb1VtsLV68WEaNGlXQ12nQRUMtqyZ0kY5trF3GAACQuA8/qpHFi1cW/b104cKF0qFDh8SODwjd6hJ/3l2zZo25Fa1NrBws9L69StPwhaj9/I3rV8qeuyZyaAAAOGHTR1LS91K95KLQrwWQP73jUynn6IYNGxgs8qFlINF/8HzVfn5l285S3ZKNBQAgXK2/UCMiK4v+XnrRRRexsQAS3liMGTOm6HO0TZs2YhsyFgAAeIjvpYDdch6eo1Y+ra//SCNGjDBlIHrf3nwsX75cHnroIbn44out+0cGAMCl76UjR47keymQsDIPz1ErBws1dOhQ0zCoZSB6396m6Mf183bZZRepqakx/+gAAISu0O+levmTfv6QIUNSO0YgZEM9O0etHSy09EMT79owqGUgjQ0L+v5+/frJE088IePHjzf/2Hov4Keeekqqq6tTP24AAFz8Xqof18+bNm2alcVbgI/aeXaOWpmxiNJ/wEGDBpkykDPPPNPcYkvT8Bpc0dWRroN0U3HJJZfIjTfeaK5Xmzt3rjz33HPSqVMnM3R06dIl678GAAB2fi99cJo89PAM88Sc/sDSq1evrA8XCPIcPeuss2TTpk2N/rzrwjlq/WBRW3euDYO33367ud9vre7du5trzE488USZOXOmea0vtZOdvm/VqlVy3HHHyQknnCAVFRUZ/i0AALDwe+m/tJAR324h59/8jrTt0DnTYwRCNn36dJk0aZL8/e9/b/DnXb1sqm3btmIzJwaLWnqoWn6nPRV6S9lOQ5fXBVeeeeYZefrpp801Z/vuu695n14KxfYCAID630u1/E57Kn58wlL54qZZYr6VfvMBkW6Dsj48IEjV1dUyevRoOeyww8xGovYc1UzFIYccYmVQ26mMRUP0H1UbtffpJOZ19B/5+OOPNwOFTnu1BXu6oTj55JNNIEaRvQAAhE6/d2o/hV5mUXnwkK1DhYjULL0360MDgrVkyRJzqaLeejZ6juprV4YK5waLppSXl5tr0vQfX69D07tD1dIthU58ekmUbi90AuTOUQCA0H3W7htS3eqL5tdlK54Q2fjPrA8JCNL8+fPNz6udO7t9OaI3g0VtY7cOF++88448++yz9T7G9gIAgB2UlUvFARds/aXUiLwzOesjAoLzySefyBtvvCGHH364uM6rwULp5VAa4Na8xdtvv73Tx9leAAAQse/Qul9WL7lHQxiZHg4Qmtdee828PvTQQ8V13g0WjeUtotheAACwTZv9pabjN80vKz5eLLL6payPCAjuMqju3bub28m6zsvBoqm8RRTbCwAARMoPuLDu17m3CHEDaVmxYoV58eEyKG8Hi+byFlFsLwAAwdv7LKkpb21+mXvnfpHqzVkfERCEBQsWyG677SYHHHCA+MDbwSKfvEUU2wsAQLB2aSNlew8wvyzfsl7kvUeyPiLAe9XV1fK3v/3NZCt8KXH2erDIJ28RxfYCABCqsv223h1K0WkBpNtd4QvvB4t88xZRbC8AAMHpfBKdFkCK5nvSXRHUYFFI3iKK7QUAICh0WgCp+cSj7orgBotC8xZRbC8AAMGg0wJIxWsedVcEOVgUmreIYnsBAAgCnRZAKuZ71F0R7GBRTN4iiu0FAMB3dFoAyVrhWXdFsINFsXmLKLYXAACv0WkBJGqBZ90VQQ8WpeQtotheAAC8RKcFkJhqD7srJPTBopS8RRTbCwCAj+i0AJKxxMPuiqhgB4tS8xZRbC8AAF6h0wJIxHwPuyuigh0s4shbRLG9AAB4g04LIHafeNpdERX0YBFX3iKK7QUAwAt0WgCxes3T7oqo4AeLuPIWUWwvAADOo9MCiNV8T7srohgsYs5bRLG9AAC4jE4LIB4rPO6uiGKwSCBvEcX2AgDgLDotgFgs8Li7IorBIsG8RRTbCwCAc+i0AEpW7Xl3RRSDRcJ5iyi2FwAA19BpAZRmiefdFVEMFinlLaLYXgAAnEGnBVCS+Z53V0QxWKSYt4hiewEAcAKdFkDRPgmguyKKwSKDvEUU2wsAgPXotACK8loA3RVRDBYZ5S2i2F4AAKxGpwVQlPkBdFdEMVhknLeIYnsBALAVnRZAYVYE0l0RxWBhQd4iiu0FAMBKdFoABVkQSHdFFIOFRXmLKLYXAACr0GkB5K06oO6KKAYLy/IWUWwvAAA2odMCyM+SgLorohgsLM1bRLG9AABYgU4LIC/zA+quiGKwsDhvEcX2AgCQOTotgGZ9Elh3RRSDhQN5iyi2FwCATNFpATTptcC6K6IYLBzJW0SxvQAAZIZOC6BJ8wPrrohisHAsbxHF9gIAkAU6LYCGrQiwuyKKwcLBvEUU2wsAQOrotAAatCDA7oooBguH8xZRbC8AAKmh0wLYSXWg3RVRDBaO5y2i2F4AANJCpwVQ35JAuyuiGCw8yVtEsb0AACSOTgugnvmBdldEMVh4lLeIYnsBAEgUnRZAnZC7K6IYLDzMW0SxvQAAJIZOC0BC766IYrDwNG8RxfYCAJAIOi0ACb27IorBwvO8RRTbCwBA3Oi0QOhC766IYrAIIG8RxfYCABArOi0QuNC7K6IYLALKW0SxvQAAxIJOCwSM7or6GCwCy1tEsb0AAMSBTguEiu6K+hgsAs1bRLG9AACUhE4LBIruivoYLALOW0SxvQAAFI1OCwSI7oqdMVgkzIW8RRTbCwBAUei0QGDortgZg0UKXMhbRLG9AAAUjE4LBIbuip0xWKTApbxFFNsLAEAh6LRAKOiuaBiDRUpcyltEsb0AAOSNTgsEtK2gu2JnDBYpci1vEcX2AgDQLDotEAB9cvXVV1+lu6IBDBYpcy1vEcX2AgDQHDot4Ls333yT7opGMFikzNW8RRTbCwBAo+i0gOcWLFhAd0UjGCwy4GreIortBQCgQXRawGN0VzSNwSIjLuctotheAAB2QqcFPKXZCkV3RcMYLDLkct4iiu0FAKAeOi3g8WVQdFc0jsEiQz7kLaLYXgAAatFpAd/QXdE8BouM+ZC3iGJ7AQAw6LSAZ+iuaB6DhQV8yVtEsb0AgMDRaQGP0F2RHwYLS/iSt4hiewEAYaPTAr6guyI/DBaW8C1vEcX2AgACRacFPEF3RX4YLCziW94iiu0FAASITgt4gO6K/DFYWMbHvEUU2wsACAydFnAc3RX5Y7CwkI95iyi2FwAQEDot4Di6K/LHYGEhn/MWzW0v9P7QAAC/0GkBV9FdURgGC0v5nLdoanuhwwXbCwDwDJ0WcBTdFYVhsLCY73mLKLYXAOAxOi3gILorCsdgYTnf8xZRbC8AwF90WsA1dFcUjsHCcqHkLaLYXgCAh+i0gGPorigcg4UDQslbRLG9AADP0GkBh9BdURwGC0eElLeIYnsBAB6h0wKOoLuiOAwWDgkpbxHF9gIAPEGnBRxBd0VxGCwcEmLeIortBQC4j04L2I7uiuIxWDgmxLxFFNsLAHAcnRawHN0VxWOwcFCoeYsothcA4Cg6LWAxuitKw2DhqFDzFlFsLwDATXRawFZ0V5SGwcJRoectotheAIBj6LSApeiuKA2DhcNCz1tEsb0AAIfQaQEL0V1ROgYLx5G3qI/tBQA4gk4LWIbuitIxWHiAvEV9bC8AwAF0WsAydFeUjsHCA+QtGsb2AgDsRqcFbEF3RTwYLDxB3qJhbC8AwGJ0WsASdFfEg8HCI+QtGsf2AgAsRKcFLEB3RXwYLDxD3qJxbC8AwD50WiBrdFfEh8HCM+Qtmsf2AgAsQqcFMkZ3RXwYLDxE3qJ5bC8AwBJ0WiBDdFfEi8HCU+Qt8sP2AgAsQKcFMkJ3RbwYLDxG3iI/bC8AIGN0WiAjdFfEi8HCY+QtCsP2AgCyQ6cF0kZ3RfwYLDxH3qIwbC8AICN0WiBldFfEj8EiAOQtCsf2AgBSRqcFUkR3RTIYLAJB3qJwbC8AIF10WiAtdFckg8EiEOQtisf2AgBSQqcFUkJ3RTIYLAJC3qJ4bC8AIAV0WiAFdFckh8EiMOQtSsP2AgASRqcFEkZ3RXIYLAJE3qI0bC8AIEF0WiBhdFckh8EiQOQt4sH2AgCSQacFkkJ3RbIYLAJF3iIebC8AIAF0WiAhdFcki8EiYOQt4sP2AgBiRKcFEkB3RfIYLAJH3iI+bC8AID50WiBudFckj8EicOQt4sf2AgBiQKcFYkZ3RfIYLEDeIgFsLwCgRHRaIEZ0V6SDwQIGeYtksL0AgBLQaYGY0F2RDgYL1CFvkQy2FwBQJDotEBO6K9LBYIE65C2SxfYCAApHpwVKRXdFehgsUA95i2SxvQCAAtFpgRLRXZEeBgvshLxF8theAECe6LRACeiuSBeDBRpE3iJ5bC8AID90WqBYdFeki8ECDSJvkR62FwDQDDotUCS6K9Jl7WAxd+5c6du3r3Tt2tX8cDtjxox6H3943ibp1auXdOzY0Xxcr59DvMhbpMeH7cW1115rzsXoy8EHH5z1YQGI2LBhg1x22WVy1FFHyXXXXWe+z770kgN3WqLTAkWguyJ95Tb/x6D/Idx2220Nf/zTnHmG98Ybb0z92EJC3iJdrm8vvvzlL8vy5cvrXvTvAMAe+uTFnDlz5NZbb5URI0aYx/dTTz1V3n//fbEenRYoEN0V6bN2sDjttNPMsylnnHFGgx8ffGKlXHPNNeYBEckib5Eul7cXLVq0kL322qvuZY899sj6kABss2nTJvM4ftNNN8kxxxxjNv5XXnmluVPO2LFjxXp0WqBAdFekz9rBAvYgb5ENF7cXGpLTyxf3228/Offcc+Xdd9/N+pAAbLNlyxbzBEWrVq3qvb9169bObBfptEC+6K7IBoMF8kLeIhsubS+OPvpoue+++2T27Nnm2U+9dE63XXpNN4DstWnTRo499lgZNWqU+YFLnyTSDcYLL7xgLl10Ap0WyBPdFdlgsEDeyFtkx4XthV6+eNZZZ8lhhx0mvXv3lj/+8Y+ybt06mTp1ataHBmCbSZMmSS6XkyOPPNIMGOPHj5dzzjnHbKadQKcF8kB3RXYceSSBLchbZMel7YVq166dHHTQQbJkyZKsDwXANvvvv78888wz5ry84oorzBMAn3/+ubl80RV0WqA5dFdkh8ECBSFvkT0XthdKB8+lS5ea4wVgFw2z6qVRulWsqqqSfv36iTPotEAz6K7IjrWDhf5QotfH1fZT6KU3+ut3V219dnbNhhrz9sKFC83bixcvNm/b+AOWb8hbZM/G7YXeXUafCdX/Lp5//nlzRzc9Tr3MAoAddIjQHJTeWEEH/4EDB5q+mQsu2L4FsB6dFmgC3RXZsnaw+Otf/ypHHHGEeVG6stVfX/vA1iDoo3/dbN4+/fTTzdvf//73zdt33HFHpscdCvIWdrBpe/Hee++ZIUJv7Tdo0CBzK8t58+ZJp06dMjkeADtbv369XHLJJXLCCSfIww8/LF//+tfNsLHLLruIU+i0QCPorshWWU5TXA6pnt5VKj5dLtUtu0jFANafWdLLoCZPniwffPCBXHzxxWaTgezoXV1mzpwpq1atMoOG/uBAaA1AY48Xd911lwwfPtzZyxVrqo6T8tV/3vpGrxdF9vh61ocEC9x5553Svn178wSXy5Y7eo5au7GA/chb2MWm7QUAJI1OC+yI7orsMVigJOQt7GJj9gIAEkGnBXZAd0X2GCxQMvIW9mF7AcB7dFoggu4KOzBYIBb0W9iH7QUA39FpgVp0V9iBwQKxIG9hL7YXALxFpwW2obvCDgwWiA15C3uxvQDgJTotQHeFVRgsECvyFnZjewHAO3RaBI/uCnswWCB25C3sxvYCgFfa7C81Hb9pflnx8WKR1S9lfUTI4DIoLWetrKzM+lCCx2CB2JG3cAPbCwC+oNMiXHRX2IXBAokgb+EGthcAvECnRbDorrALgwUSQ97CHWwvADiNTosg0V1hHwYLJIq8hTvYXgBwGZ0W4aG7wj4MFkgUeQv3sL0A4CQ6LYJDd4V9GCyQOPIW7mF7AcA5dFoEhe4KOzk1WORyOfnwoxp5Z5WY1/o23EDeIozthTlHP/zQDJH6mnMUsI+el6tXr5a1a9ea116dp3RaBIPuCjs5MVisW7dOxowZIz169JC9Llwp+14m5rW+re/Xj8N+5C383V5Ez9FOnTqZ/5/1NecoYI/oeao/jOmv9bVX5ymdFsGgu8JO1g8WVVVV0q1bN7nyyitNOGfq1KkyZ84c81rf1vfrx/XzYDfyFn5uLzhHAfuFdJ7SaeE/uisslrPY7Nmzcy1atMidfvrpueXLlzf4Ofp+/bh+nn4+7PfWW2/lfvGLX+SefvrprA8FRfrnP/+ZGzt2bO68887jHAUsF9z30s8+ylXf3zqX+73kqh9om8tt2ZT1ESFmjz/+eO43v/lNbsuWLTmfv89ee+215rVLyvR/xEK6ktVnT/TymRkzZkiLFi0a/dwtW7ZI//79TTB42bJl0q5du1SPFYV75plnTN5iyJAh5rIZuEevzdZzVLMzM2fO5BwFLBTq99Lc8+dJWW14+5sPiHQblPUhISZ6Ge7o0aPlsMMOk969e4uvli9fLnfddZcMHz7cXDHgCmsvhZowYYK5N/G4ceOafCBU+nG9LEM/f+LEiakdI4pH3sJ9kydPlk8//VTGjx/POQpYKtTvpXRa+IvuCrtZOVjoEmXs2LEyYMAA2WuvvfL6Gp3m9Pr922+/3a87XHiKvIXbOEcB+wV9ntJp4S26K+zW9NMXGV5isXjxYhk1alRBX6cPnhpE6/LLLlK+m5UzExpYaW56e5Nc8esrZNddd836cJCnmk9qZOXilZyjgMfn6Zo1a6Rjx47idKfFa6O2d1oc8u9ZHxVi6q7o1atX1ocClwaL2ktj2rdvX9DX1X7+yrUrEzkuJOjzbS9ww9qtrzhHAX/P0w0bNrg7WNR2Wrw2qq7ToqLHVSJlZVkfFUpAd4X9Wtja1Ky0vKcQtZ/fuX1nng11iK7bN2/ebC6Hal3ZWsrL+P/OdjVSIytlJeco4PF52qZNG/Gh06J89Z+3d1rs8fWsjwoloLvCflYOFvoMif6Ho8Hes846K++vm/7gg9J9v/1k0TVLzLX7cIduqe68805TqjZ48GCTwYDdw2CP+3sUfo5On27O7UXXLOIcBVI4Tw+afJA8+OCDRZ2nHTp0EC86LVb/ua7ToozBwvnuipNOOinrQ0ETrPzpTX/gGDFihHlw0/+I8r0tl4aARyxbJmWjR+vF+4kfJ+LdUmlg8J133jG3OoTdSjlHR44cyVABpJBf01t6H3jggea8C/Y83fssqSlvbX6Ze+d+kerNWR8RijR//nzZbbfd5IADDsj6UODaYKGGDh1qVl3Dhg0z99Zuin78omEXSmUuJ0N1oLjySqk57jiRxYtTO16UTm8/q50I+s3w7bffzvpwEPc5etFF5vO1uwRAcnQ40NvGPvfcc2ZAKOQ8HXbRML/O013aSNneA8wvy7esF3nvkayPCEUOypqv0GxFRUVF1ocDFwcLLebRu1JUVVWZwh59oGyIvr9//+9J1RNVMvWi46XttmdYyufNkxqter/5ZrYXDqHfwh2FnaP9zedNmzbN6dItwPYfvp566inTWaF0mO/Tp0/e5+n3+n1PZs+eLZPun+TVeUqnhfvornCHtc3btfTBcNCgQeY/KL1URm+Dp3es0HCZ/vCpK9vKyhqZNq1GTjnlS1Lxl7FSPfiHUvHWW3W/R80xx0j5ffeJdO+e6d8F+SFv4Zb8ztFKM1Rwi0AgGToYzJw5U1atWmWeoNGX6DO7zZ2n0x+aLrkWOakZWCMXDrxQxvcbL97I1Uj1w92kYvN7kpNyKev/D5HKrlkfFQrwwAMPyPr1600LdSiWO9q8bf1godatW2daQLWwR/stamm4bOTIH8h5590v7du/ZN5XU9NXyjffL7mr/1Pkt7/Vv+DW97dsKeXXXy9y2WUirNGsp5dCTZo0yVwapS9w+RwdaS6batu2babHCPi6pZg7d6657EmfjNGtRGNleE2dp2cOOVP+Z9P/yOYWWzMIE/tPlPMOP0+88bdr6m49Kz1vpNPCse6K0aNHmyemjj76aAnFcgaL5OmhamGP3ltbb4Ond6zYGi77h9TUHC7l5bW31BstIpeLPPusVJ9/PtsLRz3zzDMmb6HX+urlUXD5HAWQ9paiqfN04cKFJoehl0sdcsgh5jyduGCiDJ0x1HxO6xat5eXhL0uPTj3ECxuWijy6NfRbvXt3qei7iE4LR8ybN0/mzJkjP/7xj4O6zexyRwcLp64x0Qc+vRXtPvvsY15v/4HlS1JePrnu83I5fSbiRb1gXypefVVyP/qR5MheOIe8hXsaP0cBJJml0Ftw5htq1fNSh369FCo6/A85fIhc0HNrHmHTlk0ycOpA2fj5RvHCtk4LVddpASfQXeEWpwaLpn1320ChD5pbpLpa79m9RqSyUspuuUXKnnlGqvfbz3y8/NNPuXOUAzRbodcC6zc9vU5fC/QAIGTROz7pky86VDR26VMxfvfd30mPjlu3FAs/XCiX/vFS8YXptNhGOy3gTnfF4fqEMJzg0WChA8V1UlNzrPl1RYVeHnW+Pnxs/SDbCyfRbwEApW8p8lW5S6VMP3u6uRRK3TP/Hpm0YJJ4gU4L59Bd4R6vBguRXaS8/AGpqWlv3iovf1REbtn+YbYXTqLfAkDIkt5S7EhzFXf0uaPu7R/M+oEsWrVInEenhVPornCTZ4NFE3mLKLYXziFvASA0aW0pGuJr3oJOC3fQXeEmDweLJvIWUWwvnELeAkBI0t5SBJO36HySVLf6ovll2YonRDb+M+sjQhOhbb0bUufOnbM+FBTA08GimbxFFNsLZ5C3AOC7LLcUQeQtysql4oCtW4syqRF5Z/sVDrCru+KNN94gtO0gbweLZvMWUWwvnEHeAoCvbNhSBJG32HdrV4eqXnKPXjOd6eFgZ5qtUJqvgFs8HizyzFtEsb1wAnkLAD6xaUsRRN6CTgvr0V3hLs8HizzzFlFsL6xH3gKAL2zcUoSQt6DTwl50V7gtgMGigLxFFNsLq5G3AOAy27cU3uct6LSwFt0VbgtisCgobxHF9sJq5C0AuMiVLYXXeQs6LaxEd4X7AhksishbRLG9sBZ5CwCucG1L4Xvegk4L+9Bd4b6ABosi8hZRbC+sRN4CgAtc3VJ4nbeg08I6dFe4L7DBosi8RRTbC+uQtwBgKx+2FN7mLei0sArdFX4IbrAoOm8RxfbCOuQtANjGpy2Ft3kLOi2sQXeFHwIcLErMW0SxvbAKeQsANvBxS+Ft3oJOC2vQXeGHQAeLEvMWUWwvrEHeAkDWfN5S+Jq3oNMie3RX+CPgwSKGvEUU2wsrkLcAkIVQthRe5i3otMgc3RX+CHqwiCVvEcX2wgrkLQCkKbQthXd5CzotMkV3hV8CHyxizFtEsb3IHHkLAEkLdUvhY96CTovs0F3hFwaLOPMWUWwvMkXeAkCSQt9SeJe3oNMiM3RX+IXBIom8RRTbi8yQtwAQN7YUnuYt6LTIBN0V/mGwSCpvEcX2IjPkLQDEhS2F53kLOi1SR3eFfxgsks5bRLG9yAR5CwClYEsRSN6CTovU0V3hHwaLNPIWUWwvUkfeAkCx2FKElbeg0yI9dFf4icEizbxFFNuLVJG3AFAIthSB5i3otEgN3RV+YrBIO28RxfYiVeQtAOSDLUXAeQs6LVJBd4W/GCyyyltEsb1IDXkLAI1hSxE/F/MWdFokj+4KfzFYZJm3iGJ7kQryFgAawpYiOc7lLei0SBzdFf5isLAhbxHF9iJx5C0A1GJLkTzn8hZ0WiSK7gq/MVjYkreIYnuROPIWANhSpMe5vAWdFomhu8JvDBa25S2i2F4kirwFECa2FNlwKm9Bp0Vi6K7wG4OFjXmLKLYXiSFvAYSHLUW2XMpb0GkRP7or/MdgYXPeIortRSLIWwBhYEthB6fyFnRaxI7uCv8xWNiet4hie5EI8haA39hS2MWZvAWdFrGiuyIMDBau5C2i2F7EjrwF4B+2FPZyJW9Bp0V86K4IA4OFS3mLKLYXsSJvAfiFLYX9nMhb0GkRG7orwsBg4WLeIortRWzIWwDuY0vhDifyFnRaxILuinAwWLiat4hiexEb8haAu9hSuMeJvAWdFiWjuyIcDBau5y2i2F7EgrwF4Ba2FG6zPm9Bp0XJ6K4IB4OFD3mLKLYXJSNvAbiDLYUfbM9b0GlRPLorwsJg4VPeIortRUnIWwB2Y0vhF+vzFnRaFI3uirAwWPiWt4hie1ES8haAndhS+MnqvAWdFkWhuyI8DBa+5i2i2F4UjbwFYA+2FP6zOW9Bp0Xh6K4ID4OFz3mLKLYXRSFvAdiBLUU4rM1b0GlRMLorwsNgEULeIortRcHIWwDZYUsRHmvzFnRaFITuijAxWISSt4hie1Ew8hZA+thShMvavAWdFnmjuyJMDBah5S2i2F4UhLwFkA62FLA2b0GnRd7orggTg0WIeYsothd5I28BJI8tBWzPW9Bp0Ty6K8LFYBFy3iKK7UVeyFsAyWBLAWfyFnRaNIvuinAxWISet4hie5EX8hZAvNhSwKm8BZ0WTaK7ImwMFolzJG8RxfaiWeQtgNKxpYCreQs6LRpHd0XYGCxS4UjeIortRZPIWwClYUsBp/MWdFo0iu6KsDFYpMSpvEUU24tGkbcACseWAl7kLei0aBDdFWCwSI1jeYsotheNIm8B5I8tBbzKW9BpsRO6K8BgkSoH8xZRbC8aRN4CaBpbCniZt6DTYid0V4DBInUO5i2i2F7shLwF0Di2FPA5b0GnxXZ0V0AxWGTA2bxFFNuLeshbAPWxpUAQeQs6LerQXQHFYJEJh/MWUWwv6iFvAWzFlgLB5C3otDDorkAtBovMOJ63iGJ7UYe8BULGlgIh5i3otKC7AtsxWGTK8bxFFNsLg7wFQsWWAsHmLei0oLsCdRgsMuZF3iKK7QV5CwSFLQUk9LxF4J0WdFcgisEic57kLaLYXpC3QBDYUsAWmectAu60oLsCUQwWVvAobxEV+PaCvAV8xZYCNso0bxFwpwXdFYhisLCGR3mLqIC3F+Qt4CO2FLBZlnmLEDst6K7AjhgsLOJd3iIq0O0FeQv4gi0FXJBp3iLATgu6K7AjBgureJi3iAp0e0HeAq5jSwGXZJa3CKzTgu4KNITBwjqe5i0C316Qt4CL2FLAVVnlLULqtKC7Ag1hsLCSp3mLgLcX5C3gGrYUcF0meYuAOi3orkBDGCws5XXeItDtBXkLuIAtBXyRSd4ikE4LuivQGAYLa3metwh0e0HeAjZjSwHfZJK3CKDTgu4KNIbBwmoB5C0C3F6Qt4Bt2FLAZ6nnLQLotKC7Ao1hsLBeAHmLwLYX5C1gE7YUCEHaeQufOy3orkBTGCwcEEzeIqDtBXkLZI0tBUKSet7C404LuivQFAYLJwSUtwhoe0HeAllhS4EQpZq38LTTgu4KNIfBwhmB5S0C2V6Qt0Ca2FIgdGnmLXzstKC7As1hsHBKYHmLALYX5C2QFrYUQMp5Cw87LeiuQHMYLBwTZN7C8+0FeQskiS0FkFHewrNOC7orkA8GC+cEmrfwfHtB3gJJYEsBZJy38KjTgu4K5IPBwkkB5y083l6Qt0Bc2FIAluQtPOq0oLsC+WCwcFbAeQtPtxfkLRAHthSAXXkLHzot6K5AvhgsHBZ83sLD7QV5CxSLLQVgad7Cg04LuiuQLwYLp5G38HF7Qd4ChWJLAVict3C804LuChSCwcJ55C183F6Qt0A+2FIAbuQtXO60oLsChWCw8AJ5C9+2F+Qt0By2FIBDeQuHOy3orkAhGCw8Qd7Cv+0FeQs0hC0F4GDewtFOC7orUCgGC2+Qt/Bxe0HeAlFsKQCH8xYOdlrQXYFCMVh4hbyFj9sL8hZgSwF4kLdwsNOC7goUisHCO+QtfNtekLcIG1sKwJ+8hUudFnRXoBgMFh4ib+Hf9oK8RXjYUgAe5i0c6rSguwLFYLDwEnkLH7cX5C3CwZYC8DRv4UinBd0VKBaDhbfIW/i4vSBv4Te2FID/eQsXOi3orkCxGCy8Rt7Ct+0FeQt/saUAAslbONBpQXcFisVg4TnyFv5tL8hb+IUtBRBY3sLyTgu6K1AKBgvvkbfwcXtB3sIPbCmAQPMWFnda0F2BUjBYBIG8hY/bC/IW7mJLAQSet7C404LuCpSCwSIY5C18216Qt3ATWwrAXXHmLWzstKC7AqVisAgIeQv/thfkLdzBlgJwX6x5Cws7LeiuQKkYLIJC3sLH7QV5C/uxpQD8EVvewrJOC7orEAcGi+CQt/Bxe0Hewk5sKQA/xZW3sKnTgu4KxIHBIkjkLXzbXpC3sA9bCsBvseQtLOq0oLsCcWCwCBR5C/+2F+Qt7MCWAghDLHkLSzot6K5AXBgsgkXewsftBXmLbLGlAMISS97Cgk4LuisQFwaLoJG38HF7Qd4ifWwpgHCVnLewoNOC7grEhcEieOQtfNtekLdIF1sKAKXmLbLstKC7AnFisAB5Cw+3F+QtkseWAkBseYsMOy3orkCcGCxA3sLT7QV5i+SwpQAQa94io04LuisQNwYLbEPewsftBXmLeLGlAJBU3iKLTgu6KxA3BgtEkLfwbXtB3iI+bCkAJJq3yKDTgu4KxI3BAvWQt/Bve0HeojRsKQCkkrdIudOC7gokgcECOyBv4eP2grxFcdhSAEg1b5FipwXdFUgCgwUaQN7Cx+0FeYv8saUAkEneIsVOC7orkAQGCzSCvIVv24uk8xZjx46Vww47TL7whS+Yl2OPPVYef/xxcQ1bCgBZ5i2a6rSYO3eu9O3bV7p27Woey2fMmFHv47lcTq655hqTm2jdurWceuqpJqC9I7orkBQGCzSKvIV/24sk8xZf/OIX5de//rW8/PLL8te//lW+9a1vSb9+/eT1118XF7ClAGBF3qKJTgvNRegwcNtttzX4pTfddJP89re/lTvuuENefPFF00/Ru3dv2by5fi8G3RVICoMFmkDewsftRVJ5C30W7bvf/a4ceOCBctBBB8n1119vBpl58+aJ7dhSALAmb9FEp8Vpp50m1113nZxxxhk7fZluK2655Rb52c9+Zp7U0Q3yxIkT5Z///Ge9zQbdFUgSgwWaQd7Cx+1F0nkL/cY1ZcoU8+yaXhJlK7YUAGzMWxTTaaFPFOnlTXr5U622bdvK0UcfLS+88ELd++iuQJIYLJAH8ha+bS+Sylvos2C6pWjZsqVcfPHF8vDDD8shhxwiNmJLAcDavEURnRY6VJgv3aGTQt+u/ZiiuwJJYrBAXshb+Le9SCJvoXcY0Wt39dreESNGyNChQ2XhwoViE7YUAKzPWyTUaUF3BZLGYIE8kbfwcXsRd95i1113NWHAr371q3LDDTeYb15jxowRW7ClAOBM3qLATovax7KVK1fWe7++XfsxuiuQNAYLFIC8hY/biyTzFnqJ1ac6BGWMLQUA5/IWBXZa6OO4DhB/+tOf6t730UcfmQ1ybdaN7gokjcECBSJv4dv2Iq68xU9/+lNzj3W9tEqfFdO3dRNy7rnnSpbYUgBwNW+xY6eFPvmjl5vqi9JNs/763XffNY/hl112mblr1COPPGIeh4cMGWI6L/r37093BVLBYIGCkbfwb3sRR97igw8+MN/E9NmwU045RV566SWpqqqSb3/725IFthQAnM9b7NBp8dcXn5cjjjjCvKgrrrjC/FpL8dS///u/y6WXXirDhw+Xo446ygwis2fPllatWtFdgVS0SOePgZ95i8OlvHxtJG9xedYHFuT2QgYMkOrzz5eKt97avr148EEpv+8+TVMXlbfYe++9zduFGD9+vNhCtxQzZ86UVatWmS2FvjBQALAxbzF0xtC6vMXXun7NvH+nTot3JptOi5MOWGf6KhqjW4tf/vKX5iWqtrtCuy14LESS2FigSOQtfNxeJN1vkTS2FAB8y1sU02mxI7orkBYGC5SAvIVv2Yuk+i3SQJYCgJd5iyI6LXZEdwXSwmCBkpC38G97kUS/RZLYUgDwOm9RYqcF3RVIE4MFSkS/hY/bi7j7LZLClgJAEP0WBXZaRNFdgTQxWCAG5C183F7YnLdgSwEgqLxFgZ0WUXRXIE0MFogJeQvfthe25i3YUgAIMW+xY6dFPuiuQNoYLBAb8hb+bS9syluwpQAQdN5ih04Lqd7c7O9HdwXSxmCBGJG38HF7YUPegi0FAAk9b1HbaaGP3VvWi7z3SJO/T213hWYreAIGaWGwQMzIW/i4vcgqb8GWAkCIGstbFNJpQXcFssBggQSQt/Bte5FF3oItBYCQNZi3KKDTgu4KZIHBAokgb+Hf9iKtvAVbCgBoJG/xt9/n1WlBdwWywmCBhJC38HF7kXTegi0FADSTt/jC1tvONtVpQXcFssJggQSRt/Bxe5FE3oItBQDkmbd47Ar5uN0xTXZa0F2BrDBYIGHkLXzbXsSdt2BLAQCF5S1+tKZFo50WdFcgSwwWSBx5C/+2F7u3bt1g3iKXy8mHH35o3q+v9e3GsKUAgCLzFkufkwkbdjG/rnn7D/LhyvfqHndfeeUVuiuQGQYLpIC8hY/bi30/+6wub6Fr9zFjxkiPHj2kU6dO5lIpfa1v6/vXrVtX77dmSwEApeUtRiyrlqtniXz5xxul015fqnvcveCCC2Tp0qWyYcOGTI8XYWKwQErIW/i4vTj+pZfk448+kmOPPVauvPJKc7/0qVOnypw5c8xrfVvf361bN6mqqmJLAQBx5C2WiHz6PyI3TauQnt88o97jrj7ho4+xtY+7QJq2X6QHpJS3KCu7qS5vUVExX0Q6ZH1gyHN7IQMGSPX550vFW2+Z7UXVVVfJLeXl0us735Hx48fvtHU466yzzLW+w4YNkz59+siIESPMM2q6pdAXBgoAKEy/Fv1kwv0TpHfv3nLP+HuafdydNWuW+VwgDWwskCryFv5sL9aKyKDycvMNa+bMmY1eyqTvnzFjhvTq1csMH4MGDWJLAQBF0MtKh/y/IfKd73xHHpn5SLOPu/r4rI+5O16OCiSFwQIpI2/hy/Zi4qWXysayMhl3zz3SokXTy0/9uK7mP/vsM1bzAFCkCRMmyMaNG2X8uPF5Pe5qlk0/f+LEiakdI8LGYIEMkLdwnd7taewTT8iAgQPzDl136dLF3Enq9ttvb/JuUQCARh53x46VAQMG8LgLa5GxQEbIW7hs9erVsnjxYhk1alRBX6ffEDVcuKpLF+lYzvMaQFb2qK6Wyzdtkta33y7VXJbohA9ramTxypVFP+6uWbNGOnbsmNjxAYrBAhnnLZ6V8vIX6vIW5eUz9SNZHxqaUdu43b791kva8lX7+RtXrpQ9EzkyAPnQUcK0IHBLUmds2va62Mddvf0sgwWSxmABC/IWh0t5+dpI3uLyrA8Mzdh9993N67VrNcKdv9rPr+zcWarZWACZqamulk26sWjdWsrZWDihdU2NyMqVRT/utmnTJqEjA7ZjsIAleYvTzVtbL4/6hogcnfWBoQn6rFf37t1l+vTp5taG+dLP16/rtGiRlG3rxACQvg+WL5e77rpLhg8fbq7Dh/32zOWke48eRT/udujApcZIHk8Zwpq8harNW4isyfqg0AQdCrSTQr9h6f3S86Ft2w899JApxWOoAID0HndHjhzJ4y5SwWABK9Bv4Z6hQ4dKZWWlKWHasmVLk5+rH9fP22WXXWTz5s3y5ptvpnacABDq4+5FFw0znz9kyJDUjhFhY7CAJei3cE27du3MnUa0l6J///7mmbGG6Pv140888YT8/ve/l27duskf/vAHU6qnQwYAIInH3e9JVdXjMm3aaPN1QBrIWMAi5C1co62us2bNMs2ue++9t7lfut7aUO9CooFBXdnrGl6fMXvsscdM+7beS/2VV14x3xiXLl0qffv2lQMPPDDrvwoAePS4O10qK3Py2GM5OeWU0SJyjt42I+tDRwAYLGAZ+i1c/Ca3bNky0+yqJUz6bFotDQzefPPNZn3ftm1b8z69zvfII4+U/fffXx599FGzvejZs6f5fVq1apXh3wQAfHnc/bUMHjxOOnRYLCILJZf7oZSVjcv0mBGGshxVjLDO51JTc6Lpt1A1NX3pt3CEPpwsXLhQ7r77bhPSPuSQQ5oMDEa3Fy1btmR7AaREL5XhrlB+0MdRLb/Tngq9paze/Wnr4+7fpabmq1JevnHbZ04SkcEZHy18P0fJWMBC5C1cpd/M9JuaruS3f3Nr+vN1e6F3LNlzzz3JXgBAgfRxVG8Bvs8++5jX2x93D5by8jvrPq+m5gdm2ACSxGABy/MWW229He2LmR4RkqOXSZ177rlmY6EbD13tc+coACjVYMnlLjS/0s1FdfUAEandYADxY7CAxei3CAnbCwCIX1nZrVJdfYj5dUXF1rwFkBQGC1iNfovwsL0AgDhVSkXFdKmp2XpXqLKy8SKy/YoAIE4MFrAceYsQsb0AgDiRt0A6GCzgAPIWoWJ7AQBxIW+B5DFYwBHkLULF9gIA4kHeAkljsIAzyFuEje0FAJSKvAWSxWABh5C3CB3bCwAoFXkLJIfBAo4hbwG2FwBQGvIWSAaDBRxE3gJsLwCgFOQtkAQGCziJvAVqsb0AgGKQt0D8GCzgKPIW2I7tBQAUg7wF4sVgAYeRt0B9bC8AoFDkLRAfBgs4jrwF6mN7AQCFIW+BuDBYwHnkLdAQthcAkC/yFogHgwU8QN4CDWN7AQD5Im+B0jFYwBPkLdA4thcAkA/yFigNgwU8Qt4CjWN7AQDNI2+BUjBYwCvkLdActhcA0BTyFigegwU8Q94CzWN7AQBNIW+B4jBYwEPkLZAfthcA0BjyFigcgwU8Rd4C+WF7AQANI2+BQjFYwFvkLVAIthcAsCPyFigMgwU8Rt4ChWF7AQA7Im+B/DFYwHPkLVA4thcAEEXeAvlhsEAAyFugcGwvAGA78hbIB4MFgkDeAsViewEAirwFmsdggUCQt0Dx2F4AgCJvgaYxWCAg5C1QGrYXAEDeAo1jsEBgyFugNGwvAISOvAUaw2CB4JC3QBzYXgAIF3kLNIzBAgEib4F4sL0AEC7yFtgZgwUCRd4C8WF7ASBM5C1QH4MFAkbeAvFhewEgROQtEMVggaCRt0Dc2F4ACAt5C2zHYIHAkbdA/NheAAgLeQtsxWABkLdAQtheAAgHeQswWADbkLdAMtheAAgFeQswWADbkLdAktheAPAfeYvQMVgAdchbIFlsLwD4j7xFyBgsgHrIWyB5bC8A+I28RagYLICdkLdA8theAAgrb3Fp1oeEFDBYAA0gb4G0sL0AEEbe4h4RmZT1QSFhDBZAg8hbID1sLwCEk7dYlOkRIVkMFkCjyFsgXWwvAPidt9gk1dUDyVt4jMECaBJ5C6SL7QUA35C3CAeDBdAM8hbIAtsLAP4gbxEKBgugWeQtkA22FwD8Qd4iBAwWQF7IWyA7bC8A+IG8he8YLIC8kbdAdtheAPABeQu/MVgABSBvgayxvQDgNvIWPmOwAApC3gLZY3sBwG3kLXzFYAEUjLwF7MD2AoC7yFv4iMECKAp5C9iB7QUAV5G38A+DBVAk8hawCdsLAO4hb+EbBgugaOQtYBe2FwDcQ97CJwwWQEnIW8A+bC8AuIW8hS8YLICSkbeAfdheAHAJeQs/MFgAMSBvAVuxvQDgBvIWPmCwAGJB3gL2YnsBwA3kLVzHYAHEhrwF7Mb2AoD9yFu4jMECiBV5C9iN7QUA25G3cBeDBRAz8hZwAdsLAPYib+EqBgsgduQt4Aa2FwDsRd7CRQwWQCLIW8AdbC8A2Im8hWsYLIDEkLeAO9heALAReQu3MFgACSJvAdewvQBgF/IWLmGwABJF3gLuYXsBwC7kLVzBYAEkjrwF3MT2AoA9yFu4gMECSAV5C7iJ7QUAW5C3sB+DBZAS8hZwGdsLANkjb2E7BgsgNeQt4Da2FwCyR97CZgwWQKrIW8B9bC8AZIu8ha0YLIDUkbeA+9heAMgSeQs7MVgAGSBvAV+wvQCQDfIWNmKwADJB3gL+YHsBIBvkLWzDYAFkhrwF/ML2AkD6yFvYhMECyBR5C/iF7QWAtJG3sAeDBZAx8hbwEdsLAOkhb2ELBgsgc+Qt4Ce2FwDSQ97CBgwWgBXIW8BfbC8ApIO8RdYYLABrkLeAv9heAEgDeYtsMVgAFiFvAd+xvQCQLPIWWWKwAKxC3gL+Y3sBIFnkLbLCYAFYh7wFwsD2AkByyFtkgcECsBJ5C4SB7QWApJC3SB+DBWAp8hYICdsLAPEjb5E2BgvAWuQtEBa2FwDiR94iTQwWgNXIWyA8bC8AxIu8RVoYLADrkbdAeNheAIgTeYt0MFgADiBvgVCxvQAQD/IWaWCwAJxA3gLhYnsBIB7kLZLGYAE4g7wFwsb2AkDpyFskicECcAp5C4SN7QWAUpG3SA6DBeAY8hYA2wsApSBvkRQGC8A55C0AxfYCQPHIWySBwQJwEnkLoBbbCwDFIW8RNwYLwFnkLYBabC8AFIO8RbwYLACHkbcA6mN7AaAw5C3ixGABOI28BbAjthcACkPeIi4MFoDzyFsADWF7ASB/5C3iwGABeIG8BdAQthcA8kXeonQMFoAnyFsAjWN7AaB55C1KxWABeIO8BdAUthcAmkfeohQMFoBXyFsAzWF7AaBp5C2KxWABeIe8BdActhcAmkLeojgMFoCHyFsA+WF7AaBh5C2KwWABeIm8BZAvthcAGkbeolAMFoC3yFsAhWB7AWBn5C0KwWABeI28BVAIthcAdkTeIn8MFoDnyFsAhWN7AWA78hb5YrAAvEfeAigG2wsA25G3yAeDBRAE8hZAsdheANiKvEVzGCyAYCSbt5g7d675weuII46Qa6+9Vh5//PHYfm8gaz5sL2644QY56qijpE2bNnLooYfK/fffL0uWLMn6sACnJJ23qK6ulp///Ody9NFHy3XXXSfHHnusjBo1SnI5Ny5hZrAAApJk3uKTTz6Rww8/XH71q1/F8vsBNnJ5e/HMM8/IJZdcIvPmzZMpU6ZITU2NnHPOOebcBWBH3uLGG2+UsWPHyvXXX2/O1//8z/+Um266SW699VZxAYMFEJTk8hannXaaeXZFXwM+c3V7MXv2bDn//PPly1/+snnp37+/vP/++/Lyyy9nfWiAY5LLWzz//PPSr18/OfXUU6V9+/bSp08f6dWrl/zlL38RFzBYAMEhbwGEvr1QtYNQhw4dsj4UwEHJ5C2+8Y1vyJ/+9CdZunSpefv111+X5557zpkn7VpkfQAAsstblJXdVJe3qKiYrz9iZH1ggJPbi/33318effRRs73o2bOn9O7dW1q1aiW20sugdIOhmYuvfOUrWR8O4HDeYp7JWtTmLcrKxpf0e/7kJz+Rjz76SE444QTz+KLZCr0sSp/EcAGDBRB03uJZKS9/oS5vUV4+Uz+S9aEBzm4vXnnlFamqqjLPNuom48ADDxQbXX311fLBBx+YADeAUvMWX5Xy8o3b8hYnich5Rf+OU6dOld///vdy2223yauvvio9evQwN0Tp2rWrDB06VGzHpVBAsOi3AELMXvzbv/2bzJkzx+Qt9IcVAPbkLa666iqztdAMVOfOnWXgwIFy+eWXm7u6uYDBAggaeQsglOyFXlKhQ8XDDz8s06ZNM8FQAHblLTZu3Cjl5fV/PK+oqDCXL7qAwQIIXjz9Fh9//LHMnz9fXnvtNfP2P/7xD/P2u+++G/sRA7azcXuht66cPHmyOZbdd99dNmzYYC6H2rRpU2bHBPgirn6Lvn37mkzFk08+KWvXrjWdUKNHj5YzzjhDXFCWc6VxA0CCPpeamhNN3kLV1PQtOG/x9NNPy8knn7zT+/Wa0Pvuuy/WowVcot9ma7MXLVu2zCx7ocNOQ+69915zWRSAUv29Lm+x1cSC8xY68GtB3oMPPigrV66Uf/mXf5HBgwfLNddcI7vuuqvYjsECwDYa4D5cysvXbnt7tIhcXvDvsnz5crnrrrtk+PDh0qVLl9iPEnDV+vXrzZ2jNNid9Z2jOE+BpEyuGyZqalpLebn2xPQI5hzlUigA25C3AELMXgCwv9/CFQwWAGLPWwBwJ3sBwM68hYsYLAA00G9xrPl1bb+FCFdMAnFiewGE0G9Rad7a2m8xSULAYAFgB/RbAGlgewH47OBY+y1cwWABoAHkLYC0sL0AfDU4uLwFgwWARpC3ANLC9gLwU1lgeQsGCwCNIm8BpIvtBeCbyqDyFgwWAJpA3gJIG9sLwDfh5C0YLAA0g7wFkAW2F4BPBgeRt2CwAJAH8hZAFtheAP4oCyBvwWABIC/kLYDssL0AfFDpfd6CwQJAnshbAFliewH44GCv8xYMFgAKQN4CyBrbC8B1g73NWzBYACgQeQsga2wvALeVeZq3YLAAEFveIpfLyerVq2Xt2rXmtb4NwK7tBecpYHfeIufwOVqWc+loAVhEB4rDpbx8raxbJzJhQn8ZO3aRLF68uO4zunfvLiNGjJChQ4dKu3btMj1awHfr16+XRx99VJYuXSo9e/aU3r17S6tWreo+vm7dOpkwYYKMHTuW8xSwxmQROc/8as2aVjJp0uUyduxDzp6jDBYASvBHqao6XQYNKpeNG8tkwIABMmDAQGnfvr15pmX69OnmpbKyUqZOnWp+0AGQHP2W/sorr0hVVZW0bNnSbDIOPPBA8/agQYNk48aN287TAZyngCVyuX+VJ564J/K9dKCz5yiDBYCi6Q8rffqcLr1795Jx4+6Rvfbaa6fPWbFihQwbNsx87qxZs6x+QAR83F7ot/nrr7/enHvjxo3jPAUsU1U1U/r0OXPbOer291IGCwBF0csqunXrJscff7zMmDFDWrRo0ejnbtmyRfr37y/PPvusLFu2zPpVLuAD/fY+d+5cOe200+Tkk0824W7OU8DW76XHyYwZ7p+jhLcBFEWv1dbLKvQZ0KYeCJV+/O677zafP3HixNSOEQj9zlHz58+Xzz//XMaPH895Clj9vXS8F+coGwsABdOHjR49epiA6JQpU/L+urPPPlsWLFggixYtMj/0AEgO5ylgt5yH52jToxEANEBvf6d3rBg1alRBX6dhNA2erVrVRTp2ZGEKJOnDD2tk8eKVnKeAp+fomjVrpGPHjmITBgsABfv444/Na71jRSFqP3/jxpWy556JHBqAbTZt2vqa8xTw8xzdsGEDgwUA9+2+++7mtd4GrxC1n19Z2Vmqq3kmFEhS69Y1IrKS8xTw9Bxt06aN2IaMBYCC+XhdKOAbzlPAbjkPz1GeigBQMH0g0xZQLezRe2vnY/ny5fLQQw/JyJEjrXsgBHzEeQrYrczDc5SNBYCi0GMB2I/zFLDbOs/OUTYWAIqiD2h6VwptAdUHOn0WpSH6fv24ft60adOsfCAEfMV5CtitnWfnKBsLACXRB7lBgwaZwp4zzzzT3AZP71ih4TJd7+rKtrKy0jwQ9urVK+vDBYLEeQrYrcqTc5TBAkAsq1xtAb399ttNv0Wt7t27m+tAhw4dKm3bts30GIHQcZ4CdlvnwTnKYAEgNvpwooU9em9tvQ1ehw4drAyXASHjPAXslnP4HGWwAAAAAFAywtsAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAASsZgAQAAAKBkDBYAAAAApFT/H2sKyMSIbS40AAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 800x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Visualization: different colors per path\n",
    "POS_LIST = [\n",
    "    (40, 10), (70, 10), (40, 30), (10, 70), (40, 50),\n",
    "    (70, 70), (100, 70), (100, 10), (70, 50), (85, 30), (10, 50)\n",
    "]\n",
    "pos = {i+1: POS_LIST[i] for i in range(len(POS_LIST))}\n",
    "\n",
    "fig, ax = plt.subplots(figsize=(8, 6))\n",
    "# Draw base network\n",
    "for u, v in base_arcs:\n",
    "    x1, y1 = pos[u]\n",
    "    x2, y2 = pos[v]\n",
    "    ax.plot([x1, x2], [y1, y2], color='grey', linewidth=1)\n",
    "\n",
    "# Highlight flow arcs\n",
    "colors = ['red', 'orange', 'yellow', 'green']  # one color per path\n",
    "for idx, pth in enumerate(paths):\n",
    "    color = colors[idx] if idx < len(colors) else 'black'\n",
    "    for u, v in zip(pth, pth[1:]):\n",
    "        x1, y1 = pos[u]\n",
    "        x2, y2 = pos[v]\n",
    "        ax.plot([x1, x2], [y1, y2], color=color, linewidth=2)\n",
    "\n",
    "# Draw nodes and labels\n",
    "for n, (x, y) in pos.items():\n",
    "    ax.scatter(x, y, s=100, facecolor='white', edgecolor='black', zorder=3)\n",
    "    ax.text(x, y+3, str(n), ha='center')\n",
    "\n",
    "ax.set_aspect('equal')\n",
    "ax.axis('off')\n",
    "ax.set_title('Disjoint Paths')\n",
    "plt.tight_layout()\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}