Hint

Official solution: We shall solve the problem in the alternative formulation. Let $L_G(v)$ denote the length of the longest directed chain of edges in the given graph $G$ that begins in a vertex $v$ and is arranged decreasingly relative to the numbering. By the pigeonhole principle it suffices to show that $\sum_{v}L(v) \geq 2q.$ in every such graph. We do this by induction on $q$. For $q = 1$ the claim is obvious. We assume that it is true for $q - 1$ and consider a graph $G$ with $q$ edges numbered $1,\cdots , q$. Let the edge number $q$ connect vertices $u$ and $w$. Removing this edge, we get a graph $G'$ with $q -1$ edges. We then have \[L_G(u) \geq L_{G'}(w) + 1, L_G(w) \geq L_{G'}(u) + 1, L_G(v) \geq L_{G'}(v)\] for other $v$. Since $\sum L_{G'}(v) \geq 2(q-1)$ by inductive assumption, it follows that $\sum L_{G}(v) \geq 2(q-1) + 2=2q$ as desired.

Define a poset $P$ on the edges $e\in E(G)$ with $e_1\le e_2$ iff there exists an increasing path from $e_1$ to $e_2$. No antichain has size greater than $\lfloor{n/2}\rfloor$, so by Dilworth's theorem and pigeonhole, there exists a chain of length at least $\frac{q}{\lfloor{n/2}\rfloor} \ge \frac{2q}{n}$. Equality is achieved (for the stronger $\lfloor{n/2}\rfloor$ bound) for $G = K_n$ if we consider a round robin tournament on $\binom{n}{2}/\lfloor{n/2}\rfloor$ days, and label the $i$th day's edges $(i-1)\lfloor{n/2}\rfloor+1$ to $(i-1)\lfloor{n/2}\rfloor+\lfloor{n/2}\rfloor$. If we take $E(G)$ a suitable subset of $E(K_n)$ (with the same labels) this construction also works in general.

Here's another cool solution shown to me today by Henry Cohn. Let $F(uv)$ denote the label on edge $uv$. We greedily construct directed paths $v_1v_2\ldots v_k$ (repeated vertices permitted) such that $F(v_1v_2)<\cdots<F(v_{k-1}v_k)$ and for $j=1,2,\ldots,k-1$, $v_{j+1}$ minimizes $F(v_ju)$ over all $u$ preserving the increasing path condition (more precisely, $v_ju$ must be a labeled edge, and if $j>1$, $F(v_ju)$ must be greater than $F(v_{j-1}v_j)$). We now show that there are at most $n$ such maximal directed paths. Indeed, if $w_1w_2\ldots w_r$ is maximal, $F(w_1w_2)$ must be $w_1$'s smallest label; similarly, $F(w_{r-1}w_r)$ must be $w_r$'s largest label. Thus every vertex incident to a labeled edge starts a unique maximal greedy path (and, while unnecessary, each such path obviously has a unique starting vertex), so at most $n$ such paths exist. On the other hand, each edge belongs to two (unique) maximal greedy paths, one for each direction. By pigeonhole, one of these paths must have at least $\frac{2q}{n}$ edges, as desired.

A student in one of my classes just found the following simpler argument for the original formulation: Each team has size $2$, so the total number of people appearing in the teams is $2q$. Thus, there is at least one person appearing in at least $m$ teams (because $m = \left\lceil 2q/n \right\rceil$). Pick such a person, and pick $m$ of the teams he appears in. List them in rank order. Is anything wrong with this?