MMA CTF 2015 - Task Perfect Matching

When I read this problem, I was thinking about Edmonds' algorithm, but it runs in , which is not OK for the last 10 tests. Besides, in graph_generator.py, there are no conditions that guarantee there exists a perfect matching. So, we can't solve this problem that way (or maybe we can, I haven't tried that so I don't know :)) ). But, this task is also a pwn problem, so there should be some ways to get around this.

Here's the checking code for our output:

edges = []
used_node = []
for i in range(0, v / 2):
    v1, v2 = map(int, raw_input().split())
    edges.append((v1, v2))
    used_node.extend([v1, v2])
if len(list(set(used_node))) != v:
    raise Exception() # Wrong Size
for (v1, v2) in edges: # G includes? (v1,v2)
    pos = bisect.bisect_left(graph[v1], v2) # <- vulnerable
    if pos == len(graph[v1]) or graph[v1][pos] != v2: 
        raise Exception()

We need to send back exact n different vertices, and it will check if those edges we sent exist in the graph or not. But it didn't check if the vertices are valid, or if an edge is being used twice. Since we can access negative indexes of a list in Python as wraparound elements, we can build a new bipartite graph from the edges of the old graph, and then use Hopcroft-Karp algorithm to find a maximum matching on it in time. My first implementation in Python got TLE because it's quite slow, so I modified this implementation in C++ by indy256. Here's the final code:

gist.github.com

The flag is MMA{N3gative Number index...}.