# Pembahasan Soal Tukang Pos
### Subsoal 1
Perhatikan bahwa graf yang diberikan dijamin punya *degree* genap pada setiap *node*.

Hal ini bisa dijamin karena kita dijamin bahwa graf yang diberi bisa dipisah menjadi beberapa *cycle* yang secara keseluruhan melewati tiap edge tepat sekali. Perhatikan jika kita "menghapus" suatu cycle dari graf, maka degree setiap *node* di graf tidak akan berubah *parity*-nya (*parity* merupakan genap/ganjil). Oleh karena itu, dapat disimpulkan bahwa jika akhirnya setiap edge bisa "dihapus", maka setiap *node* pasti mempunyai *degree* yang genap (karena akhirnya pasti mempunyai *degree* 0 yang genap).

Oleh karena itu, kita dapat mencoba mencari *cycle* sembarang lalu menghapus *cycle* tersebut dari graf. Setelah kita menemukan *cycle*, kita hapus saja edge dari adjacency list yang kita miliki.

Kompleksitas: $O(N^2+M)$

### Subsoal 2
Kita dapat mengoptimisasi penghapusan edge dengan menggunakan set untuk menyimpan adjacency list. Dengan itu kita bisa mempercepat penghapusan.

Kompleksitas: $O((N+M)\text{log}(N+M))$

### Subsoal 3
Perhatikan bahwa solusi menggunakan set akan TLE karena set merupakan struktur data yang lambat (meskipun kompleksitasnya bagus) karena memiliki konstanta besar. Oleh karena itu, kita harus menggunakan cara lain untuk menghapus edge.

Untuk melakukan itu, kita bisa menggunakan teknik pending delete untuk mempercepat proses penghapusan. Singkatnya, saat menghapusa kita hanya menandai saja bahwa edge tersebut sudah dihapus tetapi tidak kita hapus dari adjacency list. Nanti saat memproses edge di adjacency list, kita memeriksa apakah edge tersebut sudah dihapus atau belum. Jika sudah dihapus, maka kita tidak perlu proses. Jika belum dihapus, maka kita proses. Lebih mudah untuk memproses dari vector.back() saja agar bisa menghapus dengan mudah.

Kompleksitas: $O(N+M)$