一筆書きができるか？という問題です。一筆書きができる条件は、頂点の次数が奇数であるものが 2 個以下であることです。

よって、この問題を \(O(N+M)\) で解くことができました。

想定解 (c++)

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    long long K;
    cin >> K;
    vector<long long> d(N);
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        d[a-1] += K;
        d[b-1] += K;
    }
    int odd = 0;
    for(long long x : d){
        if(x % 2 == 1){
            odd++;
        }
    }
    cout<<(odd <= 2 ? "Yes" : "No")<<endl;
}