Maximum number of edges in a directed graph with the following "at most one path" condition

Let $G$ be a directed graph with $n$ vertices, and let there be vertices $s$ (source) and $t$ (sink) such that

1. Every vertex is reachable from $s$, and can reach $t$. (I.e., for every $v$, there is a path from $s$ to $t$ going through $v$.)

2. For every pair of vertices $u, v$ and for every integer $k \ge 0$, there is at most one path of length $k$ from $u$ to $v$.

What is the maximum number of edges in $G$?

I'm mostly interested in the asympototic growth of the answer -- is there a linear (in $n$) upper bound on the number of edges? Can it be quadratic?

Observations:

• Without condition (1), the number of edges can be quadratic. We can split the $n$ vertices into two halves of $(n/2)$ vertices each, and connect every pair from the first to the second, yielding $\frac{n^2}{4}$ edges.

• The question is related to the theory of finite automata. The directed graph with $n$ vertices and $s, t$ is an NFA over a singleton alphabet $\{a\}$, with no epsilon transitions, and with only one initial state and accepting state. Condition (1) says that the automaton is trim (this word indicates that all unnecessary states have been removed). Condition (2) says that the automaton is unambiguous. Thus the question is a special case of this more general problem: find the maximum possible number of transitions in a trim, unambiguous NFA.

• Although this seems needlessly obscuring, we can equivalently state conditions (1) and (2) using the adjacency matrix of $G$. Let $A$ be the adjacency matrix, and let $e_1, e_2, \ldots, e_n$ be the standard basis, with $s = e_1$ and $t = e_n$ WLOG. Then the conditions are:

  1. For all $i$, there exist integers $k, l \ge 0$ such that $e_1^T A^k e_i e_i^T A^l e_n > 0$.

  2. For all $1 \le i, j \le n$ and $k \ge 0$, $e_i^T A^k e_j \le 1$.

  In particular, condition (2) says that $A^k$ is a matrix of $0$s and $1$s, for all $k$.

  The number of edges in $G$ is then $u^T A u$, where $u = e_1 + e_2 + \cdots + e_n$.

By condition (1), there exists a subgraph $S_s$ of $G$ that is a rooted tree from $s$ to every other node. Similarly there exists another subgraph $S_t$ of $G$ that is a (reverse) tree going from each node to $t$. Let $S$ be the union of $S_s$ and $S_t$. Clearly $S$ has a linear number of edges.

Whenever we add an edge to $S$, we will have a new path going from $s$ to $t$ whose length is at most $2n$ (if we add an edge $u \to v$, this path will be $s \to \cdots \to u \to v \to \cdots \to t$). By condition (2), we can thus add at most $O(n)$ such edges. Since we can construct $G$ by repeatedly adding new edges to $S$, $G$ must have a linear number of edges.