How do this faster?
1) Adding virtual edges to pairs of vertices with odd degree
2) Building Eler circuit in new graph.
3) Cutting circuit by virtual edges.
But Graph is undirected and when we removing edges
in classic stac algorithm we should use set-class as
dynamic Adj list for each vertex instead of vector-class

How to do it even faster: add virtual edges between new virtual point and odd-degree nodes. Just O(N) overhead.
(AC in 0.046 sec)

Edited by author 13.08.2008 05:28

As for bidirectionality - just add edges twice and maintain bidirectional indexation between them. Or add all edges to base-0 arraay in the order (v1;v2), (v2;v1), (v3;v4), (v4;v3), etc... then "x XOR 1" will be index of backwards edge.