Single Route - Repovive Starter Round 9 | Repovive

25F. Single Route

3000 pts2s256 MB

You are given a directed acyclic graph with $n$ vertices and $m$ edges. The $i$ -th edge goes from vertex $u_i$ to vertex $v_i$ . Initially, every vertex is reachable from vertex $1$ .

You may remove at most one edge. After the removal, there must be at most one directed path from vertex $1$ to each vertex.

Find the maximum number of vertices that can remain reachable from vertex $1$ , or report that this is impossible. Vertex $1$ itself is considered reachable.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le u_i, v_i \le n$
The graph has no directed cycles or parallel edges.
Initially, every vertex is reachable from vertex $1$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

$\mathrm{answer} = -1$ if it is impossible.

Samples

Input

Case 1

Case 2

Explanation

Case 1

No edge needs to be removed. All four vertices are reachable, and each has a unique path from vertex $1$ .

Case 2

There are two paths from vertex $1$ to vertex $4$ and two paths from vertex $1$ to vertex $7$ . The edges used by these two pairs are disjoint, so removing one edge cannot fix both.

Output

Case 1

Case 2

-1

Input

Case 1

1 0

Case 2

Case 3

Explanation

Case 1

The only vertex is vertex $1$ , which is reachable.

Case 2

Remove the edge $2 \to 4$ . All four vertices remain reachable, and each has a unique path from vertex $1$ .

Case 3

Remove the edge $1 \to 2$ . Exactly vertices $1$ , $4$ , and $5$ remain reachable, each by a unique path. Every other single-edge removal leaves two paths to vertex $4$ or vertex $5$ , so the answer is $3$ .

Output

Case 1

Case 2

Case 3

You are given a directed acyclic graph with $n$ vertices and $m$ edges. The $i$ -th edge goes from vertex $u_i$ to vertex $v_i$ . Initially, every vertex is reachable from vertex $1$ .

You may remove at most one edge. After the removal, there must be at most one directed path from vertex $1$ to each vertex.

Find the maximum number of vertices that can remain reachable from vertex $1$ , or report that this is impossible. Vertex $1$ itself is considered reachable.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$0 \le m \le 2 \times 10^5$
$1 \le u_i, v_i \le n$
The graph has no directed cycles or parallel edges.
Initially, every vertex is reachable from vertex $1$ .
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

$\mathrm{answer} = -1$ if it is impossible.

No edge needs to be removed. All four vertices are reachable, and each has a unique path from vertex $1$ .

There are two paths from vertex $1$ to vertex $4$ and two paths from vertex $1$ to vertex $7$ . The edges used by these two pairs are disjoint, so removing one edge cannot fix both.

The only vertex is vertex $1$ , which is reachable.

Remove the edge $2 \to 4$ . All four vertices remain reachable, and each has a unique path from vertex $1$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25F. Single Route

Constraints

Input

Output

Samples

25F. Single Route

Constraints

Input

Output

Samples