## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Suspects and Witnesses Round D 2022 | Kick Start 2022 Solution

### Problem

Ada baked some cookies for her birthday party where she invited $N$ guests, labeled $1$ to $N$. When all the guests have arrived and the party is about to start, something terrible has happened — someone stole the cookies!

Ada puts on her detective hat and starts questioning her guests. She gathered $M$ witness statements of the form: Guest x: "Guest y did not steal the cookies."

Ada knows that, if a guest is innocent (did not steal a cookie), then all their witness statements must be true. Note that Ada does not know whether any statement made by a cookie stealer is correct.

Lastly, Ada has an informant who told her there can be at most $K$ cookie stealers. With this information, can you help Ada find out the number of guests who can be proved to be innocent?

Solution Click Below:-  👉
👇👇👇👇👇

Note that it is possible that no guest actually stole the cookies, and Ada simply forgot how many cookies she baked.

### Input

The first line of the input gives the number of test cases, $T$$T$ test cases follow.
The first line of each test case contains three integers $N$$M$, and $K$: the number of guests, the number of witness statements, and the maximum number of cookie stealers, respectively.

The next $M$ lines describe the witness statements. The $i$-th line contains two integers ${\mathbf{A}}_{\mathbf{i}}$ and ${\mathbf{B}}_{\mathbf{i}}$, which means the witness statement Guest ${\mathbf{A}}_{\mathbf{i}}$: "Guest ${\mathbf{B}}_{\mathbf{i}}$ did not steal the cookies."

### Output

For each test case, output one line containing Case #x$x$: y$y$, where $x$ is the test case number (starting from 1) and $y$ is the number of guests that can be proved to be innocent.

### Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
$1\le \mathbf{T}\le 100$.
$2\le \mathbf{N}\le {10}^{5}$.
$1\le \mathbf{M}\le {10}^{5}$.
$1\le {\mathbf{A}}_{\mathbf{i}}\le \mathbf{N}$, for all $i$.
$1\le {\mathbf{B}}_{\mathbf{i}}\le \mathbf{N}$, for all $i$.
${\mathbf{A}}_{\mathbf{i}}\ne {\mathbf{B}}_{\mathbf{i}}$, for all $i$.
$\left({\mathbf{A}}_{\mathbf{i}},{\mathbf{B}}_{\mathbf{i}}\right)\ne \left({\mathbf{A}}_{\mathbf{j}},{\mathbf{B}}_{\mathbf{j}}\right)$, for all $i\ne j$.

#### Test Set 1

$\mathbf{K}=1$.

#### Test Set 2

$1\le \mathbf{K}\le 20$.