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

Problem

Ada baked some cookies for her birthday party where she invited N$N$ guests, labeled 1$1$ to N$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$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$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:-  👉CLICK HERE👈

👇👇👇👇👇

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$. T$T$ test cases follow.
The first line of each test case contains three integers N$N$, M$M$, and K$K$: the number of guests, the number of witness statements, and the maximum number of cookie stealers, respectively.

Image Labeler Round D 2022 Solution

Maximum Gain Round D 2022 Solution

Touchbar Typing Round D 2022 Solution

Suspects and Witnesses Round D 2022 Solution

The next M$M$ lines describe the witness statements. The i$i$-th line contains two integers Ai${\mathbf{A}}_{\mathbf{i}}$ and Bi${\mathbf{B}}_{\mathbf{i}}$, which means the witness statement Guest Ai${\mathbf{A}}_{\mathbf{i}}$: "Guest Bi${\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$x$ is the test case number (starting from 1) and y$y$ is the number of guests that can be proved to be innocent.

Limits

Time limit: 40 seconds.
Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
2≤N≤105$2\le \mathbf{N}\le {10}^5$.
1≤M≤105$1\le \mathbf{M}\le {10}^5$.
1≤Ai≤N$1\le {\mathbf{A}}_{\mathbf{i}}\le \mathbf{N}$, for all i$i$.
1≤Bi≤N$1\le {\mathbf{B}}_{\mathbf{i}}\le \mathbf{N}$, for all i$i$.
Ai≠Bi${\mathbf{A}}_{\mathbf{i}}\ne {\mathbf{B}}_{\mathbf{i}}$, for all i$i$.
(Ai,Bi)≠(Aj,Bj)$({\mathbf{A}}_{\mathbf{i}},{\mathbf{B}}_{\mathbf{i}})\ne ({\mathbf{A}}_{\mathbf{j}},{\mathbf{B}}_{\mathbf{j}})$, for all i≠j$i\ne j$.

Test Set 1

K=1$\mathbf{K}=1$.

Test Set 2

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