一筆畫問題是圖論中很經典的一道題目。對於一張給定的無向圖，要怎麼找到一條路徑使每條邊都剛好被經過一次呢？我們把這條路徑稱作歐拉路徑（Euler path），
假如起點跟終點在同一個頂點的話又叫歐拉迴路（Euler circuit）。
那一張圖擁有歐拉路徑的條件是什麼呢？
首先，先假設圖是連通的。此時，透過簡單的觀察還可以發現，除了起點與終點以外，每個點被經過時都是進去又出來，所以這些點的度數一定要是偶數。
很神奇的，這些就剛剛好是一張圖擁有歐拉路徑的充要條件！
連通無向圖 $G$ 存在歐拉路徑的充要條件是：$G$ 中奇頂點（點度為奇數的點）恰有 0 個或 2 個。
連通無向圖 $G$ 存在歐拉迴路的充要條件是：$G$ 中所有頂點的度都是偶數。
雖然我們可以利用上述證明提到的方法來找歐拉迴路，但這看起來就很麻煩，所以我們要介紹一種可以一次 DFS 找完歐拉迴路的方式。
剛才的問題主要是我們找完一段路之後可能還會在中間多插幾個迴路，為了解決這個問題，我們改成確定一段路徑中間不需要再插入後才儲存這段路徑。
一樣先從某個點出發走到沒路，這時候我們可以相信最後拜訪的邊一定是最後一條邊，因為也走不出去了。
我們把這條邊加到答案，並且回頭檢查上一個點 $v$，如果 $v$ 旁邊的邊也都走過了，那我們就可以把前一條邊也加進答案，並且繼續往回檢查。如果 $v$ 旁邊還有邊可以走，那我們就先走過去看看，反正繞一圈還是會回到 $v$，這時候我們就把多走的邊也從後面一條一條檢查後加進答案，再把一開始走到 $v$ 的邊也加進去。
重複這個動作直到每條走過的邊都檢查完，根據前面的觀察一定會形成歐拉迴路。
vector<pair<int, int>> edges[mxn];
bool used[mxn];
int ptr[mxn];
vector<int> ans;
void dfs(int now) {
for (int &i = ptr[now]; i < int(edges[now].size());) {
auto [to, eid] = edges[now][i++];
if (used[eid]) continue; // 避免使用到重複的邊
used[eid] = true;
dfs(to);
ans.push_back(eid);
}
}
// reverse(ans.begin(), ans.end()) 之後就是一條歐拉迴路/路徑
需要注意的是對於一個點，如果我們已經走過某些邊了，之後每次又從頭開始找沒有走過的邊的話複雜度會炸成 $O(NM)$ 。因此，對於每個點我們需要額外維護我們已經拜訪過這個點多長的前綴了，以方便之後直接跳過已經走過的邊。此外，因為邊是無向邊所以可能某條邊已經走過 $u$ 到 $v$ 的方向之後，我們會在 $v$ 的邊裡面看到它，但它是不能走的。解決方法有兩種：把鄰接陣列改成用 std::set 紀錄，刪除 $u \to v$ 時同時刪除 $v \to u$ ，另一種方式是在對每條邊進行編號（兩個方向的邊編號相同），刪除時跳過已經被刪到的邊。
一個細節是如果圖不連通，可能還是有歐拉迴路。但是，此時的圖上所有邊都必須要在同一個連通塊上，因此，只要檢查所有邊所在的連通塊是否有歐拉迴路就好。
很多歐拉迴路的題目都不會直接告訴你圖長怎樣，例如下面這道例題：
給 $M$ 個長度為偶數的陣列，請把每個陣列中恰一半的元素丟到 multiset $L$ 裡面，另外一半的元素丟到 multiset $R$ 裡面，且最後 $L$ 和 $R$ 要長一樣（每一種值的出現個數都一樣）。
雖然這題並沒有直接點明是圖論，但是它包含了一些歐拉迴路常見的關鍵字：分兩邊讓兩邊長一樣，因為歐拉迴路的特點就是對每個點來說入邊和出邊一樣多，我們可以試著用這個性質來建圖。
我們考慮建一張二分圖，二分圖左側的每個點代表一個陣列 $a$，總共 $M$ 個點；二分圖右側邊每個點代表一個值 $x$，總共「數值種類數」個點。這樣一來，對於每個 $a_i = x$，我們只要建立一條 $(a, x)$ 的邊就可以了。
這樣建完的目的是什麼呢？假如這張圖能找到一條歐拉迴路，那麼把每條邊定向，從左到右的放到第一個 multiset，從右到左的放到第二個 multiset，就能滿足那兩個條件了。那如果找不到歐拉迴路呢？如果是因為不連通的話，其實可以發現連通性在這題根本不重要，所以我們應該對每個連通塊分別去找找看，然後直接合併答案就好了。但如果是有某個連通塊存在奇度數的點，那就代表有個數字出現奇數次，這樣顯然就是無解的情況。
一樣的問題也可以搬到有向圖上，但因為每條邊的方向被限制了，存在解的條件也會更嚴格。可以發現現在變成起點的出邊比入邊多一條（如果這不是迴路），終點的入邊比出邊多一條，而剩下的點在被經過時都是一進一出抵消，兩種邊一樣多。同樣可以得到相似的結論，只要連通性和出入度的要求滿足了，就一定能找到歐拉迴路，而且找解的方式跟無向圖一模一樣。證明留給讀者自行練習。
當一張圖沒辦法一筆畫畫完的時候，我們可能會想進一步知道：那最少需要幾筆畫？說得更清楚一點，我們希望找到最小的 $K$，使得存在 $K$ 條路徑滿足圖上每條邊都恰好被其中一條路徑經過一次。
每個連通塊顯然可以分開看，而一個連通塊內如果有 $2K$ 個奇頂點的話，我們每劃掉一條路徑最多讓 2 個點的度數變成偶數，因此至少需要 $K$ 筆畫。實際上，$K$ 筆畫一定足夠，因為我們可以把 $2K$ 個頂點兩個兩個一組多連 $K$ 條邊，這時一定存在歐拉迴路，再把那 $K$ 條邊拔掉就形成 $K$ 條路徑了。
因此，一些 $K$ 筆畫的應用題可能會長得像：把一些東西分兩邊讓兩邊盡可能相似。解題的技巧會在於先假設兩邊可以完全一樣去建出圖，再透過新增點或邊把度數不對的點補到對。這類題目往往最難的是想出怎麼建圖，因此建議多看題目熟悉各種建圖方式。
歐拉迴路有個跟他很像的問題，也就是哈密頓迴路。
要注意到，哈密頓迴路目前是沒有多項式時間的解法，而歐拉迴路則是有線性解。因此，如果把題目建圖之後發現要找哈密頓路徑時，不妨試試看換的方法建圖，或許可以把點跟邊換過來之後轉成歐拉迴路。
給定 $N$ 點 $M$ 邊的無向圖，圖可能包含重邊和自環，請找到一條路徑使得每條邊被使用恰好一次。
給定 $N$ 點 $M$ 邊的有向圖，圖可能包含重邊和自環，請找到一條路徑使得每條邊被使用恰好一次。
知名的電視節目「Jumping Kid」即將在台北市舉辦一場大規模的打卡遊戲，在這個遊戲中，每個參賽隊伍會收到相同的 $K$ 個任務，每個任務包含一個夜市景點和一個公園景點，解決任務的方法，則是需要以計程車為交通工具，在該任務的兩個景點（不限定順序）完成打卡，而每次的計程車車資為起跳金額 $S$ 元，加上每公里 $M$ 元（假設計程車皆走最短路徑，且雙向的路徑長度相同）。
參賽隊伍可以選擇任一景點做為打卡遊戲的出發地點，為了節目效果，每個參賽隊伍一次只能執行一個任務，並不允許同時執行兩個（含）以上的任務，且每個任務也僅能執行一次。同時，為了節省車資，當任務的終點恰好是下一個任務的起點時，節目單位允許參賽隊伍可以連續打卡，以避免因為換車所需要多付的起跳金額 $S$ 元。另外，若任務的終點與下一個任務的起點不相同時，主辦單位會提供免費專車將參賽隊伍運送到下一個任務的起點，但參賽隊伍在抵達後，必須自行換乘計程車繼續解決任務，並且自付所需的車資。
您現在是這項遊戲的參賽者之一，請您根據主辦單位公佈的 $K$ 個任務，規劃可以用最少車資完成遊戲的方法，並且輸出您總共搭乘的計程車數量（假設每次叫車時，都搭乘到不一樣的車子）。
給一張 $N$ 點 $M$ 邊的無向圖，問有多少對邊的 pair $(e_i, e_j)$ 滿足存在一條路徑經過這兩條邊恰一次且經過剩餘的每條邊恰兩次。
有八種形狀的一維拼圖（只有左右有凸起或缺口），現在給你 $N$ 塊拼圖，每一塊會告訴你他的類別以及其編號，試判斷是否存在一種拼法讓所有拼圖都能被用上。若存在，請找到最小字典序的拼法。
一筆畫問題是一個經典的圖論問題，用圖論術語來描述的話，就是給定一張圖，問存不存在一條從 $s$ 到 $t$ 的路徑，滿足所有邊都恰被遍歷一次（點則可以被重複遍歷），這樣的路徑又被稱為「歐拉路徑」。
當然，一筆畫問題在有向圖上也是可以解決的！因此，現在給你一張 $N$ 點 $M$ 邊的有向圖，請你先判斷這張有向圖有幾種 $s=1, t=N$ 的歐拉路徑，並在有至少一種時，輸出一條從 $1$ 到 $N$ 的歐拉路徑。
不過，因為歐拉路徑的數量可能很多，所以假設總共有 $k$ 種歐拉路徑，你只需要輸出 $\min(k, 2)$ 就可以了。
頒獎音樂由 $N$ 個音符組成，第 $i$ 個音符的音高是 $a_i$ 。你可以修改這個音樂任意次，在一次修改中，只能選擇一個滿足第一個音符和最後一個音符音高相同的區間，並將這個區間反轉。請構造出 $a_{i-1} < a_i > a_{i+1}$、$a_{i-1} > a_i < a_{i+1}$ 數量總和最少的一組可能。