###### tags: `ap325` `圖論`
# ap325 圖論 graph
## [P-7-1. 探索距離](https://judge.tcirc.tw/ShowProblem?problemid=d090)
### <法一> 用 while queue 包迴圈 來達到 BFS

// 只留程式碼關鍵

void bfs(vector<ll> graph[102], queue<ll> que, ll s)
{
    ll visit[102] = { 0 };         
    ll depth[102];

    visit[s] = 1;                     // 記得: 要讓初始點不再被尋訪
    depth[s] = 0;
    que.push(s);

    while (!que.empty()) 
    {
        ll from = que.front();
        que.pop();

        for (ll to: graph[from])      // BFS 四大任務:          
        {
            if (visit[to])                // 1.判斷 (及設定) 是否已被尋訪
                continue;
            visit[to] = 1;                // 2.設定 parent、child(這裡沒用到)
            depth[to] = depth[from] + 1;  // 3. 紀錄深度
            que.push(to);                 // 4. push 進 queue

            ans1++;
            ans2 += depth[to];
        }        
    }
}

:::success
* 利用 while queue 包迴圈。每次我會將一點從 queue 中取出，再將其相鄰的點塞入 queue 裡，如此以來，我可以用 廣度優先搜尋 的方式走完所有節點

**--> 計算圖上的距離 : 用 ＢＦＳ**
:::
&emsp;
## [P-7-2. 開車蒐集寶物](https://judge.tcirc.tw/ShowProblem?problemid=d091)
### <法一> 用迴圈包遞迴 達到 DFS

// 只留程式碼關鍵

    for (ll from, to, i = 0; i < m; i++) {
        cin >> from >> to;
        graph[from].push_back(to);
        graph[to].push_back(from);        // 注意是雙向道路: 前後都要連結
    }

//\\ 從這裡開始就在處理 dfs 了
    for (ll i = 0; i < n; i++)
        if (!visit[i])                    // 如果此點沒被碰過
        {                  
            visit[i] = 1;                 // 設定已被碰過
            ans = max(ans, dfs(i));       // 再 dfs 它
        }

    cout << ans;
}

ll dfs(ll from)
{
    ll price = 0;                         

    for (ll to : graph[from])
        if (!visit[to]) 
        {
            visit[to] = 1;
            price += dfs(to);            // 每次將 dfs 回傳的 price 承接起來 
        }
  
    return (price + treasures[from]);    // 再加上自己的 price，丟上去
}

:::success
* 利用了 "**迴圈包遞迴**"。我先讓遞迴伸到樹的底部後，再往上回傳各點的寶藏總價值。利用**深度優先搜尋法(dfs)**，可以將 child 的值回傳給 parent

**--> 想每次 "鑽到底部地" 搜尋資料 : 用 ＤＦＳ**

:::
### ＜法二＞ 併查集

// 只留程式碼關鍵

    for (ll i = 0; i < n; i++)       // ll w[50000] 儲存每一點的寶藏價值
        cin >> w[i];                  
    for (ll i = 0; i < n; i++)       // ll parent[50000] 儲存每一點的 parent
        parent[i] = -1;              // 為了讓一開始的根是自己，parent[i] 給 -1
                                     
    ll loc1, loc2;
    for (ll i = 0; i < m; i++)         
    {
        cin >> loc1 >> loc2;
        ll root1 = find_root(loc1);    // 找到 2 點的根 (源頭)
        ll root2 = find_root(loc2);    
        join(root1, root2);            // 並把 2 點所在的樹 連接在一起 
    }

    for (ll i = 0; i < n; i++)
        if (parent[i] < 0)
            ans = max(ans, w[i]);

    cout << ans;
}

ll find_root(ll x)
{                                 // 正常的 parent 值 代表母節點是誰
    if (parent[x] < 0)            // 但根的 parent 值 代表他孩子的個數 (x) 
        return x;                 //               ，並且用負數存取 (-x)
    else{
        ll root = find_root(parent[x]);
        parent[x] = root;         // 這個遞迴式很特別
        return root;              // 它會沿著樹 "往上找出" root 
    }
}

void join(ll a, ll b)
{
    if (a == b)                   // 如果 2 者的源頭一樣，就不用連接了
        return;
                                 
    if (parent[a] < parent[b]){   // 為了讓併查集 不要太多層    
        w[a] += w[b];             // 我們將 小樹併入大樹中
        parent[a] += parent[b];     
        parent[b] = a;            // 並且最後由 最終boss 吞掉所有寶藏
    }                                      
    else{
        w[b] += w[a];  
        parent[b] += parent[a];
        parent[a] = b;        
    }   
  
}

:::success
* 關於併查集的說明之後再說，或見 AP325 p.253 頁
:::
&emsp;

## [TOI2010 第二題：專案時程](https://zerojudge.tw/ShowProblem?problemid=a454)
### <法一> kahn_algorithm (topological sort)

// 只留程式碼關鍵                    (題目輸入都完整地x列在參數列，這裡省略 cin 過程)

ll kahn_algorithm(vector<ll> graph[1001], ll time[], ll n)
{
    ll parent, ans = 0;          
    ll in_degree[1001] = { 0 };    
    queue<ll> que;                  // queue 裝著正在動工的項目
    ll dp[1001] = {0};            

    for (ll i = 1; i <= n; i++)     // kahn 演算法特別地記錄了 in_degree 
        for (ll child : graph[i]) { // in_degree[i] 代表通往節點 i 的路徑數
            in_degree[child]++;     // 也代表 節點i 的母節點數 (尚未做完的項目數)
        }                           

    for (ll i = 1; i <= n; i++)    
        if (in_degree[i] == 0) {    // 找出誰是根 (沒有被任何節點通往的點就是根)
            que.push(i);            // 並從它開始 往下走訪 (que.push)
            dp[i] = time[i];        // 其中 dp[i] 定義為節點 i 的最大完成天數
        }

    while (!que.empty()) 
    {
        parent = que.front();
                                          // 因為 parent 的工作做完了 (
        for (ll child : graph[parent])    // 所以子節點的 degree 要 - 1
        {
            dp[child] = max(dp[child], dp[parent] + time[child]);

            if (--in_degree[child] == 0)  // 當工作項目 i 之前的項目都做完了
                que.push(child);          // 項目 i 才能開始動工 (que.push)
        }                     
        
        if (graph[parent].size() == 0)         // 直到探訪到末節點時
            ans = max(ans, max_time[parent]);  // ，才結算此工作的最大完成天數
           
        que.pop();
    }

    return ans;
}

:::info
(知識點1) **topological sorting**

* topological sorting 是一個將 DAG(有向無環圖) topological sort 轉成 拓樸順序的技巧。( 所謂**拓樸順序**是**將所有點排成一個序列**， **使得所有的有向邊都是由前往後**，而非由後往前)
* 計算一個圖的**拓樸排序**常用的方法有 2 個

**1. DFS** : **DFS 離開點的順序，顛倒之後，正好是拓撲順序**。因為 DFS 優先走到最深的點，所以**離開點的原則要讓最深的點先離開**，如此一來，最深的點正是拓撲順序最後的點。
　　但有時我們不想要用遞迴 (怕 stack overflow 等等)，因此我們需要一個**非遞迴**的演算法。既然要化解遞迴，那我們要找到一個合適的**計算順序**
　　為了找出合適的計算順序，我們**勢必要找出根節點 (root)**。有了根節點就能往下找第二個點、第三個點...。但甚麼點能擔當第一個點 (root) 呢 ? 是不是**沒有人能連接到的點 就可以當根節點** ? **Kahn's Algorithm 的邏輯正從找根節點的問題產生**。

**2. Kahn's Algorithm** : 當**找到根結點時**，我們會**將此根結點與其他點連接的路拆除**。**將拆除後的圖視作一個新的圖，又可以找到新的根結點** ... <u>以此類推，當我們不斷地拆解圖形時，我們即找到一個有向的計算順序。這個的計算順序正是我們要的拓樸排序</u>
:::
:::success
* 在這題中，為了取得完成工作的最少天數，我們想要**不重複地走訪這個有向圖**。其中達成這一目標的方法就是利用 **topological sort 的 kahn algorithm**
* kahn algorithm 的邏輯是這樣的。當我們從 queue 中取出一個根結點 (root) 點後，我們會將此點與其他點的鏈接斷開 (即 --deg[child])。此時若有一個子節點 斷開後變成了根結點時 (in_degree[child] == 0 )，我們將其放入 queue 裡，再進行一次循環。
　　一個良好的 DAG 在 kahn algorithm 跑完一圈後，所有點都會被數到。**如果有一點沒被數到 (代表有環)**，那此圖就不是 DAG
:::
&emsp;
## [P-7-4. 方格棋盤的最少轉彎數路線](https://judge.tcirc.tw/ShowProblem?problemid=d093)

// 只留程式碼關鍵
                                 // 利用 dx、dy 陣列來迭代每個方向
ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  

int main()
{
    // 省略 cin
    
    for (ll i = 1; i <= m; i++) {
        for (ll j = 1; j <= n; j++)
            dist[i][j] = -1;             // 沒走過的地方設為 -1
    }

    que.push({ 1, 1 });
    while (!que.empty() && dist[m][n] < 0)
    {
        pll s = que.front();
        que.pop();

        for (ll i = 0; i < 4; i++) 
        {
            ll tx = s.first + dx[i], ty = s.second + dy[i];

            while (board[tx][ty] == '0')      // 往前直走到底
            {
                if (dist[tx][ty] == -1) {     // 沒被走過的地方為起始點 + 1
                    dist[tx][ty] = dist[s.x][s.y] + 1;
                    que.push({ tx, ty });
                }
                tx = tx + dx[i];             // 就算該點有被走過，也繼續往前走
                ty = ty + dy[i];             // ( 只要不要設該點的 dist 就好 )
            }
        }
    }
    if (m == 1 && n == 1)
        cout << 0;
    else
        cout << dist[m][n];
}

:::success
* 看到距離，想到 bfs。就算是**數轉彎路線，也可以用 bfs 紀錄**。 ( 只要<u>每次移動都直走到底</u>，那麼下一次移動就可以 直接設轉彎數 + 1 )
* 另外用 dx, dy 陣列變換方向是個好注意，要學起來

:::

&emsp;
## [P-7-9. 最短路徑 (*)](https://judge.tcirc.tw/ShowProblem?problemid=d096)
### <法一> Dijkstra 演算法

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define oo 10000000
using namespace std;

ll n, m, u, v, w, ans1 = 0, ans2 = 0;
vector<pll> graph[10005];
priority_queue<pll> pq;
ll dist[10005];

void solve();
int main()
{
    cin >> n >> m;
    for (ll i = 0; i < m; i++) {
        cin >> u >> v >> w;
        graph[u].push_back({ -w, v });
        graph[v].push_back({ -w, u });
    }
    
    solve();

    for (ll i = 0; i < n; i++) {
        if (dist[i] != -oo)
            ans1 = min(ans1, dist[i]);
        else
            ans2++;
    }

    cout << -ans1 << endl << ans2;
}
---------------------------------------以下才是關鍵--------------------------------------
void solve()
{
    for (ll i = 1; i < n; i++) {        // 因為 priority_queue 是最大值優先
        dist[i] = -oo;                  // 所以我們讓 "距離加負號"，這樣就間接
        pq.push({ -oo, i });            // 達成最小值優先了 
    }                                   //  (取出來的值補負號 即可修正回來)
    pq.push({ 0, 0 });                  
    
    ll dist_, from, to;
    while (!pq.empty())                
    {
        tie(dist_, from) = pq.top();     // 每一回合取出 "到原點距離最短的點"
        pq.pop();

        for (pll path : graph[from])     
        {
            tie(w, to) = path;
            if (dist[to] > dist_ + w)    // 如果 連到鄰近的點 距離更短的話 
            {                            // 就更新距離值
                dist[to] = dist_ + w;
                pq.push({ dist[to], to });
            }
        }
    }
}

:::info
(知識點1) **最小路徑問題**

* **Case1: 如果是 無加權、無向圖** : 可以用 BFS
* **Case2: 如果是 無加權、有向無環圖 (DAG)** : 可以計算 拓樸順序
* **Case3: 如果是 有加權、有向有環圖** : 那就用 Dijkstra 演算法 (注意<u>權重應為非負</u>)
:::
:::success
* Dijkstra 的邏輯是這樣子的。我們會先從 priority_queue 中取出 "**距離最小的那一位**"，並且 **如果原點經過他連到鄰居的距離 小於鄰居本身的距離 (dist_ + w > dist[to] )** 就更新鄰居的距離值。之後就這樣 <u>不斷地抓**到原點的最近點**</u>，直到找完了所有點就結束
:::
&emsp;
## [P-7-12. 最小生成樹 (MST)](https://judge.tcirc.tw/ShowProblem?problemid=d098)
### <法一> Kruskal algorithm (使用到 併查集)

// 只留程式碼關鍵
                                    
    std::sort(graph, graph + m);   // tuple<ll, ll, ll> graph[100000]
                                   // 將權重 w 放在 tuple 首位，就能輕鬆地排序
    for (ll i = 0; i < n; i++)
        parent[i] = -1;            // ll parent[10000]

    for (ll i = 0; i < m; i++) 
    {                              // 為了形成 "最小" 生成樹
        tie(w, u, v) = graph[i];   // 將 w 由小到大挑出來
        
        ll root1 = find_root(u);
        ll root2 = find_root(v);
        
        if(join(root1, root2)){
            cost += w;             // cost 紀錄最小生成樹的成本
            round++;               // round 紀錄成功連接 幾個邊
        }

        if (round == n - 1)        // 如果 最小生成樹中有 n - 1 個邊
            break;                 // ，就可以提早結束
    }                               
    if (round == n - 1)
        cout << cost;
    else
        cout << -1;
}

//\\ -----------------------------以下為併查集 -------------------------------
ll find_root(ll x)                  
{
    if (parent[x] < 0)             
        return x;
    else
        return parent[x] = find_root(parent[x]);
}

bool join(ll a, ll b)
{
    if (a == b) return false;       // 如果 a == b，圖形會有環

    if (parent[b] >= parent[a]) {
        parent[a] += parent[b];
        parent[b] = a;
    }
    else {
        parent[b] += parent[a];
        parent[a] = b;
    }
    return true;
}

:::info
(知識點1) **最小生成樹 ( Minimun spanning tree)**

* 最小生成樹 是指 **邊的 最低建設總成本**。又因<u>樹是一個無環圖</u>，所以 **n 個點的樹必有 n - 1 個邊**
* **Case1: 如果是無加權圖**，那最小生成樹的可由 BFS , DFS 製成，且 成本 = n - 1
* **Case2: 如果是加權圖**，那最小生成樹最常用 <span style="border-bottom:2px dashed yellow;">Prim 演算法 和 Kruskal 演算法</span>

**1. Kruskal 演算法:**　Kruskal 搭配著**併查集**實作。<span style="border-bottom:2px dashed yellow;">將邊**由小到大考慮**，如果**一個邊的加入不會形成環路就將它挑入**，否則將它捨棄。**一直到挑選到 n - 1 個邊為止** (如果輸入的是連通圖，那最小生成樹一定會存在)</span>

**2. Prim 演算法**:　Prim 演算法與 Dijkstra 幾乎一模一樣。 唯一的差別是 Prim 比較的是**與 parent 相連的邊長**，而Dijkstra 比較的是**從起點走過來的距離**
:::
&emsp;
## [P-8-3. 購物中心選位置](https://judge.tcirc.tw/ShowProblem?problemid=d104)
### <法一> 距離和 = 絕對值和　**--->** 最小值發生在中位數

// 只留程式碼關鍵

    for (ll i = 0; i < n; i++){
        if (!son_deg[i])
            que.push(i);

        num[i] = 1;                 // num[100001] 代表以 i 為根的子樹的點數
    }                               

    while (!que.empty())
    {
        ll child = que.front();
        que.pop();                 // 當我們遇到第一個 子樹的點數 > n / 2 時，
                                   // 我們即找到了 中位數 
                                   // ( 中位數就是 處在 n / 2 的臨界點 ) 
        if (num[child] >= n / 2 && ans1 == -1) {
            ans1 = child;
        }
                                        // 為了計算 中位數到各村莊的距離總和
        tie(p, w) =  parents[child];   // 加權數 num[v] 也代表"該邊被經過的次數"
        num[p] += num[child];         
        ans2 += min(n - num[child], num[child]) * w ; 
                                     // 注意經過中位數後，加權要調整成 n - num[v]                
        if (--son_deg[p] == 0)       // 才能正確計算到中位數另一邊的距離總和
            que.push(p);
    }

    cout << ans1 << endl << ans2;
}

:::info
(好想法) **建立 聯想至數學的反應**

* 從這題我發現 **思考程式問題時**，如果能**將問題 化簡成數學問題**，就能產出好的演算法
* 就像這題，如果能有 **"距離和" 就是 "絕對值和"** 的反應，就能用 **min 發生在中位數** (數學解) 處理這題
:::
:::success
* 這一題的難點如上。如果能抓到中位數這概念就能迎刃而解，所以**要怎麼建立 聯想至數學問題的反應 ?**
:::
&emsp;
## [P-8-5. 自動分裝](https://judge.tcirc.tw/ShowProblem?problemid=d105)
### <法一> top down 地處理資料

// 只留程式碼關鍵                   (灰色遺留程式碼為 "不知道為甚麼錯掉的部分")
//                                  (應該是有某種反例)
struct Node
{
    ll left = 0, right = 0;
};

ll find_w(ll x);
int main()
{
    // 省略 cin 
    
    // for (ll i = 1; i < n; i++)      
    //    w[i] = -1;                   // ll w[200002] 儲存各點的總重量
                                       // ll goods[101] 儲存依序進入的貨物重量 
    // w[1] = find_w(1);               // Node nodes[100001] 儲存切換器
    for (ll i = 0; i < m; i++) {
        ll pos = 1;
        while (pos < n) {
            if (find_w(nodes[pos].left) <= find_w(nodes[pos].right)) {
                pos = nodes[pos].left;
                // w[pos] += goods[i];             
            }
            else {
                pos = nodes[pos].right;
                // w[pos] += goods[i];
            }
        }
        w[pos] += goods[i];
        cout << pos << ' ';
    }
}

ll find_w(ll x)
{
    if (x >= n)
        return w[x];
    //else if (w[x] < 0) 
    w[x] = find_w(nodes[x].left) + find_w(nodes[x].right);

    return w[x];
}

:::warning
* **原來做錯的想法:**
我原本是用 **bottom-up 的方式**，將貨物初始的重量"向上"送到頂部。但最後實作出來後卻被 killed 了
* 後來我看到講義用 **top-down 的做法 簡單易懂**後，我驚覺原來==在樹的題目中，要切換思考 top-down 和 bottom-up 的做法，並比較哪一種做起來比較好 !==
:::
:::success
* 就像上面講的，用 top-down 想法製成的 find_w() 既簡潔又易懂，造出 find_w() 正是本題的關鍵

**--> tree 的 bottom-up 無法做:　轉 top-down 遞迴來做!**
:::
&emsp;

## [P-8-8. 樹的最大獨立集](https://judge.tcirc.tw/ShowProblem?problemid=d107)

### <法一> 利用節點間得關係 -- 想出 dp 關係式

// 只留程式碼關鍵

    ll parent;                           // vector<ll> childs[100000]
    for (ll i = 1; i <= n - 1; i++) {
        cin >> parent;
        childs[parent].push_back(i);
    }
    for (ll i = 0; i < n; i++)
        dp_[i] = -1;

    cout << dp(0);
}


ll dp(ll x) 
{ 
    if (dp_[x] >= 0)                    // ll dp_[100000]
        return dp_[x];
    else {
        ll sum_C = 0, sum_S = 0;
        for (ll child : childs[x]) {
            sum_C += dp(child);
            for (ll grandson : childs[child])
                sum_S += dp(grandson);
        }
        dp_[x] = max(sum_C, sum_S + 1);
        return dp_[x];
    }
}

:::success
* 我們可以定義 dp[j] 為 以 j 為子樹的最大獨立集，因此
**d[j]=max(Cmax[j],Smax[j]+1)** ; 其中 Cmax,Smax 分別是 j 的孩子 跟 孫子的dp和

ps: 要**思考第 j 項和其他項的關係**才可能找出 dp 式
參: https://blog.csdn.net/qq_33850438/article/details/50713191


:::
### <法二> 利用樹的 "葉子數目大於節點數目"的特性 -- 貪心作法

// 只留程式碼關鍵

    for (ll i = 0; i < n; i++) {
        if (son_deg[i] == 0)        
            que.push(i);         
        chosen[i] = true;           // bool chosen[100000] 決定節點可不可以取
    }                               // ll parents[100000]
                                    // ll son_deg[100000] = {0}
    while (!que.empty())            // queue<ll> que
    {
        ll child = que.front();
        que.pop();

        if (chosen[child]) {
            indp++;
            chosen[parents[child]] = false;
        }

        if (--son_deg[parents[child]] == 0)
            que.push(parents[child]);
    }

    cout << indp;

}

:::success
* 本題利用了 "**葉節點數目 大於等於節點數目**" 的特性來寫 greedy。
因為這個特性，我可以很篤定地**取葉節點放進最大獨立集 且不取其母節點**。而我保證這樣"貪心"地做完後，一定沒有辦法挑出更多不相臨的點

* 講義中貪心證明的概念也類似，他的做法是 **先將葉節點剪下，再將 parent(v) 剪下** ( 由證明可知 v可以取代 parent(v))。**此時被剪掉後的圖形會出現新的葉節點**，再重複此步驟直到圖形被剪完為止。

**Claim: 一定有一個最大獨立集挑選了 v (葉節點) 而沒選 parent(v)**

:::

&emsp;
## [P-8-14. 血緣關係](https://judge.tcirc.tw/ShowProblem?problemid=d111)
### <想法一> top-down DP

// 只留程式碼關鍵

    dfs(root);

    cout << maxi;                   // ll height[100001] = { 0 };
}                                   // height[i] 記錄點 i 的高度
 
void dfs(ll x)                         
{                                   // 以下的計算方式 : 不用求出最大值和次大值
    for (ll child : childs[x])      // 只要 "維護好最大值"，我們就可以將
    {                               // 最大值 + 次大值 求出來
        dfs(child);
        maxi = max(maxi, height[x] + height[child] + 1);
        height[x] = max(height[x], height[child] + 1);
    }
}

:::success

* 本題想到的關鍵在於 "**使用 dfs 的計算順序思考**"。在每一個 dfs 的節點中，我會 <u>取 最長鏈和次長鏈</u> 以求得最遠距離，並 用 最長鏈來代表此節點 ( <u>畢竟對其他鍊而言，只有最長鍊是重要的 </u>)
* 按照 dfs 的計算順序 就能得到最遠血緣距離。另外就算此點只有一個子節點，我的計算方式依然能算出當下的最遠距離

:::
&emsp;

## [Subtree Queries](https://cses.fi/problemset/result/5946464/)
### <法一> 樹壓平 + BIT

// 只留程式碼關鍵
                             // const ll maxN = 2e5 + 5
ll bit[2 * maxN];            // ll n, q, t = 1;
                             // ll val[maxN], in[maxN], out[maxN]; 
ll query(ll l, ll r)         // vector<ll> graph[maxN];
{
    if (l > 1)
        return query(1, r) - query(1, l - 1);
    else
    {
        ll sum = 0;
        for (ll i = r; i > 0; i -= i & (-i))
            sum += bit[i];
        return sum;
    }
}

void update(ll i, ll x)
{
    for (; i <= 2 * n; i += i & (-i)) 
        bit[i] += x;
}


void tour(ll u, ll fa)  // 樹壓平
{
    in[u] = t;
    update(t, val[u]);  // 進入時紀錄一次，出去時紀錄一次
    t++;                // 確保到時輸出時直接除 2 即有答案

    for (ll v : graph[u]) {
        if (v == fa)
            continue;
        tour(v, u);
    }

    out[u] = t;
    update(t, val[u]);
    t++;
}

                          
int main()                       
{                                
    // 省略初始化
    tour(1, 0);

    ll c, s, x;
    for (ll i = 0; i < q; i++) {
        cin >> c;
        if (c == 1) {
            cin >> s >> x;
            update(in[s], x - val[s]);
            update(out[s], x - val[s]);
            val[s] = x;
        }
        else {
            cin >> s;
            cout << query(in[s], out[s]) / 2 << "\n";
        }
    }
}

:::success
* 要怎麼計算子樹的區間和? 難道要每一次都 dfs 一次嗎?

* 其實利用**樹壓平**的技巧**將樹化成一維陣列**後，**再用**單點加值、區間查詢的利器 **BIT 做查詢問題**即可

**--> 看到樹的相關問題: 問自己，換成 "陣列" 會更好處理嗎?**
:::